サルにも分かるRSA暗号

解読できないか

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

(AE)D = A{n × (P - 1) × (Q - 1) + 1}

という関係がなければならず(但し n は自由な正の数)、

E × D = n × (P - 1 ) × (Q - 1 ) + 1

D = n × (P - 1 ) × (Q - 1 ) + 1

E
(専門書では「逆元」と「ユークリッドの互除法」から同式が得られます)

から D を求め、暗号化した数値を D 乗すれば、ふたたび元の平文の数値に戻ることになるはずです。 従って、この D が、E 乗して暗号化した暗号文を復号できる鍵になります( E は (P-1)×(Q-1) と「互いに素な数」という関係が成り立つ必要がありますが、大まかな理解においては気にしなくて構いません)。

結局、重要なのは2つの素数P と Qです。 法とする数 P×Q と、暗号化に使う鍵 E は公開してしまうので、もしも P と Q がバレてしまったら秘密にしなければならない鍵 D を上の式から求められてしまいます。 P と Q は暗号としては2つの鍵を作り出すのに必要なだけで、直接暗号化や復号の作業には登場しないものなので、一度鍵を作ったら 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 って分かっちゃうんじゃじゃないの…? ということです。

これこそがRSA暗号の安全性の 根幹 のなのです。 これって素因数分解のことですよね。

戻る
進む
ページ上部へ