RSAの場合、秘密指数を計算するにはどうすればよいですか。

Question

RSAの場合、秘密指数を計算する方法は？

PとQの2つのプリム、およびPhi=（P-1）（Q-1）、および公共の指数（0x10001）、秘密の指数 'd'を手に入れるのはどうやって

私は私がしなければならないことを読みました： d= E ^{-1 mod phi} モジュラインバイスとユークリッド方程式上記の式が、Modular Inversion Wikiページの ^{-1 x mod m} 式、またはそれがユークリッドGCD方程式にどのようにマッピングするかをどのようにマッピングするかを理解することはできません。

誰かが助けてくれることができます、歓声

Answer 1

extended Euclidean Algorithm は合同でdを解くために解決する

de = 1 mod phi(m)

.

RSA暗号化の場合、eは暗号化キー、dは復号化キーと暗号化です。 そして復号化はどちらも、指数MOD mによって実行されます。メッセージaを暗号化した場合 キーeを使用して、キーdを使用して復号化して、（ ^{E ） d = de mod mを算出します。だが de = 1 mod phi(m)、 eulerのTotient Theorem は、 de が合同であることを伝えています 1 mod m - すなわち、元のaを取り戻します。}

復号化キーdを認識するための既知の効率的な方法はありません。 因数分解のeを知らずに、暗号化キーmとModulus m = pqであるため、 RSA暗号化は安全であると考えられています。