公開鍵暗号

二十世紀の半ばまで、暗号には逃れられない前提があった。送る側と受ける側が、同じ鍵を持っていなければならない。鍵で文を閉じ、同じ鍵で開く。問題は、その鍵をどうやって相手に渡すかである。会って手渡すか、信用できる使者に託すしかない。そして暗号の仕組みのうちで、いちばん危ういのがこの受け渡しだった。

人数が増えると、問題は手に負えなくなる。何人もの人が互いに秘密の通信をするには、組み合わせの数だけ鍵が要り、千人なら五十万近くになる。それを前もって全部配っておかなければならない。軍や銀行は実際にそうしていて、鍵を詰めた鞄を武装した使者が運んでいた。鍵配送問題と呼ばれるこの難題は、会ったことのない相手とは秘密の通信ができないことを意味していた。計算機の網が広がり、見知らぬ相手と取引をする時代が近づくにつれて、それは大きな障害になろうとしていた。

この問題に取り憑かれたのが、ホイットフィールド・ディフィーである。1944年に生まれ、マサチューセッツ工科大学で数学を学んだが、大学に腰を落ち着けず、1970年代の初めには暗号について何か知っている人を探して、アメリカ中を車で回った。当時、暗号の研究は事実上、国家安全保障局の中にしかなく、公開された文献はほとんど無かった。1974年、ディフィーはスタンフォード大学で電気工学者マーティン・ヘルマンを訪ねた。三十分の予定だった面会が一日がかりの議論になったと、二人とも後に語っている。

二人が考えたのは二つの問いだった。前もって鍵を共有していなくても、秘密の通信はできるか。そして、電子の文書に署名はできるか。紙の署名は紙の上に残るが、電子のデータは寸分違わず複製できる。それなら、本人が書いたことをどう示せばよいのか。

1976年11月、二人は論文「暗号技術の新しい方向」を発表した。若い研究者ラルフ・マークルが別に温めていた着想も、この流れに先立っていた。論文は、自分たちはいま暗号の革命の入口に立っている、という趣旨の宣言で始まる。

中心にあるのは、鍵を二つに分けるという考え方である。一つは誰にでも配ってよい公開の鍵、もう一つは自分だけが持つ秘密の鍵。公開の鍵で閉じたものは、秘密の鍵でしか開かない。たとえて言えば、開いた南京錠をたくさん作って誰にでも配り、鍵は自分だけが持っておく。誰でも箱に錠をかけて送れるが、開けられるのは自分だけである。逆に秘密の鍵で作った印を公開の鍵で確かめれば、それは本人にしか作れない署名になる。

論文はもう一つ、具体的な方法も示した。公開の回線でやりとりを全部盗み聞きされていても、二人だけが同じ秘密の数を共有できる方法で、ディフィー・ヘルマン鍵交換と呼ばれる。ある数を何乗かして別の数で割った余りは簡単に計算できるのに、その余りから何乗したのかを逆に求めるのはきわめて難しい。この一方通行の性質を利用している。ただし、この論文には誰にでも配れる鍵で暗号化するという方式そのものは、まだ具体的には書かれていなかった。そういうものがあるはずだ、と示したのである。

翌1977年、マサチューセッツ工科大学のロナルド・リヴェスト、アディ・シャミア、レナード・エーデルマンの三人が、その方式を作った。リヴェストとシャミアが案を出し、エーデルマンがそのたびに破るということを何十回も繰り返したと伝えられる。1977年4月、ユダヤ教の過越の祭りの夜に集まった後、眠れなかったリヴェストが案をまとめ、朝までに論文の下書きを書き上げたという。三人の頭文字をとってRSA暗号と呼ばれる。

原理は、大きな素数を二つ掛け合わせるのは簡単でも、できあがった積から元の二つの素数を探し出すのはきわめて難しい、という性質にある。何百桁もの数を素因数に分けるには、いまの計算機でも途方もない時間がかかる。ただし、それが本当に難しいということは数学的に証明されているわけではない。いまのところ速い方法が見つかっていない、というだけである。

話には続きがあった。1997年、イギリスの政府通信本部が古い記録の機密を解いた。そこから分かったのは、1970年にはジェイムズ・エリスが秘密の鍵を共有しない暗号は可能だという着想を書き残しており、1973年には入ったばかりの若い数学者クリフォード・コックスがRSA暗号とほぼ同じ方式を考え出していたことだった。コックスは、思いつくのに三十分ほどしかかからなかったと後に語っている。1974年ごろにはマルコム・ウィリアムソンが、ディフィー・ヘルマンと同じ鍵交換にたどり着いていた。どれも機密とされ、当時の計算機では実用にならないとも判断されて、外には出なかった。エリスは機密解除のわずか一か月前の1997年に世を去り、自分の仕事が公になるのを見ることはなかった。

いま、このページを開いたときにも、ブラウザとサーバーのあいだで公開鍵による鍵の交換が行われ、電子署名がサイトの身元を保証している。インターネットでの買い物も、銀行の振り込みも、電子メールの暗号化も、この考え方の上に成り立っている。暗号の歴史は長く国家の秘密の領分で、第二次大戦でアラン・チューリングらが取り組んだ解読（エニグマの解読）も、戦後何十年も伏せられていた。それが、1976年の論文を境に、大学と民間の研究者の手に移っていった。

次の課題も見えている。1994年、数学者ピーター・ショアは、十分に大きな量子計算機があれば、素因数分解も離散対数も現実的な時間で解けることを示した。それが実現すれば、RSA暗号もディフィー・ヘルマン鍵交換も破られる。いつ実現するかは分からない。だが、いま暗号文を盗んで保存しておき、後で解読するという手がすでに使われていると考えられている。そのため量子計算機にも耐える新しい暗号への切り替えが始まっており、2024年にはアメリカの国立標準技術研究所が最初の標準を定めた。鍵を配るという古い問題を解いた発明は、いま次の世代への引き継ぎを迎えている。