Загадка RSA в исполнении авторов Википедии

[MGM]

Читаем:

Цитата:

RSA-ключи генерируются следующим образом:

1) выбираются два различных случайных простых числа ${\displaystyle p}$ и ${\displaystyle q}$ заданного размера (например, 1024 бита каждое);
2) вычисляется их произведение ${\displaystyle n=p\cdot q}$ которое называется модулем;
3) вычисляется значение функции Эйлера от числа ${\displaystyle n}$:
${\displaystyle \varphi (n)=(p-1)\cdot (q-1)}$;
4) выбирается целое число ${\displaystyle e}({\displaystyle 1<e<\varphi (n)}$, взаимно простое со значением функции ${\displaystyle \varphi (n)}$;
число ${\displaystyle e}$ называется открытой экспонентой (англ. public exponent);
обычно в качестве ${\displaystyle e}$ берут простые числа, содержащие небольшое количество единичных бит в двоичной записи, например,
простые из чисел Ферма: 17, 257 или 65537, так как в этом случае время, необходимое для шифрования с использованием
быстрого возведения в степень, будет меньше;
слишком малые значения ${\displaystyle e}$, например 3, потенциально могут ослабить безопасность схемы RSA;
5) вычисляется число ${\displaystyle d}$, мультипликативно обратное к числу ${\displaystyle e}$ по модулю ${\displaystyle \varphi (n)}$, то есть число, удовлетворяющее сравнению:
${\displaystyle d\cdot e\equiv 1{\pmod {\varphi (n)}}}$
(число ${\displaystyle d}$ называется секретной экспонентой; обычно оно вычисляется при помощи расширенного алгоритма Евклида);
6) пара ${\displaystyle (e,n)}$ публикуется в качестве открытого ключа RSA (англ. RSA public key);
7) пара ${\displaystyle (d,n)}$ играет роль закрытого ключа RSA (англ. RSA private key) и держится в секрете.

..........................................
В чем прикол?
В том, что критерию
${\displaystyle d\cdot e\equiv 1{\pmod {\varphi (n)}}}$

отвечает множество значений ${\displaystyle d}$ ?
И в этом секрет. Если так, то почему такое непонятное объяснение.

PS Я бы уточнил, что ${\displaystyle d}$ не вычисляется, а выбирается из вычисленных возможных значений $k$ в явном уравнении
${\displaystyle d\cdot e = {{k\varphi (n)+1}}}$

[gevaraweb]

MGM в сообщении #1570327 писал(а):

выбирается из вычисленных.

Ну, значит, все-таки вычисляется.
Ну трудность не в этом, а в том, насколько я помню:
Найти p и q по заданному n, т.е. разложить n на простые множители....

[mihaild]

Что вы понимаете под "приколом"? Если "откуда берется стойкость шифра" - как раз потому что (предполагается) что найти $d$, зная только $n$ и $e$ (не зная $p$ и $q$, или, что эквивалентно, $\varphi(n)$), сложно.

MGM в сообщении #1570327 писал(а):

${\displaystyle d\cdot e\equiv 1{\pmod {\varphi (n)}}}$

отвечает множество значений ${\displaystyle d}$ ?

Нет, ровно одно (из меньших $\varphi(n)$).