サルにも分かるRSA暗号

素因数分解の難しさ

「素因数分解」は、中学生三年生で習うはずです。 ある数が与えられたら、その数と 1 でしか割りきることができない 2 以上の整数…すなわち素数を使った掛け算の式に分解することです。 例えば、 33 なら 3×11 という式に分解できますね。 3 も 11 もそれぞれ素数ですよね。

あら?そんな方法があるなら、法とする数 P×Q = 33 を公開してしまえば、誰にでも P=3, Q=11 であることが分かってしまいまいますョ…。 そして公開する鍵 E は公開されてるから秘密の鍵 D を求められてしまいます。 う〜ん、これは困りましたね…。 でもこの 33 の素因数分解、あなたはどんな方法で 3×11 に分解しましたか?

実はこれ、人間の勘と長年の経験 によるところが非常に大きいのです。 その証拠に、それでは 6887 はどう素因数分解されますか? これも2つの素数に分解できるのですが、どうすれば分解できるか思い付かないでしょう。 思い付いたとして、きっと 2 から順に 3, 5 ... って割れないか試してみる程度じゃないですか?

それもそのはず、現在のところ 巨大な二つの素数を掛け合わせた数を素因数分解できる、効率的な方法は見つかっていない のです…。 つまり、二つの素数 P=3 と Q=11 を掛けて P×Q = 3×11 = 33 を求めることは簡単にできますが、逆に掛けた結果の P×Q = 33 から P と Q ( 3 と 11 ) を効率的に求めることは極めて難しいという意味です。 これが重要なのです。 6887 を素因数分解できなかったのは、 決して あなたの頭が悪かった からではないのです。 ちなみにこれは 71 と 97 に素因数分解できます。 実際に掛けてみて下さい、71 と 97 を掛けて 6887 を求める方は簡単ですから。

先ほどのRSA暗号は試しに P=3, Q=11 で P×Q = 33 という小さな数を選んだために P×Q = 33 から P=3 と Q=11 を割り出せましたが、これが巨大な素数を掛けたものとなると割り出せなくなってしまうのです。 この結果、法とする数 ( P×Q ) と 公開鍵 E を公開してしまっても、P, Q を使って秘密鍵 D を求めた本人以外には秘密鍵 D を知られずに済むのです。 RSA暗号は、暗号の仕組みに「奇跡が起きるべき乗数」を用い、その安全性には 素因数分解の難しさ を使っているのです。

戻る
進む
ページ上部へ