Алгоритм RSA

Алгоритм RSA предложили в 1977г. три автора Р. Райвест (Rivest), А. Шамир (Shamir) и А. Адлеман (Adleman). Алгоритм получил свое название по первым буквам фамилий его авторов. Алгоритм RSA стал первым полноценным алгоритмом с открытым ключом, который может работать как в режиме шифрования данных, так и в режиме электронной цифровой подписи.

Надежность алгоритма основывается на трудности факторизации больших чисел и трудности вычисления дискретных логарифмов.

В криптосистеме RSA открытый ключ К_В, секретный ключ k_B, сообщение М и криптограмма С принадлежат множеству целых чисел

Z_N={0,1,2,...,N-1},

где N - модуль: N = P*Q.

Здесь Р и Q - случайные большие простые числа. Для обеспечения максимальной безопасности выбирают Р и Q равной длины и хранят в секрете.

Множество Z_N с операциями сложения и умножения по модулю N образует арифметику по модулю N.

Открытый ключ К_В выбирают случайным образом так, чтобы выполнялись условия:

,

,

где - функция Эйлера.

Функция Эйлера указывает количество положительных целых чисел в интервале от 1 до N, которые взаимно просты с N.

Второе из указанных выше условий означает, что открытый ключ К_В и функция Эйлера должны быть взаимно простыми.

Далее, используя расширенный алгоритм Евклида, вычисляют секретный ключ k_B, такой, что

k_B * К_B = 1 (mod()

или

k_B=K_B^-1(mod(P-1)(Q-1)).

Это можно осуществить, так как получатель В знает пару простых чисел (P,Q) и может легко найти .

Открытый ключ К_B используют для шифрования данных, а секретный ключ k_B - для расшифрования. Преобразование шифрования определяет криптограмму С через пару (открытый ключ К_B, сообщение М) в соответствии со следующей формулой:

,

В качестве алгоритма быстрого вычисления значения С используют ряд последовательных возведений в квадрат целого М и умножений на М с приведением по модулю N.

Обращение функции , т.е. определение значения М по известным значениям С, К_B и N практически неосуществимо при N ≈ 2⁵¹².

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

.

Процесс расшифрования можно записать так:

D_B(Е_B (М)) = М.

Подставляя в D_B(Е_B (М)) = М значения и , получаем:

Или

Таким образом, если криптограмму

возвести в степень k_B, то в результате восстанавливается исходный открытый текст М, так как

. (15)

Таким образом, получатель В, который создает криптосистему, защищает два параметра: секретный ключ k_B и пару чисел (P,Q), произведение которых дает значение модуля N. С другой стороны, получатель В открывает значение модуля N и открытый ключ К_B.

Противнику известны лишь значения К_B и N. Если бы он смог разложить число N на множители Р и Q, то узнал бы "потайной ход" - тройку чисел {Р,Q, k_B}, вычислил значение функции Эйлера

. (16)

и определил значение секретного ключа k_B.

Однако, как уже отмечалось, разложение очень большого N на множители вычислительно неосуществимо (при условии, что длины выбранных Р и Q составляют не менее 100 десятичных знаков).