Легенда:
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Ну, во-первых, не p, q и e, а на основе n и e 21.09.04 17:54 Число просмотров: 4407
Автор: Heller <Heller> Статус: Elderman
|
> как на основе p, q, e (речь идет об алгоритма RSA) получить > d?
Ну, во-первых, не p, q и e, а на основе n и e.
По определению: n=pq, ф(n)=(p-1)(q-1), de=1 (mod ф(n)), где p!=q - большие простые числа.
Отсюда, разложив на простые множители n получаются p и q, а дальше de=1 (mod ф(n)).
Так как вопрос, имхо, в beginners, разъясню на всякий случай смысл de=1 (mod ф(n)), возможно, проблема именно здесь.
Это тоже самое, что d=(1+kф(n))/e, где k - натуральное число. Вычисляется по алгоритму Евклида (короче перебором). Это не трудоёмко - гораздо труднее разложить на простые множители n (можно годами раскладывать). То есть факторизировать. Хотя есть множество алгоритмов, которые сокращают время факторизации - советую по этому поводу почитать книжку О. В. Василенко "Теоретико-числовые алгоритмы в криптографии". Она даже где-то в глубине МГУ'шного сайта для свободного скачивания в pdf лежит. В общем, Яндекс в помощь..
ЗЫ. Только не совсем понятно, зачем задавать вопросы внутри другого топика, никакого отношения к данной теме не имеющего..
|
|
|