暗号はなぜ破られないのか

破られない暗号は、70年以上前に完成していた

オンラインで買い物をするとき、クレジットカードの番号は、誰でも覗ける経路を通って送られています。カフェのWi-Fiの電波は隣の席にも届いていますし、インターネットの通信は世界中の見知らぬ機器を経由します。それでも番号が盗まれないのは通信が暗号化されているから——ここまでは多くの人が知っています。では、その暗号はなぜ破られないのでしょうか。

「絶対に破られない暗号」は、夢物語ではありません。1949年、情報理論の創始者クロード・シャノンは、どれほど強力な計算機を持つ攻撃者でも原理的に解読できない方式——ワンタイムパッドと呼ばれる、使い捨ての鍵を使う暗号——の安全性を数学的に証明しました。完全な暗号は、70年以上前に完成しているのです。

ところが、あなたのスマホはそれを使っていません。ごく特殊な用途を除けば、銀行も政府もほとんど使っていません。世界が実際に頼っているのは、「破られない」とは誰も証明していない暗号のほうです。なぜ、完璧な暗号は選ばれなかったのでしょうか。

完璧な暗号には、平文と同じ重さの代償がつく

ワンタイムパッドの仕組みは単純です。送りたいメッセージと同じ長さの、完全にランダムな鍵をあらかじめ用意し、メッセージと重ね合わせて暗号文を作る。鍵は一度使ったら捨てる。この条件を守る限り、暗号文をいくら眺めても元のメッセージについて何ひとつ情報が得られないことを、シャノンは証明しました。攻撃者の計算力は、いっさい関係ありません。

ただしシャノンは、同じ論文で冷や水を浴びせる定理も証明しています。完全な秘匿を実現するには、鍵はメッセージと同じかそれ以上の長さでなければならない、というものです。1ギガバイトの動画を秘密にしたければ、1ギガバイトのランダムな鍵を、先に安全な方法で相手に届けておかなければなりません。しかし、鍵を安全に届ける手段があるのなら、その手段で動画そのものを届ければよいはずです。完璧な暗号は「鍵をどう配るか」という問題を解かないまま、守るべき秘密を鍵の形に移し替えただけでした。

この隘路が、その後の暗号設計の分かれ道になります。完璧さを取れば実用が死ぬ。実用を取るなら、何かを諦めなければならない。現代の設計者たちが諦めたのは、「絶対」のほうでした。

設計者たちは「解けない」を捨て、「解き終わらない」を選んだ

1976年、ホイットフィールド・ディフィーとマーティン・ヘルマンは「New Directions in Cryptography（暗号の新しい方向）」と題した論文で、常識を裏返す方式を提案します。盗聴されている公開の通信路だけを使って、二人の間に共有の秘密を作れる、というのです。事前に何の秘密も共有していない二人が、公開のやり取りだけで、盗聴者には割り出せない共通の鍵にたどり着く。秘密を運ばずに、秘密を作る。ワンタイムパッドを実用から遠ざけていた鍵配送問題への、まったく新しい答えでした。

彼らが構想した「公開鍵暗号」を実際の方式に仕上げたのが、1977年にMITのロナルド・リベスト、アディ・シャミア、レナード・エーデルマンが考案したRSA暗号です。核心にあるのは、掛け算と素因数分解——数を素数の掛け算にまで分解すること——の非対称性です。大きな素数を二つ掛け合わせるのは一瞬ですが、できあがった積から元の二つの素数を割り出すのは、数が十分大きければ、知られているどの方法でも天文学的な時間がかかります。

ここで、安全の定義が根本的に入れ替わったことに注目してください。現代の暗号は「解けない」ことを保証しません。目指しているのは「解き終わらない」こと——攻撃者の寿命と予算が尽きるまで、計算が終わらないことです。安全性の通貨は、真理から時間に替わりました。

そして、この土台には未証明の仮定が埋まっています。素因数分解が本当に難しいことは、証明されていません。さらに根本にある「答え合わせが簡単な問題は、解くのも簡単か」というP対NP問題も未解決のままで、クレイ数学研究所が100万ドルの懸賞金をかけてから四半世紀が経ちます。速い素因数分解の方法が明日見つかる——その可能性を排除する証明を、人類はまだ持っていないのです。

「4京年かかる」はずの計算は、17年で終わった

その時間の見積もりがどれほど頼りないかを示す出来事が、実際に起きています。

1977年8月、サイエンティフィック・アメリカン誌の名物コラムニスト、マーティン・ガードナーは、発表されたばかりのRSA暗号を紹介し、読者への挑戦として129桁の数で暗号化された一文を掲載しました。考案者のリベストは、当時最良のアルゴリズムと最速の計算機を仮定して、125桁の数の素因数分解にはおよそ4京年——宇宙の年齢のざっと300万倍——かかると見積もっています。賞金は100ドルでした。

解読の報せは、4京年後には来ませんでした。17年後の1994年に来ました。世界中の600人を超えるボランティアが約1,600台の計算機をインターネット越しにつなぎ、およそ半年がかりで129桁の素因数分解をやり遂げたのです。現れた平文は「The magic words are squeamish ossifrage（魔法の言葉は神経質なヒゲワシ）」という他愛のない一文で、100ドルの賞金はフリーソフトウェア財団に寄付されました。

見積もりを狂わせたのは、計算機の高速化だけではありません。決め手は、1981年にカール・ポメランスが考案した「二次ふるい法」という、1977年には存在しなかったアルゴリズムでした。ハードウェアの進歩はある程度予測できても、数学の進歩は予測できない。「解き終わらない」への信頼は、こうして時おり大幅に値切られます。暗号の鍵の長さが数十年にわたって伸び続けてきたのは、この追いかけっこの跡です。

数学が無傷でも、暗号は破られる

もっとも、現実の暗号が破られるとき、正面の数学が敗れることはめったにありません。

1996年、暗号研究者のポール・コッハーは、研究者たちを騒がせる攻撃を発表しました。暗号の計算にかかる時間を精密に測ると、そこから秘密鍵が割り出せる、というのです。計算の中身は覗けなくても、処理にかかる時間は鍵の中身に応じてごくわずかに変わる。金庫の扉をこじ開ける代わりに、ダイヤルを回す音を聴き分けるような攻撃です。この種の手口はサイドチャネル攻撃——正面の数学ではなく、実装が漏らす物理量を突く攻撃——と呼ばれ、その後、消費電力や電磁波からも鍵が抜き取れることが次々と示されていきました。

そして現実の情報漏洩の多くは、そんな精密さすら必要としません。鍵の管理ミス、設定の不備、人間をだますソーシャルエンジニアリング。設計者の間では「攻撃者は正面から数学に挑まない。横から、あるいは人から入る」が半ば常識になっています。「暗号はなぜ破られないのか」への答えの半分は、「破られている。ただし、数学ではない場所で」なのです。

証明のない安全の上で、世界は今日も回っている

整理しましょう。理論的に完全な暗号は存在しますが、鍵配送の代償が重く、ほとんど使われていません。世界を実際に支えているのは計算量的安全性——「まだ誰も速い解き方を見つけていない」という経験の積み重ね——で、そこに証明はありません。それどころか、計算は簡単で逆算だけが難しい「一方向関数」なるものが本当に存在するのかどうかさえ、証明されていないのです。

一方で、時間の壁を掘り崩す候補はすでに現れています。1994年、ピーター・ショアは、量子コンピュータの上でなら素因数分解が現実的な時間で解けるアルゴリズムを発見しました。それを実行できる規模の量子コンピュータはまだ存在しませんが、米国の国立標準技術研究所（NIST）は量子計算に耐える新方式の公募と選定を2016年から進め、2024年8月に最初の標準を確定させました。攻撃が現実になる前に土台ごと入れ替える工事が、いま世界中の通信の裏側で静かに進んでいます。

考えてみれば、不思議な光景です。送金も外交も医療記録も、証明されていない仮定の上に置かれている。しかもそれを誰より知っている専門家たちは、パニックに陥るでもなく、粛々と鍵を伸ばし、標準を入れ替えている。工学の安全は、真理の上にではなく、「まだ破られていない」という経験と、破られたときに備える準備の上に築かれるものなのかもしれません。今夜スマホで何かを買うとき、少しだけ思い出してみてください。その決済を守っているのは完成した証明ではなく、稼ぎ続けられている時間と、それを見張り続ける人たちなのです。