RSAの公開鍵

質問

RSAは二つの素数p、qから乗算された合成数Nと
(p-1)(q-1)と互いに素な整数eを公開鍵とするそうですが、
同じ平分Mをeだけ変えてNは同じ値を使って2種類の暗号文を作った場合、
2つの暗号文が手に入れば鍵を知らなくても複合化されてしまうそうですが、
どうしてでしょうか。

回答No.1

Rice-Etude · ベストアンサー

共通の法使用時の同一平文暗号化の問題ですね。

一方の公開鍵を(ea,N)、もう一方の公開鍵を(eb,N)とします。Nは共通とします。

そして二つの暗号文を
Ca＝M^ea(mod N)
Cb＝M^eb(mod N)
とします。

GCD(ea,eb)＝1よりα×ea＋β×eb=1を満たすα,βが存在し、それを求めることができます。
そうすると、二つの暗号文と求めたαとβを使って【mod表示を省略します】
　Ca^α×Cb^β
＝(M^ea)^α×(M^eb)^β
＝M^(α×ea)×M^(β×eb)
＝M^(α×ea＋β×eb)
＝M^1
＝M
を計算することで、Mが求まります。

お礼

大変わかりやすい回答ありがとうございました。
とても理解しやすかったです。