名著『暗号解読』① デジタル社会崩壊を防いでいるのは中学で習った数学

スポンサーリンク
スポンサーリンク

数学者の戦争

「第一次世界大戦は化学者の戦争であり、第二次世界大戦は物理学者の戦争だった~略~第三次世界大戦が起こるとすれば、それは数学者の戦争になるだろうと言われている」。英国のサイエンス・ライター、サイモン・シンは、著書『暗号解読』(新潮文庫、青木薫訳)にそう記した(上巻15㌻)。

第一次世界大戦では、毒ガス(マスタードガス)が初めて使用され、第二次世界大戦では、広島、長崎に原子爆弾が投下された。化学、物理学がもたらした陰惨な負の結末である。

 第三次世界大戦は、そう簡単には起きないと思う。しかし、米中間でのサイバー攻防戦は日常茶飯事だそうだし、北朝鮮が金融システムをハッキングして得た数十億ドルを核兵器開発につぎ込んでいるといったニュースを読むと(ブルームバーグ)、各国の対立に暗号が重要な役割を果たし、その裏で数学者たちが熾烈な攻防戦を繰り広げているだろうことは容易に想像できる。

『暗号解読』の原書(The Code Book)の出版は1999年で、もう20年も前だが、その後の世界の流れは、当時の専門家たちが予想した通りの道筋をたどっていると言えそうだ。

著者のサイモン・シン氏はケンブリッジ大学大学院で素粒子物理学の博士号を取得しており、科学に対する知識と理解力は生半可ではない。難しい話を懇切丁寧に説明し、青木薫氏の名訳もあるのだろうが、素人にも理解できるように書かれ、好奇心に誘われて、どんどん読み進んでしまう。シン氏の『フェルマーの最終定理』『宇宙創成・上下』も時折、読み返す愛読書になっている。

解読が難しいRSA暗号の仕組み

それはともかく、暗号をめぐる攻防戦に話を戻すと、現在進行形の開発競争で、将来の勝敗のカギを握るのは量子力学のようだ。『暗号解読』も下巻の最終章「未来への量子ジャンプ」で詳しく言及している。量子コンピュータや量子暗号について20年前に書かれた内容だが、基本に大きな変化はないだろう。

近い将来の暗号ウォーズの話に入る前に、まず現状を確認しておこう。

現在、暗号技術の標準になっているのはRSAと呼ばれる方式だ。RSA暗号は1977年に米国のコンピュータ科学者、数学者たち3人によって着想を得るが、いまだ十分に通用するかなり強力な暗号だ。そして、この暗号の核心は、素因数分解という中学レベルの数学にある。そんな素朴な知恵で暗号が守れるのか疑いたくなるが、仕組みを聞くと、なるほどと思えてきた。

RSA暗号には、二つの鍵がある。鍵とは、暗号文を元の文章に戻すときの規約=プロトコルだ。たとえば「アルファベットを一字先に進めて読む」という規約を決めていたら、暗号文「HAL」を受けた者は、規約に従って復号し「IBM」と読む(厳密には、複合には「鍵+アルゴリズム」が必要だが、「暗号システムの安全性は、鍵の秘密が守れるかどうかにかかっている」上巻39㌻)。当然ながら、鍵は人に知られてはならない。

RSA暗号の二つの鍵とは、公開鍵と秘密鍵だ。ただし、鍵と言っても、公開鍵は、送信者がメッセージを暗号化する時にだけ使われ、秘密にせず、逆に、必要ならば教えてしまう。一方、秘密鍵は、受信者だけが持っており、受け取った暗号メッセージを復号し平文に戻す時に使う。従来の鍵の概念だ。

シン氏は、南京錠と鍵にたとえて、こうわかりやすく説明している。「アリス(メッセージの受信者)は、鍵を大切にしまっておくが、南京錠の方は何千個もの複製を作って世界中の郵便局に送る。ボブ(送信者)がアリスにメッセージを送りたければ、彼はそれを箱に入れ、最寄りの郵便局に行って、”アリスの南京錠”をもらい、箱に掛ければよい。ボブにはその南京錠をはずすことができないが、(郵便配達人から)箱を受け取ったアリスは手元の鍵を使ってそれをはずすことができる」(下巻144㌻)。公開鍵は鍵というよりも錠の性格を持っている。

素因数分解が立ち塞がる

そして、暗号を解こうとする盗聴者が、秘密鍵の成り立ちを探ろうとしたときに高い壁となって立ち塞がるのが素因数分解の難しさである。

秘密鍵の正体は、実は素数だ。受信者はまず、素数pとqを選ぶ。これが秘密鍵になる。暗号を復号するときに使う。pとqに、たとえば、p=17159,q=10247を選んだとする。これは誰の目にも触れないよう大事にしまっておく。

もう一方の公開鍵は、このpとqの積(N)を使う。17159(p)×10247(q)=175828273(N)が公開鍵である。175828273は、南京錠のたとえに従えば、世界中の郵便局に送られることになる。メッセージの送信者はこれを使ってメッセージを暗号化する(下巻151㌻~)。

もちろん実際の暗号はもっと複雑な施しがなされているだろうが、大筋はシン氏の説明の通りと理解しておく。だとしたら、単純そうな作りだが、暗号の強度はこれで保証されるのだろうか。

盗聴者にとって、公開鍵は入手できるし、それが素数の積で成り立っていることも知っている。ならば、公開鍵を中学で学んだ素因数分解すればいいだけだ。高性能のコンピュータにやらせれば容易にp,qがわかるだろう……。

ところが、公開鍵の数字をとてつもなく大きくすると、素因数分解は難しくなる。素数をひとつづつチェックして、しらみつぶしに計算していくらしいのだが、素人の想像を超え、計算に時間がかかるという。

2016年1月に、「史上最大の素数が更新された」というニュースが流れた。2,233万8,618桁の素数だそうだ(WIRED)。確かに、この素数に数百万桁の素数を掛け合わせた数字を秘密鍵にしたら、素因数分解は容易ではないと想像がつく。

『暗号解読』には「10の130乗程度の数を素因数分解するには、ざっと五十年ほどかかる」(下巻156㌻)と書かれている。これは、原書出版当時のコンンピュータの性能による推定だが、最近の数字をネットで調べてみると、富士通の研究者たちが2016年に公表したレポートがあった。

それによると、高強度のRSA暗号を解読できるのは、スパコンの性能向上を計算に入れても、2213年性能になるという(44㌻表)。

200年後に解読された暗号の内容に関心を持つのは歴史学者ぐらいだろう。国家機密や軍事用のドキュメントに使われる暗号ともなれば、解読まで200億年かかるものもあるそうだ(KDDI「TIME&SPACE」)。

いまは暗号優位のようだが、現状の秩序をひっくり返してしまうのが、量子コンピュータだ。

長くなったので、次回に「量子コンピュータも解読できない暗号の仕組みとは」をまとめます。