Для RSA, как я вычисляю секретную экспоненту?
Для RSA, как я вычисляю секретную экспоненту?
Данный p и q эти два начала и phi = (p-1) (q-1), и общедоступная экспонента (0x10001), как я получаю секретную экспоненту 'd'?
Я считал, что должен сделать: d = e-1 модификация phi использование модульной инверсии и евклидова уравнения, но я не могу понять, как вышеупомянутая формула отображается или на a-1 ≡ x модификация m формула на модульной инверсии страница Wiki, или на как это отображается на евклидово уравнение GCD.
Может кто-то помогать, аплодисменты
1 ответ
Вы можете использовать расширенный евклидов алгоритм для решения d в конгруэнции
de = 1 mod phi(m)
Для шифрования RSA, e - ключ шифрования, d - ключ дешифрования, и шифрование
и дешифрование выполняются путем экспоненцирования mod m. Если вы зашифруете сообщение a
ключом e, а затем расшифровываете его ключом d, то вычисляете (ae)d = ade mod m. Но
поскольку de = 1 mod phi(m), теорема Эйлера о тотальности говорит нам, что ade конгруэнтно
к a1 mod m - другими словами, вы получаете обратно исходное a.
Не существует эффективных способов получить ключ расшифровки d, зная только ключ шифрования .
ключ шифрования e и модуль m, не зная факторизации m = pq, поэтому
считается, что шифрование RSA безопасно.