公開鍵暗号の背後にあるシンプルな数学

この物語 のオリジナル版はQuanta Magazineに掲載されました。

何千年もの間、秘密のメッセージを送りたい場合、基本的に方法は一つしかありませんでした。それは、あなたと相手だけが知っている特別なルールを使ってメッセージを暗号化するのです。このルールは錠前の鍵のような役割を果たします。鍵さえあればメッセージを解読できますが、そうでなければ錠前をピッキングしなければなりません。中には、無限の時間と資源を費やしても決して解読できないほど強力な錠前もあります。しかし、そのような仕組みにも、あらゆる暗号化システムに共通する弱点があります。それは、鍵を正しい人の手に渡し、同時に間違った人の手から守るにはどうすればよいかということです。

直感に反する解決策である公開鍵暗号は、鍵を秘密にするのではなく、広く公開することを前提としています。秘訣は、通信相手であっても誰にも共有しない2つ目の鍵も使うことです。この2つの鍵（公開鍵と秘密鍵）の組み合わせを使うことでのみ、メッセージを暗号化したり復号化したりすることが可能になります。

この仕組みを理解するには、「鍵」を錠前にはめ込む物体としてではなく、目に見えないインクの2つの相補的な成分として考えると分かりやすいでしょう。最初の成分はメッセージを消し、2番目の成分はメッセージを再び現れさせます。ボリスという名のスパイがナターシャに秘密のメッセージを送りたい場合、彼はメッセージを書き、最初の成分を使って紙上でメッセージを見えなくします。（これは彼にとって簡単なことです。ナターシャはインクを消す簡単でよく知られた製法を公開しています。）ナターシャが郵便で紙を受け取ると、ボリスのメッセージを再び現れさせる2番目の成分を塗布します。

この計画では、誰でもメッセージを見えなくすることができますが、再び見えるようにできるのはナターシャだけです。彼女は第二の材料の配合を誰にも、たとえボリスにさえも教えないので、メッセージが解読されていないことを確信できます。ボリスが秘密のメッセージを受け取りたい時は、同じ手順を踏むだけです。メッセージを消す簡単なレシピを公開し（ナターシャや他の誰でも使えます）、同時にメッセージを再び表示させるレシピを自分だけのために残しておきます。

公開鍵暗号では、「公開鍵」と「秘密鍵」は、この特殊な目に見えないインクの第一と第二の材料のように機能します。一方がメッセージを暗号化し、もう一方がそれを復号します。しかし、公開鍵暗号では化学物質ではなく、「落とし戸関数」と呼ばれる数学的なパズルを用います。これらの関数は一方向への計算は容易ですが、逆方向への計算は極めて困難です。しかし、これらの関数には「落とし戸」と呼ばれる情報も含まれています。これを知れば、関数を双方向で容易に計算できるようになります。

よくある落とし戸関数の一つに、2つの大きな素数を掛け合わせるというものがあります。これは簡単に実行できる演算です。しかし、その逆、つまり積から始めてそれぞれの素因数を求める演算は、計算上非現実的です。公開鍵を作成するには、まず2つの大きな素数を用意します。これらが落とし戸です。2つの数を掛け合わせ、さらにいくつかの数学演算を実行します。これで、この公開鍵でメッセージを暗号化できます。復号化するには、対応する秘密鍵が必要です。秘密鍵には、必要な落とし戸である素因数が含まれています。これらの素因数があれば、メッセージは簡単に復号化できます。この2つの素因数を秘密にしておけば、メッセージは秘密のままです。

公開鍵暗号の基礎は、1970年から1974年の間に、第二次世界大戦中にナチスのエニグマ暗号を解読した英国政府通信本部に勤務していた英国の数学者によって初めて発見されました。彼らの研究成果（1997年まで機密扱い）は米国国家安全保障局と共有されましたが、コンピューティング能力が限られていて高価だったため、どちらの政府もそのシステムを実装しませんでした。1976年、米国の研究者であるホイットフィールド・ディフィーとマーティン・ヘルマンが、暗号学者ラルフ・マークルの影響を受け、初めて公に知られる公開鍵暗号方式を発見しました。わずか1年後、発明者であるロン・リベスト、アディ・シャミール、レナード・エイドルマンにちなんで名付けられたRSAアルゴリズムにより、公開鍵暗号を使用する実用的な方法が確立されました。RSAは現在でも広く使用されており、ショッピングからWebベースの電子メールまで、あらゆるものを可能にしている現代のインターネットの基本的な構成要素です。

この2つの鍵システムは、「デジタル署名」、つまりメッセージが秘密鍵の所有者によって生成されたことを数学的に証明する手段も可能にします。秘密鍵はメッセージを復号するだけでなく、暗号化にも使用できるため、この仕組みは機能します。もちろん、これはメッセージの秘密性を保つという点では役に立ちません。秘密鍵を使ってメッセージを暗号化した場合、誰でも対応する公開鍵を使って復号できてしまうからです。しかし、秘密鍵の所有者であるあなただけがメッセージを暗号化できるため、このシステムは、あなただけがメッセージを作成したことを証明します。ビットコインのような暗号通貨は、このアイデアなしには存在し得なかったでしょう。

1つではなく2つの暗号鍵がそれほど効果的なのなら、なぜ発見に数千年もかかったのでしょうか？カリフォルニア大学サンディエゴ校のコンピューター科学者で暗号理論家のラッセル・インパグリアッツォ氏によると、コンピューターが発明される前は、落とし戸関数の概念はそれほど有用ではなかったそうです。

「これは技術の問題です」と彼は言った。「19世紀の人は、暗号は軍事情報を扱う個々のエージェントと現場、文字通り銃撃戦の現場にいる個々のエージェントの間で行われるものだと考えていました。ですから、最初のステップが『100桁の素数を2つ選んで掛け合わせる』というものだとしたら、実際に掛け合わせる前に戦いは終わってしまうでしょう。」問題を人間がすぐにできるレベルまで単純化してしまうと、それほど安全ではなくなるだろう。

コンピュータは公開鍵暗号の実現に貢献した一方で、その防御に亀裂を生じさせてきました。1994年、数学者ピーター・ショアは、素因数分解を含む、現在のほとんどの公開鍵暗号システムの基盤となっている落とし戸関数を量子コンピュータで効率的に逆転させる方法を発見しました。このアルゴリズムが実装されれば、あらゆる目に見えないメッセージを再現できる万能の「再現インク」のように機能します。さようなら、インターネットセキュリティ。

幸いなことに、量子コンピュータ自体は「まだENIAC段階にある」とインパグリアッツォ氏は述べ、1945年に米軍向けに開発された部屋ほどの大きさのマシンを指して言った。量子コンピュータが公開鍵暗号に真の脅威を与えるほど高度化する頃には、従来のトラップドア関数は格子問題と呼ばれる「量子耐性」のあるバージョンに置き換えられる可能性がある。もちろん、この新しい計算「インク」も将来的には攻撃を受けやすくなる可能性がある。しかし、それが公開鍵暗号の素晴らしい点だ。新しい関数を見つけられる限り、車輪の再発明、あるいはこの場合は鍵の再発明を繰り返していけばいいのだ。

オリジナルストーリーは、数学、物理科学、生命科学の研究の進展や動向を取り上げることで科学に対する一般の理解を深めることを使命とする、 シモンズ財団の編集上独立した出版物であるQuanta Magazineから許可を得 て転載されました。