Для RSA, как мне вычислить секретный показатель?

Question

Для RSA, как мне вычислить секретный показатель?

Учитывая два простых числа p и q, phi=(p-1)(q-1) и общедоступный показатель степени (0x10001), как мне получить секретный показатель степени 'd'?

Я читал, что мне нужно сделать: д = е^-1 мод фи с использованием модульная инверсия и евклидово уравнение но я не могу понять, как приведенная выше формула соответствует либо а^-1 ≡ х мод м формула на вики-странице модульной инверсии или как она отображается в евклидовом уравнении НОД.

Может кто-нибудь помочь, пожалуйста, ура

Answer 1

Вы можете использовать расширенный алгоритм Евклида решить для d в конгруэнтности

de = 1 mod phi(m)

Для шифрования RSA: e это ключ шифрования, d является ключом дешифрования, а шифрование и дешифрование выполняются с помощью мода экспонентации m.Если вы зашифруете сообщение aс ключом e, а затем расшифровать его с помощью ключа d, вы вычисляете (a^е)^д = а^де мод m.Но с тех пор de = 1 mod phi(m), Теорема Эйлера о тотенте говорит нам, что^де совпадает с¹ mod m -- другими словами, вы возвращаете оригинал a.

Не существует известных эффективных способов получения ключа дешифрования. d Зная только ключ шифрования e и модуль m, не зная факторизации m = pq, Считается, что шифрование RSA в безопасности.