2.17. Другие алгоритмы с открытым ключом

Хотя алгоритм RSA получил широкое распространение, он ни в коей мере не является единственным известным алгоритмом с открытым ключом. Первым алгоритмом с открытым ключом стал «алгоритм ранца». Его идея состоит в том, что имеется большое количество объектов различного веса.

Владелец этих объектов кодирует сообщение, выбирая подмножество объектов и помещая их в ранец. Общий вес объектов в рюкзаке известен всем, как и список всех возможных объектов. Список объектов, находящихся в рюкзаке, хранится в секрете. При определенных дополнительных ограничениях, задача определения возможного списка объектов по известному общему весу считалась неразрешимой для вычисления, то есть считалось, что решение можно найти только полным перебором различных сочетаний предметов списка. Поэтому она была положена в основу алгоритма с открытым ключом.

Изобретатель алгоритма Ральф Меркле был настолько уверен в надежности своего алгоритма, что предложил 100 долларов любому, кто сумеет его взломать. Ади Шамир, мгновенно взломал его и получил награду. Это не смутило Меркле. Он усилил алгоритм и предложил за его взлом уже 1000 долларов. Рон Ривест, «R» в RSA, тут же взломал улучшенную версию алгоритма и получил награду. Несмотря на то, что алгоритм ранца был в очередной раз исправлен, он не считается надежным и редко используется.

Другие схемы с открытым ключом основаны на сложности вычисления дискретных логарифмов. Алгоритмы, использующие этот принцип, были разработаны Эль-Гамалем и Шнорром.

Существуют и некоторые другие методы, например, основанные на эллиптических кривых. Однако две основные категории составляют алгоритмы, основанные на сложности нахождения делителей больших чисел и вычислений дискретных логарифмов. Эти задачи считаются особенно сложными, так как математики уже много лет пытаются их решить без особых успехов.

2.18. Цифровые подписи.

Подлинность различных бумажных документов (юридических, финансовых и др.) определяется наличием или отсутствием авторизованной рукописной подписи. Фотокопии документами не считаются. Чтобы системы компьютерных сообщений могли заменить физическое перемещение документов, написанных чернилами на бумаге, нужно решить проблему подписи.

Проблема разработки замены рукописной подписи довольно сложна. По существу, требуется система, с помощью которой одна сторона могла бы послать другой стороне «подписанное» сообщение так, чтобы:

• получатель мог проверить объявленную личность отправителя;

• отправитель не мог позднее отрицать содержимое сообщения;

• получатель не мог позднее изменить подписанное сообщение.

Первое требование существенно, например, для финансовых систем. Когда компьютер клиента заказывает компьютеру банка купить тонну золота, банковский компьютер должен быть уверен, что компьютер, пославший заказ, действительно принадлежит компании, со счета которой следует снять денежную сумму. Другими словами, банк должен иметь возможность установить подлинность клиента (а клиент — подлинность банка).

Второе требование необходимо для защиты банка от мошенничества. Предположим, что банк покупает тонну золота, и сразу после этого цена на золото резко падает. Бесчестный клиент может подать в суд на банк, заявляя, что он никогда не посылал заказа на покупку золота. Банк может показать сообщение в суде, но клиент будет отрицать, что посылал его. Таким образом, должно быть обеспечено требование невозможности отречения от данных ранее обязательств. Методы составления цифровых подписей, которые мы изучим далее, предназначены, в том числе и для этого.

Третье требование нужно для защиты клиента в случае, если цена на золото после его покупки банком взлетает вверх и банк пытается создать подписанное сообщение, в котором клиент просит купить не одну тонну золота, а один слиток. При таком сценарии банк, совершив мошенничество, забирает оставшуюся часть золота себе.

Подписи с симметричным ключом

Один из методов реализации цифровых подписей состоит в создании некоего центрального авторитетного органа (АО), которому все доверяют. Затем каждый пользователь выбирает секретный ключ и лично относит его в АО. Таким образом, например, секретный ключ Алисы, К_А, известен только Алисе и АО.

Когда Алиса хочет послать открытым текстом своему банкиру Бобу подписанное сообщение Р, она формирует сообщение, зашифрованное К_А (ключом Алисы), К_А(В, R_A, t, Р), где В - идентификатор Боба, R_A - случайное число, вы-бранное Алисой, t — временной штамп, подтверждающий свежесть сообщения.

Затем она посылает его АО, который видит, что это сообщение от Алисы, расшифровывает его и посылает Бобу. Сообщение, посылаемое Бобу, содержит открытый текст сообщения Алисы и подпись АО К_АО(А, t, Р). Получив подписанное сообщение, Боб может выполнять заказ Алисы.

Что случится, если позднее Алиса станет отрицать отправку этого сообщения? Естественно, в случае возникновения подобных конфликтов конфликтующие стороны первым делом подают друг на друга в суд. Наконец, когда дело попадает в суд, Алиса энергично утверждает, что она не отправляла Бобу обсуждаемое. Судья спрашивает Боба, почему он уверен, что данное сообщение пришло именно от Алисы, а не от злоумышленницы Труди. Боб сначала заявляет, что АО не принял бы сообщения от Алисы, если бы оно не было зашифровано ее ключом К_А, — у злоумышленника просто нет возможности послать АО фальшивое сообщение от Алисы.

Затем Боб элегантным жестом демонстрирует суду сообщение А: К_АО(А, t, P). Боб заявляет, что это сообщение подписано АО, что доказывает, что Алиса послала сообщение Р Бобу. Затем судья просит АО (которому все доверяют) проверить подпись под этим сообщением. Когда АО подтверждает, что Боб говорит правду, судья решает дело в пользу Боба.

Теоретически проблема с этим протоколом цифровых подписей может возникнуть, если злоумышленник повторно воспроизведет оба сообщения. Для минимизации вероятности этого используются временные штампы. Кроме того, Боб может просмотреть все недавние сообщения, проверяя, не встречалось ли в них такое же RA. В этом случае сообщение считается дубликатом и просто игнорируется. Очень старые сообщения, обнаруживаемые по значению временного штампа, также игнорируются. Для защиты от мгновенной атаки повторным воспроизведением Боб просто проверяет значение случайного числа RA, содержащегося в каждом приходящем сообщении, запоминая все такие числа, полученные за последний час. Если в течение часа такое значение получено еще не было, Боб может быть уверен, что пришедшее сообщение является новым заказом.