Алгоритм создания открытого и секретного ключей

Алгоритм создания открытого и секретного ключей (RSA)

Наша цель - это формирование 3-ёх чисел (далее их общепринятые названия):

1. модуля $\Large n $
2. открытой экспоненты $\Large e$
3. и закрытой экспопнеты $\Large d$

Из трёх этих чисел открытый из закрытый ключ образуются путём использования:

1. пары $\Large\left\{ e, n \right\} $ - в качестве открытого ключа
2. пары $\left\{ d, n \right\}$ - в качестве закрытого ключа

Друзья, сосредоточьтесь и внимательно прочитайте следующие пункты:

1. для начала мы берём два случайных простых числа ($\Large p$ и $\Large q$) стандартного размера (например 1024 бит - то есть - достаточно большие)
2. затем вычисляем функцию Эйлера от числа n, таким образом:
   $\Large \varphi(n) = (p-1)(q-1)$
   (правая часть здесь рассчитывается моментально а потому из данного уравнения мы можем получить само значение $\Large n$)
3. Далее вы подбираем $\Large e$ - открытую экспоненту , так чтобы:
   • её значение было взаимно простым со значением функции $\Large \varphi(n)$
   • удовлетворяло неравенству: $\Large 1
4. И теперь вычисляем закрытую экспоненту d, значение которой должно соответствовать условию:
   $\Large d\cdot e \equiv 1 \mod {\varphi(n)}$
5. Вот и всё )

Примечания

Как вы только что прочитали - мы искали значение n (модуля) очень так:
$\Large \varphi(n) = (p-1)(q-1)$
где праву часть рассчитать быстро - в то время как обратный поиск - $\Large p$ и $\Large q$ по заданному $\Large n$ заёмёт очень много времени - на этом и основана защита RSA, так как противник не будет знать исходных $\Large p$ и $\Large q$ и ему придётся их подбирать