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

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

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

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

Ответы

Ответ 1

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

de = 1 mod phi(m)

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

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