Описание алгоритма RSA

В 1978 г. появилась работа, в которой РонРайвест (RonRivest), Ади Шамир (AdiShamir) и Лен Адлеман (LenAdleman) предложили алгоритм с открытым ключом. Схема Райвеста–Шамира–Адлемана (RSA) получила широкое распространение.

Опишем процесс шифрования. Исходный текст должен быть переведен в числовую форму, этот метод считается известным. В результате этого текст представляется в виде одного большого числа. Затем полученное число разбивается на части (блоки) так, чтобы каждая из них была числом в промежутке [0, N – 1] (о выборе N — см. ниже). Процесс шифрования одинаков для каждого блока. Поэтому мы можем считать, что блок исходного текста представлен числом x, 0 £ x £ N -1.

Каждый абонент вырабатывает свою пару ключей. Для этого он генерирует два больших простых числа p и q, вычисляет произведение N = p · q. Затем он вырабатывает случайное число e, взаимно простое со значением функции Эйлера от числа N, j (N)=(p -1)·(q -1) и находит число d из условия e ∙ d º 1(mod φ (N)). Так как (e, φ (N))=1, то такое число d существует и оно единственно.

Пару (N, e) он объявляет открытым ключом и помещает в открытый доступ. Пара (N, d) является секретным ключом. Для расшифрования достаточно знать секретный ключ.

Числа p, q, φ (N) в дальнейшем не нужны, поэтому их можно уничтожить.

Пользователь A, отправляющий сообщение x абоненту B, выбирает из открытого каталога пару (N, e) абонента B и вычисляет шифрованное сообщение y = x^e (mod N).

Чтобы получить исходный текст, абонент B вычисляет y^d (mod N). Так как e ∙ d º 1(mod φ (N)), т. е. e ∙ d = φ (N)· k +1, где k – целоечисло, то применяя теорему Эйлера, получим: следующее соотношение: .

Пример 1. Пусть p = 7, q = 17. Тогда N = 7∙ 17 = 119, φ (N)=96.

Выбираем значение е: e < 96, НОД (e, 96) =1.

Пусть в нашем случае e = 5.

Находим d: d =1/ e (mod 96).

Получаем d = 77, так как 77∙ 5 = 4∙ 96 + 1. Открытый ключ (119, 5), личный ключ (119, 77).

Пусть х = 19. Для зашифрования число 19 возводим в 5-ю степень по модулю 119, тогда имеем 195 = 2 476 099 и остаток от деления 2 476 099 на 119 равен 66. Итак, y = 195 mod 119 = 66.

Прирасшифрованииполучим x =667mod119=19.

Как шифрование, так и расшифрование в RSA предполагают использование операции возведения целого числа в целую степень по модулю N. Если возведение в степень выполнять непосредственно с целыми числами и только потом проводить сравнение по модулю N, то промежуточные значения окажутся огромными. Здесь можно воспользоваться свойствами арифметики в классах вычетов (a mod N)·(b mod N) mod N =(a·b) mod N.

Таким образом, можно рассмотреть промежуточные результаты по модулю N. Это делает вычисления практически выполнимыми.