Основные этапы реализации алгоритма

1. Для генерации двух ключей пользователь А выбирает два больших случайных простых числа p и q. Для максимальной безопасности p и q должны иметь равную длину. Два простых числа p и q больше не нужны они могут быть отброшены, но не должны быть раскрыты. Рассчитываются их произведение n=pq и значение M = (p-1)(q-1).

2. Затем он выбирает случайное целое число е, взаимно простое M.

3. Наконец, с помощью расширенного алгоритма Евклида пользователь А вычисляет ключ расшифрования d, такой что:

Другими словами:

Параметры d и n так же взаимно простые числа.

4. После это пользователь А публикует числа е и n как свой открытый ключ, сохраняя число d, как закрытый (сектретный) ключ.

5. Пользователь В перед зашифрованием сообщения P сначала разбивает его на цифровые блоки P_i, размерами меньше n (для двоичных данных выбирается самая большая степень числа два, меньшая n). Зашифрованное сообщение C будет состоять из блоков C_i той же самой длины.

6. Затем пользователь В вычисляет все и пересылает пользователю А.

7. Пользователь А, получив щифртекст дешифрует его, вычисляя .

Стойкость алгоритма RSA полностью зависит от трудоемкости решения проблемы разложение на множители больших чисел. С технической точки зрения это не корректно. Утверждение, что безопасность RSA зависит от проблемы разложения на множители больших чисел, является гипотетическим. Никто и никогда не доказал математически, что для восстановления P по C и е нужно разложить п на множители Понятно, что может быть открыт совсем иной способ криптоанализа RSA. Но если этот новый способ даст возможность криптоаналитику получить d, он также может быть использован для разложения на множители больших чисел.

Самым очевидным средством вскрытия является разложение п на множители. Любой противник сможет получить открытый ключ е и модуль п. Чтобы найти ключ расшифрования d, противник должен разложить п на множители. Конечно, криптоаналитик может перебирать все возможные d до тех пор, пока не найдет правильное значение. Но такой лобовой взлом менее эффективен, чем даже разложить п на множители.