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

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

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

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

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

f(N) = (Р-1)(Q-1)

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

1<К_B <= f(N), НОД(К_B, f(N)) = 1.

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

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

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

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

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

2. Пользователь А шифрует текст, представленный в виде последовательности чисел М_i по формуле С_i = М_i^Кв (mod N) и отправляет криптограмму С₁, С₂, С₃, ..., С_i, ... пользователю В.

3. Пользователь В расшифровывает . принятую крип­тограмму С₁, С₂, С₃, ..., С_i, ... используя секретный ключ k_B, по формуле М_i = С_i^kв(mod N).

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

Пример. Шифрование сообщения САВ. Для простоты вычислений будут использоваться небольшие числа. На практике применяются очень большие числа.

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

Выбирает Р = 3 и Q = 11.

Вычисляет модуль N = Р*Q = 3*11 = 33.

Вычисляет значение функции Эйлера для N = 33:

f(N) = f(33) = (Р -1 )(Q -1) = 2*10 = 20.

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

1 < К_B <= 20, НОД (K_B,20) = 1.

Пусть К_B= 7.

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

k_B = 7^-1 (mod 20).

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

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

Рассмотрим подробнее, как получено решение k_B=3.

Расчет k_B осуществляется с использованием частного режима работы расширенного алгоритма Евклида, использующего равенство НОД(К_В, f(N))=1.

1. Введем трехмерные векторы u, v, t

u = {0, 1, f(N)}, v = (1, 0, K_B)

2. Если u₃=1, то переход к пункту 4; в противном случае, переход к пункту 3.

3. S=[u₃ / v₃]целая часть; t=u-v*s; u=v; v=t; переход к пункту 2.

Конец, k_B = u₁.

Процесс поиска решения можно задать таблицей.

В результате решения получаем, что k_B=3.