Для RSA, как мне вычислить секретный показатель?
-
13-09-2020 - |
Вопрос
Для RSA, как мне вычислить секретный показатель?
Учитывая два простых числа p и q, phi=(p-1)(q-1) и общедоступный показатель степени (0x10001), как мне получить секретный показатель степени 'd'?
Я читал, что мне нужно сделать: д = е-1 мод фи с использованием модульная инверсия и евклидово уравнение но я не могу понять, как приведенная выше формула соответствует либо а-1 ≡ х мод м формула на вики-странице модульной инверсии или как она отображается в евклидовом уравнении НОД.
Может кто-нибудь помочь, пожалуйста, ура
Решение
Вы можете использовать расширенный алгоритм Евклида решить для d
в конгруэнтности
de = 1 mod phi(m)
Для шифрования RSA: e
это ключ шифрования, d
является ключом дешифрования, а шифрование и дешифрование выполняются с помощью мода экспонентации m
.Если вы зашифруете сообщение a
с ключом e
, а затем расшифровать его с помощью ключа d
, вы вычисляете (aе)д = аде мод m
.Но с тех пор de = 1 mod phi(m)
, Теорема Эйлера о тотенте говорит нам, чтоде совпадает с1 mod m -- другими словами, вы возвращаете оригинал a
.
Не существует известных эффективных способов получения ключа дешифрования. d
Зная только ключ шифрования e
и модуль m
, не зная факторизации m = pq
, Считается, что шифрование RSA в безопасности.