12. 解読できるか

ＲＳＡ暗号の暗号化と復号の手順が分かりました。 少しだけまとめると、まず自由な２つの異なる素数 P , Q を定め、 N ( = P×Q ) を法とする世界を考えるのです。この P×Q を法とする世界で、 平文の数値を適当に定めた E 乗することで暗号化を行ないます。 この時、全ての数は n×(P-1)×(Q-1) + 1 乗すると どんな数も必ず自分自身に戻るため、

という関係がなければならないので （但し n は自由な正の数）、

から D を求め、暗号化した数値を D 乗すれば、 ふたたび元の平文の数値に戻ることになるはずです。従って、この D が、E 乗して暗号化した暗号文を復号できる鍵になります （但し E は (P-1)×(Q-1) と互いに素な数とする必要があります）。

結局、重要なのは２つの素数P と Qです。 法とする数 P×Q と、暗号化に使う鍵 E は公開してしまうので、 もしも P と Q がバレてしまったら秘密にしなければならない鍵 D を上の式から求められてしまいます。 P と Q は暗号としては２つの鍵を作り出すのに必要なだけで、 直接暗号化や復号の作業には登場しないものなので、一度鍵を作ったら P と Q をメモした紙は食べてしまうくらいな方が 一番よいかもしれません。

しかし、このような仕組みでは、ある疑問がわきませんか？ 「 P×Q の結果は公に教えてしまうのに P と Q 自体は教えてはいけない」 なんて…でも 「P×Q を教えたら P と Q が分かってしまうのではないのか？」 と。 つまり、先ほどの例で言えば 「ある素数と素数を掛けたら 10 になった （ P×Q = 10 ）」 ということは教えるけども、 つまり 「それがいくつといくつか （ P=2, Q=5 ）」 は教えてはいけないなんて、 P×Q = 10 が分かれば、誰でも P=2, Q=5 って分かっちゃうんじゃじゃないの…？ということです。

それが ＲＳＡ暗号 の重要なミソのなのです。 これ、素因数分解の事ですよね。