было бы около 21024. В этом случае каждый блок мог бы содержать до 1024 бит или 128 восьмиразрядных символов против 8 символов шифра DES или 16 AES.

Рис. 8.14. Пример работы алгоритма RSA

Следует отметить, что использование алгоритма RSA в описанном выше виде аналогично использованию симметричного алгоритма в режиме ECB (Electronic Code Book — электронный шифроблокнот), в котором одинаковые блоки на входе преобразуются в одинаковые блоки на выходе. Таким образом, для шифрования данных требуется сцепление блоков в каком-либо виде. Однако на практике алгоритм RSA с открытым ключом используется только для передачи одноразового секретного ключа, после чего применяется какой-нибудь алгоритм с симметричным ключом типа AES или тройного DES. Система RSA слишком медленная, чтобы шифровать большие объемы данных, однако она широко применяется для распространения ключей.

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

Хотя алгоритм RSA получил широкое распространение, он ни в коей мере не является единственным известным алгоритмом с открытым ключом. Первым алгоритмом с открытым ключом стал «алгоритм ранца» (Merkle и Hellman, 1978). Его идея состоит в том, что имеется большое количество объектов различного веса. Владелец этих объектов кодирует сообщение, выбирая подмножество объектов и помещая их в ранец. Общий вес объектов в рюкзаке известен всем, как и список всех возможных объектов и их соответствующий вес. Список объектов, находящихся в рюкзаке, хранится в секрете. При определенных дополнительных ограничениях задача определения возможного списка объектов по известному общему весу считалась неразрешимой по вычислениям, то есть считалось, что решение можно найти только полным перебором различных сочетаний предметов списка. Поэтому она была положена в основу алгоритма с открытым ключом.

Изобретатель алгоритма Ральф Меркле (Ralph Merkle) был настолько уверен в надежности своего алгоритма, что предложил $100 любому, кто сумеет его взломать. Ади Шамир (Adi Shamir), «S» в группе RSA, мгновенно взломал его и получил награду. Это не смутило Меркле. Он усилил алгоритм и предложил за его взлом уже $1000. Рон Ривест (Ron Rivest), «R» в RSA, тут же взломал улучшенную версию алгоритма и получил награду. Меркле не рискнул предложить $10 000 за следующую версию, поэтому «A», Леонарду Эйдлману (Leonard Adleman), не повезло. Несмотря на то что алгоритм ранца был в очередной раз исправлен, он не считается надежным и редко используется.

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

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

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

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

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

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

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

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

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

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

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

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

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

Когда Алиса хочет послать открытым текстом своему банкиру Бобу подписанное сообщение P, она формирует сообщение, зашифрованное KA (ключом Алисы), KA(B, RA, t, P), где B — идентификатор Боба, RA — случайное число, выбранное Алисой, t — временной штамп, подтверждающий свежесть сообщения. Затем она посылает его Большому Брату, как показано на рис. 8.15. Большой Брат видит, что это сообщение от Алисы, расшифровывает его и посылает Бобу. Сообщение, посылаемое Бобу, содержит открытый текст сообщения Алисы и подпись Большого Брата KBB(A, t, P). Получив подписанное сообщение, Боб может выполнять заказ Алисы.

Рис 8.15. Цифровая подпись Большого Брата

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

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

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