Чтение онлайн

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

Хотя RSA по-прежнему популярен, это далеко не единственный известный алгоритм с открытым ключом. Первым таким алгоритмом стал алгоритм на основе задачи о рюкзаке (knapsack algorithm) Меркла и Хеллмана (Merkle and Hellman, 1978). Его принцип заключается в следующем. Допустим, имеется очень большое количество объектов разного веса. Их владелец кодирует сообщение, выбирая подмножество вещей и помещая их в рюкзак. Известен общий вес объектов в рюкзаке, а также список всех возможных объектов и их вес по отдельности. Список вещей в рюкзаке хранится в секрете. Считалось, что при некоторых дополнительных ограничениях определить возможный список объектов по известному общему весу невозможно путем вычислений. Поэтому эта задача легла в основу алгоритма с открытым ключом.

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

Остальные алгоритмы с открытым ключом основаны на сложности вычисления дискретных логарифмов или значений эллиптических кривых (Менезес и Ванстоун; Menezes and Vanstone, 1993). Первые были разработаны Эль Гамалем (El Gamal, 1985) и Шнорром (Schnorr, 1991). Вторые используют раздел математики, известный в очень узких кругах, — теорию эллиптических кривых.

Существует и ряд других схем, однако алгоритмы, использующие сложность факторизации больших чисел, вычисления дискретных логарифмов, разделенных по модулю на большое простое число, и значений эллиптических кривых, безусловно, являются самыми важными. Эти задачи считаются по-настоящему сложными, так как математики пытаются их решить уже много лет без особого успеха. Эллиптические кривые здесь представляют особый интерес, поскольку задачи дискретного логарифмирования на такой кривой еще сложнее, чем задачи разложения на множители. Голландский математик Арьен Ленстра (Arjen Lenstra) предложил сравнивать криптографические алгоритмы по количеству энергии, которая тратится на их взлом. По его расчетам, чтобы взломать 228-битный RSA-ключ, требуется примерно столько же энергии, сколько нужно для того, чтобы вскипятить одну чайную ложку воды. Однако в случае ключа той же длины на базе эллиптической кривой на взлом уйдет столько же энергии, сколько нужно для того, чтобы вскипятить всю воду на планете. Перефразируя Ленстра, можно сказать, что даже испарив всю воду (включая воду в их телах), взломщики вряд ли добьются успеха.

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

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

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

1. Получатель может проверить заявленную личность отправителя.

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

3. Получатель не имеет возможности изменить сообщение.

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

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

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

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

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

Обозначение

Описание

A

Алиса (отправитель)

B

Банковский менеджер Боб (получатель)

P

Открытый текст сообщения, которое хочет отправить Алиса

BB

Большой Брат (авторитетный центральный орган)

t

Временная метка (для подтверждения новизны)

RA

Случайное число, выбранное Алисой

Симметричный ключ

KA

Секретный ключ Алисы (аналогично и в случае KB, KBB и т.д.)

KA(M)

Сообщение M шифруется/дешифруется с помощью секретного ключа Алисы

Асимметричные ключи

DA

Закрытый ключ Алисы (аналогично и в случае DB и т.д.)

EA

Открытый ключ Алисы (аналогично и в случае EB и т.д.)

DA(M)

Сообщение M шифруется/дешифруется с помощью закрытого ключа Алисы

EA(M)

Сообщение M шифруется/дешифруется с помощью открытого ключа Алисы

Профиль сообщения

MD(P)

Профиль сообщения для открытого текста P

Илл. 8.20. Алиса хочет отправить сообщение своему банковскому менеджеру: расшифровка ключей и символов

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

Илл. 8.21. Цифровая подпись BB

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