Пользователь

, отправляющий сообщение

, шифрует его следующим образом:

. Этот текст получает только пользователь

.
Чтобы восстановить исходный текст,

поступает следующим образом:
1. Находит число

, такое, что

и

.Это сравнение разрешимо единственным образом, поскольку

.
Для решения сравнения

пользователь

должен вычислить

.

Любой другой пользователь, который знает только

, вынужден находить

и

, т.е. разлагать число

на простые множители, а эта задача при больших

и

имеет большую вычислительную сложность. Далее пользователь

вычисляет

.

Алгоритм применения RSA.
1. Отправитель выбирает два больших простых числа

и

. Вычисляет два произведения

и

2. Затем он выбирает случайное число

(целое), взаимно простое с

, и вычисляет

, удовлетворяющее условию

.
3. После этого он публикует

и

как свой открытый ключ шифрования, сохраняя

как закрытый ключ.
4. Если

– сообщение, длина которого, определяемая по значению выражаемого им целого числа, должна быть в интервале

, то она превратится в криптограмму возведением в степень

по модулю

и отправляется получателю в следующем виде

.
5. Получатель сообщения расшифровывает его. Возводя в степень

по модулю

, так как

Пояснение.
Таким образом, открытым ключом служит пара чисел

и

, а секретным ключом число

. Крипкостойкость системы RSA основана на том, что

не может быть просто вычислена без значения

и

, нахождение этих сомножителей из

достаточно трудоемко.
Электронная подпись (цифровая подпись).
Если

планирует подписывать документ Ц.П., то он должен выбрать параметры RSA.

выбирает два простых числа

и

, вычисляет

затем выбирает число

,взаимно простое с

, и вычисляет

, далее публикует числа

и

и хранит в секрете

. Числа

– более не понадобятся.
Пусть

хочет подписать сообщение

. Тогда

вычисляет хеш-функцию

, которая ставит в соответствие сообщению

число

.
Практически невозможно изменить основной текст

, не изменив

. Поэтому

достаточно снабдить только число

подписью, и эта подпись будет относиться ко всему сообщению

.
Далее

вычисляет число

, т.е. она возводит число

в свою секретную степень. Число

– цифровая подпись.

– вид сообщения с подписью.
Теперь каждый, кто знает открытые параметры

, т.е.

и

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

, т.е. число

, и проверить равенство

.
/*Пример*/ Электронная подпись RSA.

Пусть

(алгоритм Евклида).

(допущение)