公開指数の逆数を求めるRSA

Question

私はRSA鍵の生成とその使用に非常に基本的な疑問があります。

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

Answer 1

ウィキペディアhereおよびhereを参照してください。基本的には、暗号化を「元に戻す」ために復号化する必要があります。イー・D = 1 MODφ（N）は、Eと同等であるので* D = 1 +いくつかの整数kの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）^XY =（^X）^Y =（^{Y X}）^{、及び
2）X +はX * Yが= Yこれを終えると（M ）*（M φ（N））K MOD Nを簡素化、THAを覚えて}

、^φ（N） = 1 MOD N Tので

（M ^φ（N））^K MOD N = 1 ^K = 1 MOD N.