Как рассчитать секретный показатель для RSA?

Question

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

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

Я читал, что мне нужно сделать: d = e ^-1 mod phi используя модульная инверсия и евклидово уравнение , но я не могу понять, как приведенная выше формула отображается либо в a ^-1 ≡ x mod m в модульной формулевики-страница инверсии, или как она отображается в евклидовом уравнении GCD.

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

Answer 1

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

de = 1 mod phi(m)

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

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