Процедуры шифрования и расшифрования в криптосистеме RSA

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

1. Пользователь В выбирает два произвольных больших простых числа Р и Q.
2. Пользователь В вычисляет значение модуля N=Р*Q.
3. Пользователь В вычисляет функцию Эйлера

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

.

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

.

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

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

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

М_i=0,1,2,...,N-1.

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

С_i=M_i^K_B(mod N)

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

C1, С2, С3,...,Ci,...

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

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

C1, С2, С3,...,Ci,...,

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

M_i=C_i^k_B(mod N).

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

Пример - Шифрование сообщения CAB

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

Действия пользователя В.

1. Выбирает Р=3 и Q=11.
2. Вычисляет модуль N=P*Q=3*11=33.
3. Вычисляет значение функции Эйлера для N=33:

1. Выбирает в качестве открытого ключа КB произвольное число с учетом выполнения условий:

.

Пусть К_B=7.

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

k_{B =} 7^-1 (mod 20).

Решение дает k_B=3.

1. Пересылает пользователю А пару чисел (N= 33, K_B=7).

Действия пользователя А

1. Представляет шифруемое сообщение как последовательность целых чисел в диапазоне 0-32. Пусть буква А представляется как число 1, буква В - как число 2, буква С - как число 3. Тогда сообщение CAB можно представить как последовательность чисел 312, т.е. M₁ = 3, M₂ = 1, M₃ = 2.
2. Шифрует текст, представленный в виде последовательности чисел M₁, M₂ и M₃, используя ключ К_B = 7 и N = 33, по формуле

C_i = M_i^K_B (mod 33) = M_i⁷ (mod 33),

получает

,

1. Отправляет пользователю В криптограмму

C₁,C₂,C₃ =9, 1, 29.

Действия пользователя В

1. Расшифровывает принятую криптограмму C₁,C₂,C₃, используя секретный ключ k_B=3, по формуле

M_i = C_i^k_B (mod 33) = C_i³ (mod 33).

получает

.

Таким образом, восстановлено исходное сообщение CAB - 3 1 2.