Криптосистеме RSA

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

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

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

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

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

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

1< К_в £ j (N), НОД (К_в, j (N)) =1.

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

k_в º К_в^–1 (mod j (N)).

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

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

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

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

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

C_i = (mod N)

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

С₁, С₂, С₃,..., C_i,...

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

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

С₁, С₂, С₃,..., C_i,...,

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

М_i = (mod N).

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