Патенты

Оригинальный алгоритм Меркла-Хеллмана запатентован в Соединенных Штатах [720] и в остальном мире (см. 18th). Public Key Partners (PKP) получила лицензию на патент вместе с другими патентами криптографии с открытыми ключами (см. раздел 25.5). Время действия патента США истечет 19 августа 1997 года.

Табл. 19-1. Иностранные патенты на алгоритм рюкзака Меркла-Хеллмана

Страна	Номер	Дата получения
Бельгия		5 апреля 1979 года
Нидерланды		10 апреля 1979 года
Великобритания		2 мая 1979 года
Германия		10 мая 1979 года
Швеция		14 мая 1979 года
Франция		8 июня 1979 года
Германия		3 января 1982 года
Германия		15 июля 1982 года
Канада		20 июля 1982 года
Великобритания	2.006580	18 августа 1982 года
Швейцария		14 января 1983 года
Италия		28 сентября 1985 года

19.3 RSA

Вскоре после алгоритма рюкзака Меркла появился первый полноценный алгоритм с открытым ключом, ко­торый можно использовать для шифрования и цифровых подписей: RSA [1328, 1329]. Из всех предложенных за эти годы алгоритмов с открытыми ключами RSA проще всего понять и реализовать. (Мартин Гарднер (Martin Gardner) опубликовал раннее описание алгоритма в своей колонке "Математические игры" в Scientific American [599].) Он также является самым популярным. Названный в честь трех изобретателей - Рона Ривеста (Ron Rivest), Ади Шамира (Adi Shamir) и Леонарда Эдлмана (Leonard Adleman) - этот алгоритм многие годы проти­востоит интенсивному криптоанализу. Хотя криптоанализ ни доказал, ни опроверг безопасность RSA, он, по сути, обосновывает уровень доверия к алгоритму.

Безопасность RSA основана на трудности разложения на множители больших чисел. Открытый и закрытый ключи являются функциями двух больших (100 - 200 разрядов или даже больше) простых чисел. Предполагает­ся, что восстановление открытого текста по шифротексту и открытому ключу эквивалентно разложению на множители двух больших чисел.

Для генерации двух ключей используются два больших случайных простых числа, р и q. Для максимальной безопасности выбирайте р и q равной длины. Рассчитывается произведение:

п — р q

Затем случайным образом выбирается ключ шифрования е, такой что е и (p-l)(q-l) являются взаимно про­стыми числами. Наконец расширенный алгоритм Эвклида используется для вычисления ключа дешифриров а-ния d, такого что

efi?=l(mod (p-l)for-l))

Другими словами

rf= e-¹ mod ((p-l)(_?-l))

Заметим, что d и п также взаимно простые числа. Числа е и п - это открытый ключ, а число d - закрытый. Два простых числам и q больше не нужны. Они должны быть отброшены, но не должны быть раскрыты.

Для шифрования сообщения от оно сначала разбивается на цифровые блоки, меньшие п (для двоичных дан­ных выбирается самая большая степень числа 2, меньшая и). То есть, если/; и q - 100-разрядные простые числа, то п будет содержать около 200 разрядов, и каждый блок сообщения от, должен быть около 200 разрядов в длину. (Если нужно зашифровать фиксированное число блоков, их можно дополнить несколькими нулями ел е-ва, чтобы гарантировать, что блоки всегда будут меньше п. Зашифрованное сообщение с будет состоять из бло­ков с, той же самой длины. Формула шифрования выглядит так

с, = от,^е mod n

Для расшифровки сообщения возьмите каждый зашифрованный блок с, и вычислите

от,■ = с? mod n

Так как

с? = (от,У = m?d = OT,^-1)^fe-1)+1 = от,от,*^№1) = от,*1 = от,; все (mod n)

формула восстанавливает сообщение. Это сведено в 17-й.

Табл. 19-2. Шифрование RSA

Открытый ключ:

п произведение двух простых чисел puq (puq должны храниться в секрете) е число, взаимно простое с (р- 1 )(д- 1)

Закрытый ключ:

d e^lmo&{(p-\){q-\))

Шифрование:

c = m^e mod n

Дешифрирование:

m = c^d mod n

Точно также сообщение может быть зашифровано с помощью d, а зашифровано с помощью е, возможен любой выбор. Я уберегу вас от теории чисел, доказывающей, почему этот алгоритм работает. В большинстве

книг по криптографии этот вопрос подробно рассмотрен.

Короткий пример возможно поможет пояснить работу алгоритма. Если/; = 47 и q = 71, то

и = pq = 3337

Ключ е не должен иметь общих множителей

(р-1)(д-1)= 46*70 =3220

Выберем (случайно) е равным 79. В этом случае rf = 79"¹ mod 3220 = 1019

При вычислении этого числа использован расширенный алгоритм Эвклида (см. раздел 11.3). Опубликуем е и п, сохранив в секрете d. Отбросим/; и q. Для шифрования сообщения

т = 6882326879666683

сначала разделим его на маленькие блоки. Для нашего случая подойдут трехбуквенные блоки. Сообщение разбивается на шесть блоков от,:

От! = 688

от₂ = 232

от₃ = 687

от₄ = 966

от₅ = 668

от₆ = 003

Первый блок шифруется как 688⁷⁹ mod 3337 = 1570 = с,

Выполняя те же операции для последующих блоков, создает шифротекст сообщения:

с = 1570 2756 2091 2276 2423 158

Для дешифрирование нужно выполнить такое же возведение в степень, используя ключ дешифрирования 1019:

1570¹⁰¹⁹ mod 3337 = 688 = от:

Аналогично восстанавливается оставшаяся часть сообщения.