2.15. Алгоритм rsa

Единственная загвоздка состоит в том, чтобы найти алгоритмы, удовлетворяющие всем трем требованиям. Поскольку преимущества шифрования с открытым ключом очевидны, многие исследователи неустанно работали над созданием подобных алгоритмов, и некоторые из них уже опубликованы. Один хороший метод был разработан группой исследователей Массачусетского технологического института (Rivest и др., 1978). Он назван по начальным буквам фамилий трех разработчиков: RSA (Rivest, Shamir, Adleman). Этот метод вот уже четверть века выдерживает попытки взлома и считается очень прочным. На его основе построены многие практические системы безопасности. Главный недостаток RSA заключается в том, что для обеспечения достаточного уровня защищенности требуется ключ длиной, по крайней мере, 1024 бита (против 128 бит в алгоритмах с симметричными ключами). Из-за этого алгоритм работает довольно медленно.

В основе метода RSA лежат некоторые принципы теории чисел. Опишем в общих чертах, как пользоваться этим методом.

1. Выберем два больших простых числа р и q (обычно длиной 1024 бита).

2. Сосчитаем n=p*q и z = (p- l)(q - 1).

3. Выберем число d, являющееся взаимно простым с числом z.

4. Найдем такое число е, что остаток от деления произведения e*d на число z равен 1.

Вычислив заранее эти параметры, можно начинать шифрование. Сначала разобьем весь открытый текст (рассматриваемый в качестве битовой строки) на блоки так, чтобы каждое сообщение Р попадало в интервал 0 <= Р < n. Это несложно сделать, если разбить открытый текст на блоки по k бит, где k — максимальное целое число, для которого 2k < n.

Чтобы зашифровать сообщение Р, вычислим С = Р (mod n). Чтобы расшифровать С, сосчитаем Р = Cd (mod n). Можно доказать, что для всех значений Р в указанном диапазоне функции шифрования и дешифрации являются взаимно обратными. Чтобы выполнить шифрование, нужны е и n. Для дешифрации требуются d и n. Таким образом, открытый ключ состоит из пары (е, n), а закрытый ключ — из пары (d, n).

Надежность метода обеспечивается сложностью нахождения множителей больших чисел. Если бы криптоаналитик мог разложить на множители (открытое) число n, он мог бы тогда найти значения р и q, а следовательно, и число z. После этого числа e и d можно найти при помощи алгоритма Евклида. К счастью, математики пытались решить проблему разложения на множители больших чисел по меньшей мере 300 лет, и накопленный опыт позволяет предположить, что эта проблема чрезвычайно трудна.

Ривест с коллегами утверждает, что для разложения на множители числа из 500 цифр необходимо 1025 лет, если применять грубую силу. Предполагается, что задействованы лучший известный алгоритм и компьютер, выполняющий одну инструкцию за 1 мкс. Даже при сохранении экспоненциального роста скоростей компьютеров потребуются века, чтобы найти множители числа из 500 цифр, а к этому времени наши потомки могут просто выбрать еще большие р и q.

Тривиальный учебный пример работы алгоритма RSA приведен на рис. 33. Для этого примера мы выбрали р = 3, a q=11, что дает значения n = 33, a z = 20. Число d можно выбрать равным 7, так как числа 20 и 7 не имеют общих делителей.

При таком выборе значение е можно найти, решив уравнение 7e = 1 (mod 20), откуда следует, что е = 3. Зашифрованный текст С получается из открытого сообщения Р по формуле С = Р³ (mod 33). Получатель расшифровывает сообщение по формуле Р= С7 (mod 33). В качестве примера на рис. 33 показано шифрование слова «SUZANNE».

Символ	Число		P3		P3 mod 33		C7		C7 mod 33	Символ
S	19		6859		28		13492928512		19	S
U	21		9261		21		1801088541		21	U
Z	26		17576		20		1280000000		26	Z
A	1		1		1		1		1	A
N	14		2744		5		78125		14	N
N	14		2744		5		78125		14	N
E	5		125		26		8031810176		5	E

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

Поскольку выбранные для данного примера простые числа так малы, Р должно быть менее 33, поэтому каждый блок открытого текста может содержать лишь одну букву. В результате получается моноалфавитный подстановочный шифр, что не очень впечатляет. Если бы мы вместо этого выбрали числа р и q порядка 2⁵¹², тогда число n было бы около 2¹⁰²⁴. В этом случае каждый блок мог бы содержать до 1024 бит, или 128 восьмиразрядных символов, против 8 символов шифра DES или 16 AES.

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