連載「暗号と暗号史」

このエントリーをはてなブックマークに追加
2011/10/13

【第8回】有史以来の課題を解決~「公開鍵暗号」RSA暗号~

米国政府のDES暗号採用を契機に、政府や軍部などの限られた人間から世界中の人々が利用するようになった暗号。しかし、いくら強固な暗号を用意しても、それを復号する鍵がメッセージを送る相手へ安全に送られなければ意味がない。

 「鍵」の配送は有史以来、暗号に携わる人間達が頭を悩ませていた問題である。通信網やコンピュータが一般に広まり、暗号の利用者が格段に増えた20世紀後半にはなおさら放置できないものになっていたが、これを解決に導いた数学者・エンジニア達がいた。

 「暗号と暗号史」第8回は、鍵を安全に送るための公開鍵暗号の理論、そして実際の暗号方式「RSA暗号」の誕生を見てみたい。

閉める鍵を公開する

 米国・スタンフォード大学の研究員だったホイットフィールド・デフィーとマーティン・ヘルマン、そしてラルフ・マークルの3人は、暗号化通信のための鍵を安全に送る「デフィー・ヘルマン鍵共有」方法を1976年に発表した。公開鍵暗号の誕生だ。


 彼らが用いたのは「1方向性関数」「非対称関数」と言われる、要するに後戻りができない計算方法である。閉める鍵と開ける鍵が別々のものになるというものだ。

公開鍵暗号の仕組み
公開鍵暗号の仕組み

 公開鍵暗号は大まかに説明すれば次のようになる。AさんがBさんへ秘密の文書を送りたいときは、まずAさんの鍵(共通鍵)自体を、Bさんが不特定多数に公開している公開鍵を使って暗号化し、文書を送る。


 暗号化された文書を受け取ったBさんは、自分しか知らない秘密鍵を使って共通鍵を復号する。この共通鍵を使ってBさんは文書を読めるようになる、という仕組みだ。


 Bさんの公開鍵で暗号化されたデータは、公開鍵では開けることはできない。悪意を持った人が公開鍵を持っていても、Bさんに宛てた文書を見ることはできない。


 公開鍵と秘密鍵は常に対になっており、逆に秘密鍵で暗号化したファイルは公開鍵でしか平文化できない。この機能を利用することで、デフィー・ヘルマンの鍵配送方法は、鍵を安全に送れるだけでなく、相手の認証にも活用できる。相手の見えないネットワーク上の通信で、情報を送る相手が当の本人であるかを確認するのは非常に重要だ。


 Aさんが「本当にBさんであるか」を確かめるには、Bさんへ平文を送る。Bさんは秘密鍵を使って暗号化したデータを送る。本物のBさんの秘密鍵であれば、Bさんの公開鍵で開くことができるため、平文送付先の真偽が確認できる。


公開鍵暗号「RSA」

 デフィー・ヘルマンの理論は画期的なものだったが、この時は、理論を実行する関数を見つけるまでには至らなかった。デフィー達の後を継いで形にしたのはロナルド・リベスト、アディ・シャミア、レナード・アドルマンの3人だ。


 彼らはデフィー・ヘルマンの発表から1年後の1977年、「1」と「その数」以外で割り切れない「素数」を用いた「RSA暗号」(3人の研究者の頭文字)を発表した。


 RSA暗号は「2つの違う素数を掛けた数」、それから「何乗するかの数」、この2つを公開鍵として使用する。Aさんがこの公開鍵を使用して暗号化した文書を受け取ったBさんは、自分の秘密鍵(何乗するかの数)を使って平文に戻す。この時、Bさんの秘密鍵、それから2つの素数は他人に知られてはいけない。

RSA暗号の仕組み(クリックすると拡大します)
RSA暗号の仕組み(クリックすると拡大します)

 RSA暗号は、2つの素数さえ分からなければ安全なものとなる。またRSA暗号の安全性は素因数分解の難しさ、言うなれば「絶対破られない」のではなく、「鍵を解くまでにかかる膨大な時間」で担保される。


 実際、RSA暗号発明者のリベストが1977年に129桁の素因数分解を出題したが、解答が出たのは17年後の1993年。それも1600台のコンピュータを8ヶ月間稼働させた結果だ。現在使われている公開する素数の桁数は、約300~600桁のものとなっている。


秘密裏に公開鍵暗号を開発していた英国

 こうして誕生した公開鍵暗号だが、なんと英国ではこれより数年早く公開鍵暗号の理論と実装を発見していた。


 理論を打ち出したのは、第2次世界大戦中のエニグマ解読を行ったブレッチレーパークの後を引き継いだ英国政府通信本部(GCHQ)に所属するジェームズ・エリス。彼は1969年頃にデフィー達が考案した理論にたどり着き、1973年にGCHQへ入った数学者クリフォード・コックスがRSA暗号と同じ素数と素因数分解をベースにした公開鍵暗号を発見した。


 この事実が公開されたのは1997年。暗号に関する最先端の研究は世間の耳目を集めることなく進められていたのである。


 次回は、現在利用されている様々な暗号を見ていきたい。

(中西 啓)

>>暗号と暗号史【第9回】へ


【関連カテゴリ】

情報セキュリティ