Алгоритм шифрования RSA

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

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

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

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

где N — модуль:

N = P * Q.

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

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

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

1 < K_B £ j (N), HOД (K_B, j (N)) = 1,

j (N) = (P – 1) (Q – 1),

где j (N) — функция Эйлера.

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

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

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

k_B * K_B º 1 (mod j (N))

или

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

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

Открытый ключ K_B используют для шифрования данных, а секретный ключ k_B — для расшифрования.

Преобразование шифрования определяет криптограмму С через пару (открытый ключ K_B, сообщение М) в соответствии со следующей формулой:

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

Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В — в роли получателя. Криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В. Рассмотрим последовательность действий пользователя В и пользователя А.

Пользователь В выбирает два произвольно больших простых числа P и Q.

Пользователь В вычисляет значение модуля N = P * Q.

Пользователь В вычисляет функцию Эйлера

j (N) = (P – 1) (Q – 1)

и выбирает случайным образом значение открытого ключа K_B с учетом выполненных условий:

1 < K_B £ j (N), HOД (K_B, j (N)) = 1.

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

k_B = K_B^-1 (mod j (N)).

Пользователь В пересылает пользователю А пару чисел (N, K_B) по незащищенному каналу.

Если пользователь А хочет передать пользователю В сообщение М, он выполняет следующие шаги.

Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в виде числа

М_i = 0, 1, 2, …, N – 1.

Пользователь А шифрует текст, представленный в виде последовательности чисел M_i по формуле

и отправляет криптограмму

С₁, С₂, С₃ … С_i, …

пользователю В.

Пользователь В расшифровует принятую криптограмму

С₁, С₂, С₃ … С_i, …

используя секретный ключ k_B по формуле

В результате будет получена последовательность чисел M_i, которые представляют собой исходное сообщение М. Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей k_B и K_B.