#cryptography #rsa
#криптография #rsa
Вопрос:
По-видимому, альтернативным методом (по сравнению с простым использованием расширенного алгоритма Евклида) получения показателя для расшифровки является выполнение d = e **(phi(phi(n))-1) mod(phi (n)). Почему это работает?
Ответ №1:
Общее требование для правильной работы операции RSA заключается в том, что e*d = 1 mod X , где X обычно (p-1)*(q-1) .
В этом случае X является phi(n) , e является e и d является e^[phi(phi(n))-1] = e^[phi(X)-1] .
Обратите внимание, что e*d mod X равно e*e^[phi(X)-1] mod X = e^phi(X) mod X .
Теорема Эйлера утверждает, что a^phi(X) = 1 mod X для любого a , которое является относительно простым для X , таким образом, выполняется требование.
Комментарии:
1. Все верно, за исключением того, что X не является p * q . X равно (p-1) *(q-1), где n = pq, а p и q оба являются простыми.