ズブさんの
アイデア天体
写真館

もくじ

公開鍵と素数

昨日、「フェルマーの最終定理」に関する本を読んだことを書いた。このような数学の話題に興味を持ったのは、インターネットでの暗号化の話がもとだった。

インターネットでは、バケツリレー式にデータを次々転送し、相手先のコンピュータに届ける。そのため、途中でいわゆる盗聴を行うことが可能だ。クレジットカードの番号や、会員登録のための個人情報などを入力するとき、あるいはそもそもパスワードを入力するときに盗聴されては問題だから、盗聴されても意味が分からないようにするため暗号化が必要となる。しかし、正規の受信者は暗号化された情報を復号(暗号化された情報を元に戻すこと)できなくては通信の意味がない。ところが、元に戻す方法をインターネットで教えれば、「元に戻す方法」が盗聴されてしまうかもしれない。かといって、インターネット以外の方法で「元に戻す方法」を伝えるのではインターネットの利便性が損なわれる。

この問題を解決する方法として『公開鍵』という方法がある。暗号化するための“鍵”と復号するための“鍵”が別という方法だ。鍵といっても、コンピュータの情報はすべて数字なので、実際は「計算方法」である。暗号化する鍵は公開してしまう。「自分のところに送る情報を暗号化するときは、こういうふうに計算して暗号化してくれ!」と公開してしまうのだ。これが公開鍵となる。しかし、それを復号するための計算方法は教えない。こちらは秘密鍵となり、自分だけが知っている。

一見良さそうな方法だが、問題は、そんな都合のいい計算方法があるか、ということだ。例えば、「伝えたい数字に3を掛けて2を足して、暗号化してくれ!」と言えば、元に戻す方法は教えられなくても「2を引いて3で割る」と分かってしまう。実は“都合のいい計算方法”があるのだ。それは、「伝えたい数字をe乗し、それをnで割ったときの余りを算出して、暗号化してくれ!」というものだ。この暗号化された数字は、暗号化するための計算方法がわかっても、逆算ができない。しかし、暗号化された数字を「d乗し、nで割ったときの余りを算出する」と、なんと元の数字に戻るというのだ。この「d」という数字は秘密にしなくてはいけない。dという数字が小さいと、総当りで計算すればそのうち正解が見つかってしまうだろう。しかし、総当りで計算するには時間がかかりすぎるくらい大きくしておけばいいのだ。

さて、この話が素数とどう関係があるのか。この計算に使うeとかn、dといった数は適当なものではいけない。ある条件を満たす数である必要がある。このような条件に合う数を見つけるのに素数を元にするのだ。nという数字は、2つの素数の積を用いる。e、dも元の素数から条件に合うものを見つける。この暗号が簡単に解読できないのは、「大きな数を素因数分解するのは困難である」という仮定に基づいている。だからnという数字を公開しても、秘密にしているdという数字が求められないのである。しかしこれは『仮定』であり、証明はされていない。だから、「大きな数を素因数分解する簡単な方法」が見つかったら、この暗号方法は信頼できなくなる。それにしても、このような数学上の性質が実際に応用されるというのは面白いと思った。最初に素数の研究をした人は、こんなふうに応用されるとは思っていなかっただろう。

なお、ここに書いたのはかなり大雑把な説明である。詳しいことを知りたいときは、「RSA暗号」などのキーワードで調べるとよいと思う。

2006.4.3