rsa - 公開指数の逆数を見つけるRSA

Question

私は RSA 鍵の生成とその使用法について非常に基本的な疑問を持っています。

RSA 鍵生成では、非常に大きな順序の 2 つの大きな素数を選択します。次に、それらを乗算します。(eq p * q = N) さて、Euler(N)=(p-1)(q-1). 0 < e < Euler(N)ここで、e と Euler(N) が互いに素となる数を見つけます。{e.Euler(N)}があなたの公開鍵になります。ここで、d(秘密鍵) を次のように計算しe * d =1 (mod(Euler(N)))ます。
ここで、公開鍵を使用して何か (m) を暗号化するとします。c=m^e(mod(N)). そして、秘密鍵 (d) を使用して暗号化を解除しているときに、c^d(mod(N)).
今私の疑問は、あなたが mod(Euler(N)) で e の逆を見つけたということですが、復号化するときは mod(N) でそれをやっています。これはどのように可能ですか？

Answer 1

こことここのウィキペディアを参照してください。基本的に、暗号化を「元に戻す」ために復号化が必要です。e⋅d = 1 mod φ(N) は、ある整数 k に対して e⋅d = 1 + k⋅φ(N) と等価であるため、次のようになります。

c ^d mod N = (m ^e ) ^d mod N = m ^(e⋅d) mod N = m ^{(1 + k⋅φ(N))} = (m ¹ ) ⋅ (m ^φ(N) ) ^k mod N

代数で学んだ次の規則を適用することによって:

1) a ^xy = (a ^x ) ^y = (a ^y ) ^x
2) a x ^+y = a ^x ⋅ a ^y

これを終了して単純化するには、(m ¹ ) ⋅ (m ^φ(N) ) ^k mod N を思い出してください^{。a φ(N)} = 1 mod N で あることを思い出してください。

(m ^φ(N) ) ^k mod N = 1 ^k = 1 mod N.