14

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

pとqに2つの素数、phi =（p-1）（q-1）、および公開指数（0x10001）が与えられた場合、秘密の指数'd'を取得するにはどうすればよいですか？

私は私がしなければならないことを読みました：モジュラー反転とユークリッド方程式を使用してd = e -1 mod phiしかし、上記の式がモジュラー反転wikiページのa - 1≡xmodm式にどのようにマッピングされるか理解できません、またはそれがユークリッドGCD方程式にどのようにマッピングされるか。

誰か助けてくれませんか、乾杯

4

1 に答える 1

19

拡張ユークリッドアルゴリズムdを使用して、合同で解くことができます

de = 1 mod phi(m)

RSA暗号化の場合、eは暗号化キー、dは復号化キーであり、暗号化と復号化は両方ともべき乗modによって実行されmます。キーを使用してメッセージa を暗号化しe、次にキーを使用して復号化する場合d、（a e）d = ademodを計算しますm。しかしde = 1 mod phi(m)、オイラーのトーティエント定理は、deが1 mod mと合同であることを示しているため、つまり、元のを取り戻すことができますa。

因数分解を知らdずに、暗号化キーeとモジュラスのみを知っている復号化キーを取得するための既知の効率的な方法はないため、RSA暗号化は安全であると考えられています。mm = pq

于 2010-07-09T04:19:24.007 に答える