Алгоритм для быстрого нахождения закрытого ключа RSA?

Question

[nnikolyaa]

Здравствуйте
Решил заглянуть в криптографию, узнать новое. Посмотрел статьи, работы по RSA. Решил на практике посмотреть, но тут начались проблемы...

func_eiler = (P-1)*(Q-1)
ekspon = random.randint(1, func_eiler)
d=0
while (ekspon*d)%func_eiler!=1:
    d+=1

Всё идёт прекрасно, но при начале поиска d происходит жёсткий просад по скорости. Весь скрипт просто спит. Покажите пожалуйста алгоритм для быстрого нахождения d

Answer 1

[Lynn «Кофеман»]

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

Во-первых, ekspon должен быть не просто рандомным, а взаимно простым с func_eiler. Практически всегда его берут равным 65537 и не заморачиваются случайным выбором.

Во-вторых,

число d называется секретной экспонентой; обычно оно вычисляется при помощи расширенного алгоритма Евклида

Comments

[nnikolyaa]

Благодарю