1章 トラップドアの福音
どうやら21世紀は小売店舗が消滅し、巨大物流倉庫とサーバーと宅配に取って代わるらしい――
そう思って玄関に宅配ボックスを設置したのが2017年のこと。合板で作ってペンキを塗り、柱にチェーンで結びつけた。大小二つのロッカーを備え、扉には南京錠をひっかけた。ハンコが必要な配達人のために、シャチハタの三文判もぶらさげた。 そして本当に配達人が使ってくれるのか、やきもきしながら不在配達の発生を待った。
悲しいことに初回は配達人にスルーされ、郵便受けに不在通知書だけが入っていた。宅配ボックスの存在に気づかなかったらしい。そこで呼び鈴のスイッチの上に掲示を出し、矢印で宅配ボックスの存在を示した。 それからは順調で、配達人からは「宅配ボックス助かります！」と感謝され、こちらも配達がありそうな時に心置きなく外出できるので、いいことづくめになった。
宅配ボックスは施錠できる屋外用ストッカーでも代用できるので、まだの方は設置したらいいだろう。私が作ったものについてはこちらで公開している。
さて、宅配ボックスにはこんなロジックが組み込まれている。
(1) 宅配ボックスは開放空間に設置された私有空間である。
(2) 宅配ボックスは不特定多数が施錠できる。
(3) 宅配ボックスは受取人しか解錠できない。
することは郵便ポストと同じだから、別に目新しいものではない。しかし今回のテーマ、暗号技術のアナロジーになるので、もう少し説明しよう。
集合住宅などにある共用の宅配ボックスは、受取人だけが解錠できるよう、使い捨ての鍵(暗証番号)を受取人に通知する仕組みが加わるが、戸建て用なら単純だ。配達人は荷物をロッカーに入れて南京錠をかける。鍵は家の中にあるので、中身を取り出せるのはその家の住人だけになる。もちろん南京錠をピッキングすれば別だし、いたずらで施錠される可能性もあるが、ここでは考慮しない。
つまり宅配ボックスのポイントは、施錠する機構と解錠する機構が分かれていることにある。
もし分かれてなかったらどうだろうか。施錠も解錠も、同じ鍵を差し込んで回さなければならないとしたら、配達人は担当エリアにある宅配ボックスの数だけ合鍵を持つことになり、現実的ではない。宅配ボックスの持ち主も運送会社ごとに合鍵を作って渡す必要が生じるので不便きわまりない。
宅配ボックスのように施錠だけをして作動したら開かなくなる仕組みをトラップドアという。罠が作動して扉が閉まると中からは開けられない、一方通行のメカニズムだ。暗号技術においても数学的なトラップドアが重要な意味を持つ。
そして鍵を共有する場合に起きる問題を鍵配送問題という。映画や小説で暗号書を届けるためにスパイが命がけの冒険をするのをご存じだろう。鍵配送には大変なコストがかかるので、かつては政府や軍隊、大企業ぐらいしか使えなかった。
それを一気に解決したのが公開鍵暗号という発明だ。物理的実体はなく、数学で定義されたソフトウェアである。
もし公開鍵暗号がなかったら、ネット社会はまったく異なるものになっただろう。AmazonもメルカリもPayPalもネットバンキングも存在できない。ということはPayPalで財をなしたイーロン・マスクの宇宙開発もない。URLがhttpsで始まるウェブサイトは公開鍵暗号を使って安全性を高めている。
いまやネットの利用者は、本人が知ろうが知るまいが公開鍵暗号に依存している。しかし公開鍵暗号は無謬とは言えず、それをとりまくテクノロジーをにらみながら改良が続けられている。シンギュラリティを占うなら必ず理解しておきたい技術だ。
なお公開鍵の読みは「こうかいかぎ」だ。重箱読みが落ち着かないので、自分の脳内では「こうかいけん」と読んでしまうのだが、これは少数派らしい。
2章 RSA暗号の試作
公開鍵暗号にはいろんな種類があるが、本稿ではそのひとつ、RSA暗号を紹介しよう。
RSA暗号は1977年に発明された最初の実用的な公開鍵暗号で、現在も広く使われている。「RSA」は開発者の三人、リベスト、シャミール、エードルマンの頭文字だ。
RSA暗号の使い方を、まずたとえ話で説明しよう。
アリスは霊夢(れいむ)に秘密の手紙を送りたい。治安の悪い世界なので、普通に郵送すると誰かに見られてしまう心配がある。そこで――
(1) アリスは霊夢から空の手提げ金庫を取り寄せる。
(2) アリスは金庫に手紙を入れ、施錠して霊夢に返送する。施錠は南京錠のように、押し込むだけでロックする。つまり手紙を宅配ボックスごと配送するようなものだ。
(3) 霊夢は届いた金庫を、自分だけが持っている解錠用の鍵で開く。この方式だと合鍵を共有しなくていいので鍵配送問題は起きない。
公開鍵暗号はこれをデジタル通信上でおこなう。数学的な処理をするので、文章も鍵もすべて数値で表現する。では金庫にあたるものはどうするかというと、それが思案のしどころだった。数学者たちが「不可能かもしれない」と悩みながら何年も頭をひねって考案したものだ。
なぜ難しいかといえば、デジタル通信は物理的な金庫とちがって、ユーザーと悪者が対等な立場にあるからだ。ユーザーにできることは悪者にもできてしまう。どうにかしてユーザーと悪者を差別化したいが、共通鍵方式ではコストもリスクも大きすぎる。
RSA暗号はその困難を、後述するトラップドア関数で解決した。
受取人の霊夢は施錠用の鍵と解錠用の鍵を作り、施錠用の鍵を一般公開する。SNSのプロフィール欄に書いてもいい。これが公開鍵だ。RSA暗号の場合、公開鍵は2つの数値からなる。
いっぽう解錠用の鍵は秘密鍵といい、これも2つの数値からなる。秘密鍵は霊夢が手許で秘密に保管する。
これで準備ができた。通信手順は以下の通りだ。図は家系図の「父と母から子が生まれる」ような類推で読んでほしい。「公」は公開鍵、「秘」は秘密鍵、緑の縞模様は暗号文を示す。
(1) アリスは霊夢の公開鍵を使って、自分の通信文を暗号化する。
(2) アリスはその暗号文を霊夢にメールする。メールは盗聴可能だが、暗号化されているので内容は理解できない。
(3) 霊夢は届いた暗号文を自分の秘密鍵で復号する。これで平文がでてくる。
霊夢の公開鍵はアリスだけでなく、誰が使ってもかまわない。同じ鍵セットで霊夢あての暗号通信をすべてまかなえるのもRSA暗号の大きな長所だ。
しかしRSAの公開鍵と秘密鍵はジグソーパズルのように噛み合った関係にあるので、悪者に重大なヒントを与えているように見える。この公開鍵から秘密鍵を逆算できないだろうか？ もしそれができるなら、公開鍵暗号は役に立たなくなる。
それをできなくしているのがトラップドア関数だ。RSA暗号ではトラップドアに素因数分解を利用する。
素因数分解は中学1年で習う、とても簡単なものだ。任意の正の値を素数の積で表せばよい。素数とは2以上の整数で、1とその数以外では割り切れない数のこと。2, 3, 5, 7, 11, 13, 17, 19 … と無限に続く。
たとえば187を素因数分解すると、こうなる。
187 = 11 × 17
126なら3つの素数になる。
126 = 2 × 3² × 7
素因数分解を筆算でやるときは、小さい素数から順に割っていく。3～4桁の値ならすぐ終わる。しかし大きい値になると大変なことになる。うちのPCにやらせてみると、60桁ぐらいで長時間考え込むようになった。
細田守監督の映画『サマーウォーズ』のクライマックスシーンで主人公が筆算で大きな計算をする場面がある。彼はRSA暗号を破ろうとしていて、1000桁の素因数分解に挑んでいるのだった。1000桁になるとスパコンでも難しいと思うが、有限時間ではあるので、魔法や超能力よりは現実的かもしれない。
現在、よく使われているRSA暗号はRSA-2048という規格で、鍵長は2進数で2048桁になる。10進数だと600桁ぐらいだ。計算にはスパコンで数十年かかると言われ、現時点では破られていない。
うちにスパコンはないが、Pythonでプログラムを組み、小さな素数でRSA暗号を試してみた。プログラムはこちらに置いた。世紀の大発明なのに、作ってみると40行ほどの簡単なものになった。上のスクリーンショットは左側にプログラム、右側にprint文の出力結果が出ている。
手順はというと、まず2つの素数p,qを用意し、秘密鍵にする。
その2つの素数を掛け合わせた値nと、2つの素数から導いた値rを公開鍵とする。rは(p-1)(q-1)と互いに素な値から適当に選ぶ。
上の最初の例だと秘密鍵は11と17。公開鍵はnの187とrの3になる。
暗号化したい文字は数値で置き換えて扱うから、ここでは簡単に39という1個の数値を「平文」としよう。これでもアルファベット1文字ぶんにはなる。
暗号文は 平文をr乗してnで割った余りになる。
39のr乗 ÷ n の余りが暗号文だ。
Pythonで書くと 39 ** 3 % 187 で、暗号文は40になる。
暗号文を復号するには、秘密鍵の2つと、そこから導いたdを使う。dはここでは27になる。dの算出方法は、まだ理解できてない部分があるので、詳述しない。理解しないまま書いたプログラムは、試した範囲では正しく動いているが、値によっては破綻しそうだ。
暗号文をd乗してnで割った余りがもとの平文になる。
Pythonで書くと 40 ** 27 % 187 で、めでたく平文の39が出てきた。
悪者がこの暗号文「40」を盗聴したとしよう。公開鍵187を素因数分解して秘密鍵11と17を得れば復号できる。実用のRSA暗号は大きな素数を使うために時間がかかるだけで、解読できないわけではない。スパコンを何十年もぶん回して電気代を何百億円も払うなら、可能だ。
最後にRSA暗号が持つ重要な機能、デジタル署名について説明しよう。悪者がやりそうなもうひとつの悪事は、手紙の差出人としてアリスを詐称するケースだ。それを防ぐのがデジタル署名で、とても巧妙な仕組みになっている。霊夢向けの暗号文の中にアリス向けの暗号文を入れ子にする、というアイデアだ。ちょっと複雑だが、以下の説明を図の番号とつきあわせながら理解してほしい。
(1) アリスは自分用の公開鍵と暗号鍵を作る。そして自分の署名を自分の秘密鍵で暗号化する。普通なら暗号化には公開鍵を使うのだが、デジタル署名では逆だ。RSA暗号の鍵は逆向きにも使える。
(2) アリスは暗号化したデジタル署名を霊夢あての手紙に書き加える。
(3) (2)を霊夢の公開鍵で暗号化し、メールする。
(4) 霊夢は届いた暗号文を自分の秘密鍵で復号する。するとアリスの平文のあとにデジタル署名の暗号文が出てくる。
(5) その暗号文をアリスの公開鍵で復号すると、平文の署名になる。アリスの公開鍵で復号できる署名を作れるのは秘密鍵を持っているアリスだけなので、署名は本人のものだと証明できる。
もしメールを悪者が盗聴して霊夢に送りつけても、同じメールが届くだけだ。悪者は中身を解読できないし、破綻なく改竄することもできない。
1977年に発表されたRSA暗号の最初の論文タイトルは『デジタル署名と公開鍵の暗号体系』で、デジタル署名の実装が最初から考慮されていたことがわかる。セキュアな通信に何が必要か、関係者はこの時点で見通していたわけだ。
当時インターネットはまだ存在せず、その前身であるARPANETの時代だが、暗号技術の要件は変わらないということだろう。そしてRSA暗号の技術が確立していたからこそ、多くの実業家や企業はインターネットを「使える」と判断し、投資したのだと思う。
3章 暗号の数理と宇宙
今回、暗号技術をとりあげた経緯を語ろう。
2週間ほど前のこと、廊下に積み上げた本を整理していたら『暗号の数理』(一松信、講談社ブルーバックス)がでてきた。30年ぶりの再会だった。私はこの本でRSA暗号の使い方を理解したのだった。
『暗号の数理』の刊行は1980年。RSA暗号の発明が1977年だから、最初期の一般向け解説書にちがいない。
著者の一松信は日本を代表する数学者で、戦時中、東大理学部から学徒動員で軍の暗号研究に携わった経歴を持つ。「公開鍵暗号」という訳語も氏が提唱している。
一松信は『サイエンス』誌(現『日経サイエンス』)1977年10月号に掲載された記事『新種の暗号』の訳者でもある。この記事はRSA暗号を世界に知らしめ、大反響を巻き起こした。記事は『別冊サイエンス 数学ゲームI』に採録されている。この本も自宅から発掘できた。
その新装版『マーチン・ガードナーの 数学ゲーム 1 (別冊日経サイエンス 176) 』も絶版ではあるが、まだ新しいので入手しやすいだろう。
手許にある『暗号の数理』は15刷で、刊行は1991年。そのタイムラグからわかる通り、私は周回遅れでこの大発明に関心を持ったわけだった。そして1992年、富士見ファンタジア文庫『クレギオン ヴェイスの盲点』に公開鍵暗号のエピソードを盛り込んだ。といっても登場人物が「これは公開鍵暗号だ」と理解して操作するだけで、数学的に発展させたアイデアはでてこない。
私は『暗号の数理』を読んではいたが、数学的な記述はスキップしていた。本文にもこんな前置きがある。
数学的基礎として、しばらくの間、整数論の初歩の解説を挿入する。それらについて周知の方や、数学は大嫌いだが、RSA体系について書いてあることは信用するという方々は、以下しばらく(181ページまでの)数学的基礎の部分をとばしても差し支えない。
「信用するという方々」というくだりにはユーモア、皮肉とともに、証明を積み重ねて進む数学者の矜持が読み取れる。だが当時の私は楽な道を選んだ。
数学的基礎からRSA暗号の数理までの記述はほんの40ページくらいだ。現在の私は30年前より分別があるので「よし、今こそこれを読んで、プログラムが組めるぐらいにはRSA暗号を理解しよう。そのことをケムールの連載記事に書こう」と思い立ったわけだった。
「40ページくらいなら」と軽く考えて始めたのだが、やってみると手強かった。私は予習なしで整数論の大海に放り出された。弾道や軌道運動などの物理に絡む数学は多少心得があるのだが、整数論は正直、1ミリも知らなかった。
その40ページは読者がRSA暗号を理解するのに最低限必要な知識を網羅している。NP完全、ナップザック問題、時計代数、モジュロ演算、互除法、有限体、フェルマーの小定理、オイラーのφ関数、中国の一古定理、等々。
限られた紙幅に1行の無駄もなく押し込んであるので、読み飛ばして先に進むと必ずわからないことが出てくる。「なんだこれ。さっきのとこか？」と引き返して読み直すことがたびたびあった。勉強を始めて2週間になるが、まだ全部は理解できていない。
しかし整数論の面白さはつかめた。どれくらいつかめたかは不明だが、現に面白いのだから、ゼロでないことは確かだ。
なぜ数学者は素数を愛し、素数をプリントしたTシャツを着たがり、カレンダーやナンバープレートを見ては「素数だ」とつぶやくのか。たぶん、素数は数における元素だからだろう。元素の種類は3桁どまりだが、素数は無限にある。素数を法にしたモジュロ演算――整数の割り算をしてその余りを得る計算――をすると、その素数ごとに小宇宙が生まれ、面白い性質がぞろぞろでてくる。モジュロ演算がわかるとフェルマーの小定理やオイラーのφ関数も、まあ何をしているかぐらいはわかる。何をしているかがわかると、なんでこんなことをしたんだ？と新たな疑問が立てられるから、どんどん面白くなってくる。
ちょっとかじったくらいでこんなことを言うのはおこがましいが、手頃なゴールを定めてそこに至るツリーを短期間でたどるのは、いい勉強法かもしれない。『暗号の数理』の40ページのように、精緻に組み立てられたテキストがあれば、だが。
Twitterでは『暗号の数理』で数学の面白さにめざめたという人もみかけた。『暗号の数理』はKindle版があるので、まだの方は挑戦してみてはいかがだろうか。
整数論は純粋数学、ピュア・マスなどと呼ばれ、暗号技術に使われるまでは役に立たない学問の代表格、数学者の道楽とみなされていた……ような気がする。無理解な大衆から見ての話だ。
それが現在社会の基盤になったのは驚くべきことだが、実は必然かもしれない。浮世離れして見える量子論や相対論も日常生活にがっつり関わっているから、整数論もそうなのだろう。基礎科学は万物と関わりを持つものだ。
その量子論がRSA暗号を脅かしていることも興味深い。
量子コンピューターの応用にショアのアルゴリズムというものがある。これは量子現象を使って素因数分解を短時間で実行するものだ。
現在の量子コンピューターはごく限られた量子ビットしか扱えず、RSA-2048の鍵長にはまだ遠く及ばない。なんだか景気のいい報道もあるが、イジングマシンとか量子アニーリングマシンとか、「それほんとに量子コンピュータなの？」という、まぎらわしいものがあるのでわかりにくい。
ともかく暗号界には耐量子暗号(Post-Quantum Cryptography)という言葉があり、量子コンピューターが実現しても耐えられる暗号が研究されている。RSA暗号や楕円曲線暗号はショアのアルゴリズムで破られるが、代数曲線暗号や格子暗号は耐性があるとされている。より良い暗号の模索はまだまだ続くだろう。
この記事を読んだ皆さんは、宇宙人と共通の話題を持てたことを喜んでほしい。
数学や物理学は人類と関係なく、この宇宙全体に備わっている図書館のようなものだ。それは宇宙のどこにいても享受でき、りんごを落下させたり三平方の定理を示すなど、つきっきりのレクチャーもしてくれる。我々は海や山や野生生物を指して自然と呼ぶことが多いが、数学・物理の描像こそは真の自然だ。
もし異星文明が存在するなら、彼らも彼らなりのやり方でその書庫を紐解いているにちがいない。そして人類と出会ったら、すぐにこんな会話を始めるだろう。
「あれはもう読んだ？ どうだった？ あなたはどんな暗号が好き？」
(第11回おわり)
野尻抱介
SF作家、Maker、ニコニコ技術部員。1961年生まれ。三重県津市在住。計測制御・CADのプログラマー、ゲームデザイナーをへて専業作家になったが、現在は狩猟を通して自給自足を模索する兼業作家。『ふわふわの泉』『太陽の簒奪者』『沈黙のフライバイ』『南極点のピアピア動画』ほかで星雲賞7回受賞。宇宙作家クラブ会員。第一種銃猟免許、わな猟免許所持、第三級アマチュア無線技師。JQ2OYC。Twitter ID @nojiri_h
