Процедуры шифрования и расшифрования
в криптосистеме RSA
Предположим, что пользователь А хочет передать пользователю В сообщение в зашифрованном виде, используя криптосистему RSA. В таком случае пользователь А выступает в роли отправителя сообщения, а пользователь В - в роли получателя. Как отмечалось выше, криптосистему RSA должен сформировать получатель сообщения, т.е. пользователь В. Рассмотрим последовательность действий пользователя В и пользователя А.
1. Пользователь В выбирает два произвольных больших простых числа Р и Q.
2. Пользователь В вычисляет значение модуля N=Р*Q.
3. Пользователь В вычисляет функцию Эйлера
и выбирает случайным образом значение открытого ключа КB с учетом выполнения условий:
4. Пользователь В вычисляет значение секретного ключа kB, используя расширенный алгоритм Евклида при решении сравнения
5. Пользователь В пересылает пользователю А пару чисел (N, КB) по незащищенному каналу.
Если пользователь А хочет передать пользователю В сообщение М, он выполняет следующие шаги.
6. Пользователь А разбивает исходный открытый текст М на блоки, каждый из которых может быть представлен в виде числа
Мi=0,1,2,...,N-1.
7. Пользователь А шифрует текст, представленный в виде последовательности чисел М, по формуле
и отправляет криптограмму
C1, С2, С3,...,Ci, ...
пользователю В.
8. Пользователь В расшифровывает принятую криптограмму
C1, С2, С3,...,Ci, ...,
используя секретный ключ kB, по формуле
.
В результате будет получена последовательность чисел Mi, которые представляют собой исходное сообщение М. Чтобы алгоритм RSA имел практическую ценность, необходимо иметь возможность без существенных затрат генерировать большие простые числа, уметь оперативно вычислять значения ключей КB и kB.
Пример. Шифрование сообщения CAB. Для простоты вычислений будут использоваться небольшие числа. На практике применяются очень большие числа.
Действия пользователя В.
1. Выбирает Р=3 и Q=11.
2. Вычисляет модуль N=P*Q=3*11=33.
3. Вычисляет значение функции Эйлера для N=33:
Выбирает в качестве открытого ключа КB произвольное число с учетом выполнения условий:
Пусть КB=7.
4. Вычисляет значение секретного ключа kB, используя расширенный алгоритм Евклида (см. приложение) при решении сравнения
КB є T1(mod20).
Решение дает kB=3.
5. Пересылает пользователю А пару чисел (N= 3, kB=7).
Действия пользователя А.
6. Представляет шифруемое сообщение как последовательность целых чисел в диапазоне 0 ... 32. Пусть буква А представляется как число 1, буква В - как число 2, буква С - как число 3. Тогда сообщение CAB можно представить как последовательность чисел 312, т.е. M1 = 3, M2 = 1, M3 = 2.
7. Шифрует текст, представленный в виде последовательности чисел M1, M2 и M3, используя ключ КB = 7 и N = 33, по формуле
,
получает
Отправляет пользователю В криптограмму
C1,C2,C3 =9, 1, 29.
Действия пользователя В.
8. Расшифровывает принятую криптограмму C1,C2,C3, используя секретный ключ kB=3, по формуле
получает
Таким образом, восстановлено исходное сообщение: CAB - 3 1 2.
