Общая структура алгоритма

В целом процесс шифрования и расшифрования выглядит следующим образом:

Пусть мы имеем некое сообщение, которые мы хотим зашифровать. Представим его числом $m$

$c = m^e \pmod n$ - шифрование сообщения $m$

$m = c^d \pmod n$ - расшифрование сообщения $c$

Тут пара чисел $(e, n)$ является открытым ключем и не является секретом, может передаваться по скомпрометированному каналу. Можно хоть нарисовать их на асфальте центра города. А пара $(d, n)$ - секретная часть. Число $d$ нужно надежно хранить, например, чтобы он хранился в памяти компьютера и никогда не покидал его пределы.

Эти ключи связаны особым образом:

Возьмем два больших простых числа $p$, $q$ Вычислим $n = p·q$

Вычислим функцию Эйлера $\phi = (p - 1)·(q - 1)$

Выберем произвольную экспоненту $e$ взаимно простую c $n$

Вычислим число $d$ обратное к числу $e$ по модулю $\phi$

Наше сообщение $m$ должно быть меньше $n$.

Чтобы прочитать сообщение, злоумышленнику нужно разложить число $n$ на его составляющие $p$, $q$. На текущий момент, используют $n$, которое занимают 1024 бита и более. Например, для числа из 2048 бит его десятичная запись будет составлять примерно 600 знаков! Это невероятно огромное число. Современным компьютерам нужны годы, столетия чтобы разложить его на множители.