19.3 RSA

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

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

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

n = p q

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

ed = 1 (mod (p-1)(q-1))

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

d = e-1 mod ((p-1)(q-1))

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

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

ci = mie mod n

Для расшифровки сообщения возьмите каждый зашифрованный блок ci и вычислите mi = cid mod n Так как

cid = (mie)d = mied = mik-1)(q-1)+1 = mimik-1)(q-1) = mi*1 = mi; все (mod n) формула восстанавливает сообщение . Это сведено в 17-й.

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

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

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

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

d e-1 mod ((p-1)(q-1))

Шифрование:

c = me mod n

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

m = cd mod n

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

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

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

Ключ e не должен иметь общих множителей (p-1)(q-1)= 46*70 =3220

Выберем (случайно) e равным 79. В этом случае d = 79-1 mod 3220 = 1019

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

m = 6882326879666683

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

От! = 688

от2 = 232

т3 = 687

от4 = 966 от5 = 668 от6 = 003

Первый блок шифруется как 6 8 879 mod 3337 = 1570 = cl

Выполняя те же операции для последующих блоков, создает шифротекст сообщения : c = 1570 2756 2091 2276 2423 158

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

15701019 mod 3337 = 688 = ot!

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

Аппаратные реализации RSA

Существует много публикаций, затрагивающих тему аппаратных реализаций RSA [1314, 1474, 1456, 1316,

1485, 874, 1222, 87, 1410, 1409, 1343, 998, 367, 1429, 523, 772]. Хорошими обзорными статьями служат [258,

872]. Шифрование RSA выполняется многими микросхемами [1310, 252, 1101, 1317, 874, 69, 737, 594, 1275, 1563, 509, 1223]. Частичный список доступных в настоящее время микросхем RSA, взятый из [150, 258], приведен в 16th. Не все из них доступны в свободной продаже .

Табл. 19-3. Существующие микросхемы RSA

Скорость RSA

Аппаратно RSA примерно в 1000 раз медленнее DES. Скорость работы самой быстрой СБИС-реализации RSA с 512-битовым модулем - 64 килобита в секунду [258]. Существуют также микросхемы, которые выполня-

ют 1024-битовое шифрование RSA. В настоящее время разрабатываются микросхемы, которые, используя 512-битовый модуль, приблизятся к рубежу 1 Мбит/с. Возможно, они появятся в 1995 году. Производители также применяют RSA в интеллектуальных карточках, но эти реализации медленнее .

Программно DES примерно в 100 раз быстрее RSA. Эти числа могут незначительно измениться при измен е-нии технологии, но RSA никогда не достигнет скорости симметричных алгоритмов . В 15-й приведены примеры скоростей программного шифрования RSA [918].

Табл. 19-4.

Скорости RSA для различных длин модулей при 8-битовом открытом ключе (на SPARC II)

Программные Speedups

Шифрование RSA выполняется намного быстрей, если вы правильно выберете значение e. Тремя наиболее частыми вариантами являются 3, 17 и 65537 (216 + 1). (Двоичное представление 65537 содержит только две единицы, поэтому для возведения в степень нужно выполнить только 17 умножений .) X.509 советует 65537 [304], PEM рекомендует 3 [76], а PKCS #l (см. раздел 24.14) - 3 или 65537 [1345]. Не существует никаких проблем безопасности, связанных с использованием в качестве e любого из этих трех значений (при условии, что вы дополняете сообщения случайными числами - см. раздел ниже), даже если одно и то же значение e используется целой группой пользователей .

Операции с закрытым ключом можно ускорить при помощи китайской теоремы от остатках, если вы сохр а-нили значения p и q, а также дополнительные значения: d mod (p - 1), d mod (q - 1) и q-1 mod p [1283, 1276]. Эти дополнительные числа можно легко вычислить по закрытому и открытому ключам .

Безопасность RSA

Безопасность RSA полностью зависит от проблемы разложения на множители больших чисел . Технически, это утверждение о безопасности лживо . Предполагается, что безопасность RSA зависит от проблемы разложения на множители больших чисел. Никогда не было доказано математически, что нужно разложить n на множители, чтобы восстановить m по c и e. Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Однако, если этот новый способ позволит криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел. Я не слишком волнуюсь об этом.

Также можно вскрыть RSA, угадав значение (p-1)(q-1). Это вскрытие не проще разложения n на множители

[1616].

Для сверхскептиков: доказано, что некоторые варианты RSA также сложны, как и разложение на множители (см. раздел 19.5). Загляните также в [361, где показано, что раскрытие даже нескольких битов информации по зашифрованному RSA шифротексту не легче, чем дешифрирование всего сообщения .

Самым очевидным средством вскрытия является разложение n на множители. Любой противник сможет получить открытый ключ e и модуль n. Чтобы найти ключ дешифрирования d, противник должен разложить n на множители. Современное состояние технологии разложения на множители рассматривалось в разделе 11.4. В настоящее время передним краем этой технологии является число, содержащее 129 десятичных цифр . Значит, n должно быть больше этого значения. Рекомендации по выбору длины открытого ключа приведены в разделе

Конечно, криптоаналитик может перебирать все возможные d, пока он не подберет правильное значение . Но такое вскрытие грубой силой даже менее эффективно, чем попытка разложить n на множители.

Время от времени появляются заявления о том, что найден простой способ вскрытия RSA, но пока ни одно из подобных заявлений не подтвердилось . Например, в 1993 году в черновике статьи Вильяма Пейна ( William Payne) был предложен метод, основанный на малой теореме Ферма [1234]. К сожалению, этот метод оказался медленнее разложения на множители

Существует еще один повод для беспокойства. Большинство общепринятых алгоритмов вычисления простых чисел p и q вероятностны, что произойдет, если p или q окажется составным? Ну, во первых, можно свести вероятность такого события до нужного минимума . И даже если это произойдет, скорее всего такое событие будет