2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.



Начать новую тему Ответить на тему
 
 Загадка RSA в исполнении авторов Википедии
Сообщение17.11.2022, 20:30 
Аватара пользователя


05/06/08
470
Читаем:
Цитата:
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}}}$

 Профиль  
                  
 
 Re: Загадка RSA в исполнении авторов Википедии
Сообщение17.11.2022, 21:10 


15/11/15
916
MGM в сообщении #1570327 писал(а):
выбирается из вычисленных.

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

 Профиль  
                  
 
 Re: Загадка RSA в исполнении авторов Википедии
Сообщение17.11.2022, 21:20 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Что вы понимаете под "приколом"? Если "откуда берется стойкость шифра" - как раз потому что (предполагается) что найти $d$, зная только $n$ и $e$ (не зная $p$ и $q$, или, что эквивалентно, $\varphi(n)$), сложно.
MGM в сообщении #1570327 писал(а):
${\displaystyle d\cdot e\equiv 1{\pmod {\varphi (n)}}}$

отвечает множество значений ${\displaystyle d}$ ?
Нет, ровно одно (из меньших $\varphi(n)$).

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 3 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group