« サマーウォーズの数学・補講 ~数字をアルファベットに置き換える~ | トップページ | ナショナル・プライドの明と暗 ~ロータスT127・コスワース~ »

2013年5月30日 (木)

サマーウォーズの数学

基本的に出不精で、アニメなんかもDVD媒体ですませてしまうぼくが劇場まで観に行った数少ない作品が、09年公開の「サマーウォーズ」だった。当時ぼくは祖父が危篤との報をうけて一家で日本におり (その後容態が落ち着いて当座の危機はなくなったのだが、なんだかんだで一週間ぐらい滞在していた記憶がある)、テレビで連日この映画の宣伝を打っていたのを見ていた。ストーリー的には一般的な家族ものの範疇だと思うが、当時まだ若く純真だったぼくは「夏希先輩かわええペロペロ」という理由だけで劇場に足を運んだのである。そして期待していたよりもずっといい映画じゃないか、ということに感銘を受け、その後マレーシアでDVDを購入して保存決定とあいなったわけだ。

さて、本編内容はネタバレになるので注意しなければならないが、今回の記事に必要な部分を抜粋していくと、おそらく理科オタクである主人公・健二が数学でいろいろする話、ということになるだろうか。彼は高校の物理部に所属しつつ数学オリンピックの代表候補になるという経歴があり、その辺が数学一辺倒で物理はオンチレベルなぼくとはやはりちがうのだが、彼が作中で解く暗号が二度に渡って作品の中で重要な役割を果たすのである。以下、その辺の数学的なお話を、なるべく数学で20点以上を取ったことのない人 (ぼく自身そういう状態だった時期が長かったので人のことをとやかく言うわけにはいかない) にもわかるように解説していきたく思う。例によってネタバレ箇所が多いので、特に「Simacherが観たなら俺も観る!」というようなありがたい方は先に映画を見てきてから読み進めていただきたい。




まず、暗号のお話ではないのだが、冒頭の電車の中のシーンで健二が読んでいる数学書。ページが一瞬大写しになるカットがあるのだが、本文の大見出しに「Shorの因数分解アルゴリズム」 (手元のDVDはマレーシア製のためか解像度がわるく「円数分解」に見えるが、この文脈から「因数分解」とわかる) と読める。Shorというのはマサチューセッツ工科大のペーター・ショア教授、および彼が中心となって1994年に開発された量子コンピューター用の一連の計算アルゴリズム (計算機におけるにおけるアルゴリズムとは、プログラムによって指示される計算の手順のことである。たとえば21という数を得るのに「7に3をかける」とか、「11と10を足しあわす」といった手順をとることができるが、この四則演算の部分がアルゴリズムである。アルゴリズムというととかく複雑なものを考えがちだが、単純な足し算や引き算でもアルゴリズムとして成立することはできる) のことを指すと思われる。量子コンピューターとは、古典的な計算機が電路のオン・オフや電荷の状態によって0と1を形成するのに対して、量子間の重なりあいの状態によって情報を伝達するまったく新しいタイプのコンピューターのことで、現在はまだ理論研究から小規模な試験の域を出ていない (理論そのものはずいぶん前から存在した) が、実用化することが出来ればその強烈な計算速度を武器に、従来型の計算機械を三千年ぐらいぶん回さないと計算できないようなものを比較的短時間で解決出来るようになることが期待されている。見出しにもある通り、ショア・アルゴリズムは大きな数をふたつの約数に分解するためのものである。後でくわしく書くが、この因数分解というのがサマーウォーズ作品内における数学的なテーマのひとつとなっているのである。しかしまあ、高校二年で量子計算機論に手を出すとはたいしたもんである。数学オリンピックの出題範囲は調べてないが、もしかしたら最近は量子計算機の問題も出るのかもしれない。

つぎに、健二が夏希といっしょに彼女の実家へ向かう新幹線の中での会話。健二が数学オリンピック代表候補だったことを知り、「何かやって見せてくれ」という夏希 (ぼくの考えだが、こういう質問は数学にかぎらず、ある能力の持ち主に対する考えうる限り最高にムチャな設問だと思う。自分勝手といわれるかもしれないが、たとえば二ヶ国語以上の言葉ができるとして「何か喋ってみてよ」とか、MMDのソフトがいじれるからといって「じゃあ何か作ってみてくれないか」とか、悪気がないのはわかるのだが、質問される側にとってはその「何か」に大変こまるのである。その意味で健二の切り返しはかなり優秀である。数学ができるというだけでなく、人間的にいわば「コミュ能力」のすぐれた、すばらしい人格の持ち主ということができる) に、健二は彼女の生年月日である1992年7月19日が何曜日かを当ててみせる (日曜日である。ぼくは劇場で観た際にたまたまこれを覚えていた。というのはその一週間前の7月12日がちょうどこの年のイギリス・グランプリのレースデイであったからだ。もちろんすべてのGPの日付を覚えているわけではなく、当時たまたま92年のF1を研究していた縁で覚えていただけである)。彼は「モジュロ演算を使った」といっているが、この「モジュロ演算」とは平たい話、「余りの数の計算」である。たとえば、25は6では割り切れず、6×4=24に1を足した数となる。小学生の数学にも出てくるが、一般的な数学ではこれを「25 mod 6=1」と書く (modは「Modulo」の略)。「25÷6の余りは1である」と読むとわかりやすい。このモジュロ演算を使った公式のひとつに「ツェラーの公式」という式があり、これは正に歴史上のある日付が何曜日であるかを算出するための公式である。健二が使ったのもおそらくこれだろう。詳しい公式や証明はWikipediaに記事があるのだが、例によって一般人が理解するにはあまりにも難解なので、ここでは1582年以降のグレゴリオ暦日付に限った計算法を極力噛み砕いて書く。ある年のm月d日の曜日計算を一般化した式はつぎのようなものである (普通に打つと面倒なので画像を使わせていただいた。ある年の1月と2月は前の年の13月、14月として計算しなければならないことに留意する必要がある)。

ZellerF

ここから算出されるhの取りうる数字は0 (余りなし) から6までの間で、それぞれ土曜日~金曜日に対応している。0が土曜日、以下日曜日、月曜日、…ということだ。1992年7月19日の場合、hの計算は「(19+20+92+23+4-38) mod 7=1」であり、日曜日であることがわかる。最後の「7で割った余り」と、真ん中に3つ存在する「計算結果を超えない最大の整数」(床関数という。たとえば12.7なら12、29.5なら29である) が厄介な以外は普通の暗算の範疇にあるといえる (割り算ではなく掛け算のアプローチでいけば、ちいさい数字の場合もう少し簡単になる。たとえば19÷4なら、4×5=20ということを知っていれば、この床関数は4であることはすぐにわかる)。関数電卓にすっかり甘やかされて、暗算は三桁以内の足し算と引き算以外からっきしダメなぼくから見たら、こんな計算を一瞬でやってしまう健二は数学マンの鑑である。これもつぎに述べるが、この「モジュロ演算」、「余りの数の計算」は、上に述べた「因数分解」と並んでこの作品の数学的テーマとなっているのである。さすがはアニメ屋というか、伏線の張り方は上手いもんである。

さて、つぎに物語の核心部分である。夏希の実家に泊まり込んでいる健二に、携帯メールが送られてくる。開けてみると数字の羅列で、何がなんだかさっぱりわからない。じつはこのメール、作中のSNSシステムである「OZ」の中核部分 (おそらくコード) を保護している2056桁の暗号であり、それを見ぬいた健二は紙と鉛筆を取り出して夜が明けるまで解読に勤しむ。解読を終えた彼の前に、一組の文字列が現れる。平文は大文字、小文字混じりの文で、「the magic words are squeamish ossifrage ... (続き失念。to know you dont know anything...だったかもしれない。文意的にはソクラテス「無知の知」のことか)」と読める。彼はその文章をメールの主に送り返すが、けっきょく末尾の一文字をまちがえていたことが後にわかる。しかし同じメールは全世界にばらまかれており、それを55人が解読してしまったことで、翌日OZの中枢は何者かに乗っ取られてしまい世界中が大混乱を来たし…というプロットだ。

数字を文字に変換するというのは、ふるくから暗号の常道であった。これは長いので次の記事で解説する。興味のある方はそちらも読んでみるといいだろう。健二に送られてきたメールも一種の乱数表である、ということが出来る。数字を文字に置き換える方法ではコードブックだとか、「ポリュビオスの暗号表」というものがある。別にAから順に01、02…と番号を振っていってもいいが、それでは小学生にも解読されてしまうだろう。暗号表で数値化したものをそのまま暗号としてもいいが、強度を上げるためにこれに乱数を使った「キーワード」、「鍵語」を組み込んで使う場合が多い。いずれにしてもこの辺の解説をここで書いてしまうと記事が人間の身長並に縦長になってしまうので、どうしても別記事を建てて書くしかないのであるが、今はまあそういうことだと思って納得していただくより他ない。

インターネット上の暗号であることや、平文に対する暗号文の長さ (平文は英字100文字も無いが、暗号文は数字2056桁なのである) を勘案すると、この暗号は単なる乱数表ではなく、いわゆる「RSA暗号」ではないかと推測される。RSA暗号とは、1978年に発表された全く新しいタイプの暗号で、提唱者のリヴェスト、シャミル、アドルマンの三人の頭文字からこう呼ばれ、それまで整数論の大きな分野でありながら実用的価値はまったく無いと考えられてきた素数の研究を一気に加速させた。この暗号は素因数分解の演算が一方向性関数であるという前提に基づいた安全性を有するものである。たとえば、85という数字が5と17というふたつの素数に分解できることは、ちょっと計算慣れした人ならすぐにわかる。しかし、たとえば1009961という数字を見て、それが997と1013という素数どうしを掛けあわせた数だというのがわかるまで、どれぐらいの時間がかかるだろう。素数と素数をかけあわせてある数 (ふたつの数字の掛けあわせの結果として生まれる数を合成数という) を作るのは簡単である。しかし、ある数、特に大きな数を見て、それをふたつの素数に分けられるかどうか判断することや (2を多数回乗じた数字より少しちいさい数、たとえば253-1だとか、そういった数字は比較的分解しやすいとされている)、実際に約数となるふたつの素数を計算によって見つけることははなはだ困難である (現在はまだ不可能とは言い切れない)。トウモロコシを使ってポップコーンを作るのはたやすいが、ポップコーンをトウモロコシのツブツブに戻すのが無理な相談なのと同じである。標準的な演算操作、たとえば足し算や引き算の場合、5に6を足して11を得ることができるし、11から6を引けばもとの数である5を得ることが出来る。このような操作ができず、ポップコーンのように「ある方向に行ってしまったらその逆算が出来ない」操作のことを一方向性関数という。素因数分解はそのひとつだと考えられており、一度素数どうしを掛けあわせて大きな数にしてしまったが最後、それをふたつの素数に戻すことは出来ないのである (厳密には不可能というわけでもないのだが、この場合膨大な時間がかかる、ということである。たとえば明日とか明後日とか来週にミクさんのしまぱんを盗み出そう、というような内容の暗号文が傍受されたとして、それが四十年たってから解読されたところで通常は何の意味もなさないからである)。一方向性関数はあくまで仮設にすぎず、ポップコーンを果たしてトウモロコシに戻せるか否かを立証することは現代数学における最重要な未決問題のひとつでもある (「P≠NP問題」参照) のだが、こと素因数分解という一演算に関しては、その方向の単一性は揺らごうとしている。その原因が、ほかならぬ量子コンピューターなのである。ごく最近にいたるまで、現実的な時間内 (数十年とか数百年ではなく) にある合成数を素数に分解する演算をおこなうための確固たる手順、たとえば分数の割り算とか対数の計算のようなわかりやすい共通のルールは存在しないとされてきた。しかし、2001年になって、IBMが前述のショア・アルゴリズムを用いて、15を3と5というふたつの素数に分解することに成功したのである。計算機の世界においては、基本的にちいさい数である演算を行うことが出来れば、それは大きい数にも通用する。この分野の研究がすすめば、近い将来に劇中に登場するような数千桁という数字のバケモノも分解することができるようになるかもしれない。 ちなみに、前掲した「The magic word is...」の文章は、RSA法の発表に先立って1977年に雑誌に発表された、129桁のRSA暗号の平文である。「Squeamish ossifrage」とは「小うるさいヒゲワシ」の意味だが、これはMITのスラングで「骨折り損」を意味するともいわれる。この平文は1994年になってようやく解読されたのだが、健二に送りつけられた暗号が (通常の乱数表ではなく) RSA暗号数であることの根拠ということもできなくはない。

さて、RSA暗号の基本的な解き方である。RSA暗号は、それより前に提唱されていた「ディフィー/ヘルマン鍵転送」という、暗号の鍵の一部を公開するタイプの暗号モデルを現実に行うための方法である。わかりやすくお話するために、ルドルフ・キッペンハーン著「コード・ブレーキング」に記載されているモデルを借用させていただく。仮に、ミクさんがルカさんに暗号の手紙を書くとしよう。ミクはまず普通に手紙を書いて、それを暗号化する。いわば手紙を箱に入れてカギをかける操作である。この鍵の錠前がもし普通の南京錠なら、ルカは手紙を取り出して読むのにミクの持っているのと同じ鍵が入用である。暗号においては、この鍵は例えばスパイが持っている乱数表とかコードブック、ということになるが、この方法はスパイが捕らえられた場合にかなり危険であるし、本部側とスパイで数字の表や本をあらかじめ共有しておかなくてはならない。そこで特別製の南京錠を使う。現実にこんな錠前があるのかどうかわからないが、鍵穴が三つ開いた錠前を想像していただきたい。大きな鍵穴に対応する鍵をN、ちいさな2つの鍵穴に対応する鍵をそれぞれE、Dとする。現実には「鍵」とはもちろん数字である。この錠前をNとEで施錠したとすると、開けるにはNとDが必要になるのである。NとEの数字は「公開鍵」と呼ばれ、これは誰でも入手できる。というか、ルカに暗号の手紙を書きたい人は持っていなければならない。Dの数字は「秘密鍵」と呼ばれ、受信側は絶対にこの数字を秘匿しなければならない。ミクは手紙を書き、箱に入れてこのヘンテコな錠前で鍵をかける。彼女はNとEで施錠したから開けるにはNとDがいるのだが、彼女はDの鍵を持っていない。箱に鍵をかけた瞬間から、ミクは自分の手紙を取り出すことすらできなくなるのである。これが一方向性関数の応用である。手紙の入った箱をもらったルカは、金庫からDの鍵を取り出して箱を開け、手紙を読むことになる。これがディフィー/ヘルマンの提唱したモデルである。

現実にはN、E、Dとも数字なのは前記のとおりだが、この数字の求め方を以下に述べる。まずふたつの素数を用意 (仮にp、qとしよう) する。計算を簡単にするために、先の5と17を使うとしよう。p=5、q=17で、これをかけ合わせると85という数になる。これがNである。もうひとつ、ここでは補助数と呼ばれる数、仮にzを計算する。zはp、qよりそれぞれ1少いだけの数を掛けあわせたものである。この例では5-1=4、17-1=16なので、z=4×16=64である。この補助数はEの選定に使われる。Eはzと共通の約数を持たない任意の数である。zが例えば2と3と4と6で割り切れるとすると、Eはこれらの数で割り切れない数でなければならない。p、qがともに奇数であり、それに1を減じた数の乗算であるzは必然的に偶数となるので、Eは奇数でなければならないことがわかる。zよりもちいさく、zの約数ではない素数がEに適している。64よりちいさい素数はいろいろあるが、ここでは仮にE=5とする。秘密鍵Dはけっこう複雑な計算になるが、DとEを掛けあわせ、その数をzで割った余りが1となる数、とされている。DE mod z=1となる数字、というわけだ。上の例から5D mod 64=1という数式を導出できる。数字がちいさいので、「65 mod 64=1」、したがって「5D=65、∴D=13」という算式は比較的すぐに浮かぶが、大きい数字となるとこれはもう大変である。人によってはこれの数式を理解するのに半日かかるレベルである。文字で書くのが面倒になったのでまたしても数式画像で勘弁していただきたい。上の曜日計算のところで述べたように、「余りの数の計算」がどっさり出てくるのである。

RSA1

さて、これでN=85、E=5、D=13という三つの鍵が出揃った。これである数字を暗号化するとしよう。試しに「24」という数字を暗号数とする。ミクはNとEを使って暗号化を行う。この暗号数は平文数のE乗をNで割った余りを求めることで算出する。ここでは245 mod 85である。答えは79だが、NやEが大きいと (実際これらの鍵は十分大きくないと意味が無い) 数字が限りなくでかくなっていくので、一回の掛け算ごとにそれをNで割った数字を求め、それにさらに平文数をかけてNで割る操作を繰り返すこともできる。ルカがこの「79」という暗号数をNとDで翻訳するには、暗号数のD乗をNで割った余りを求めることになる。この場合は7913 mod 85で、答えは24である (関数電卓かコンピューターに計算をやらせて見るといいだろう)。平文数が得られたことがわかる (証明略)。

以上の数式からわかるように、この暗号の解読のキーポイントはNをpとqに分解できるか否かにかかっている。pがわかればqは算出できる。p、qが得られればそこからzを計算して、NとEを使ってDを割り出すことができ、暗号は解読されてしまうのである。「素因数分解の一方向性」とはつまりこういうことなのである。現実では、Nは100桁以上ないと安全ではないとされている。作中のOZは現実世界とひじょうに密接したシステムで、たとえば水道局員のアカウントで仮想ネットワーク上から水圧を上げ下げできたり、JR関係者のアカウントなら鉄道の信号をいじったり、といったことが出来ることが示唆されている。セキュリティは当然、NSAかCIAのネットワーク並に強固でなければならないはずである。もし健二に送られてきた暗号がRSA暗号の公開鍵 (上のモデル内のN) だったとすると、彼はまずそれを素因数分解してpとqを得、そこから補助数zおよびもう一方の公開鍵Eと秘密鍵Dを計算して暗号を翻訳し、その暗号数をさらにアルファベットに転置して平文を得る操作をしたことになる。

現実世界において古典的計算機がおこなった素因数分解でもっとも大きなものは、2010年1月に分解された232桁の合成数である。この計算には300台のコンピューターを用いて三年かかったという。その十倍に近い2056桁の数とは、とてもじゃないが生身の人間が一晩で分解できるようなものじゃないことは確かである。そのうえ、暗号数を導出したとしても、それをアルファベットに転置する法を知らなければお手上げである (アルファベット順に番号を振っていくタイプの転置なら簡単だが…)。しかし作中では恐ろしいことに、全世界規模とはいえ55人もの人間がこれを一晩で分解し、平文を得ているのである (もしかしたら暗号数を平文数に戻したものだけ送った人もあったかもしれないが)。そしてさらにおっかないことに、物語終盤で一分一秒を争う緊迫した場面になった際、ハッキングされたシステムが矢継ぎ早に突きつけてくる暗号数 (こちらの桁数は明らかではないが、数字の量から少なくとも100桁前後はあると思われる) を次々に筆算で解読して転置し (キーボードのテンキー部分ではなく文字盤部分を連打していたから間違いない。もしかしたら本当数字だけ打っていて、あの場面は作画ミスか何かだったとも言えるが)、果ては切羽詰まって暗算で平文を入力していた (予告編やCMでも繰り返されていた、「よろしくお願いしまぁぁぁあああすッ!」のシーンである)。いくら鼻血を出したところで、10桁以上の素因数分解にz、E、Dの算出を全部暗算でやるのは無茶苦茶である。鼻血だけで失血死してもおかしくない (いちおう、冒頭の方のシーンで健二が量子コンピューターのアルゴリズムを勉強してはいるが、あれはあくまでコンピューター用の計算式であって、人間がそのまま計算することは想定外である)。あちらの世界では脳に量子コンピューターを埋め込む義体化手術でも流行っているのだろうか。ちなみに、もし量子コンピューターが実用化されて、数千桁の数字を分解できるようになったとしても、同時にさらに大きな合成数Nを計算する能力も得られるはずだから、RSA法をすぐに過去の遺物とすることはできない、という人もある。確かにそうかもしれないが、それならそれで、量子コンピューター人間が一晩で解読してしまうようなヘナチョコな暗号をそんな大事な所にほうっておくべきではないのである。2000桁が解読されるなら2万桁とか、あるいは20万桁の暗号で出直してこい (…これまた大いなる余談だが、筆算といえば映画「アポロ13」の中で、宇宙船と交信している宇宙センターのスタッフが再突入時の軌道計算の検算をつぎつぎに筆算で行いクリアーを出すシーン、あの雰囲気がたまらなく好きである。レースでのピットワークのような、一糸乱れぬ動きの気迫のようなものを感じられるシーンである)。

作中では、これらOZの乗っとり事件やその後のAIの暴走は、米軍によるハッキングAIの実験の事故によるもの (ここまでの大騒ぎになるとは米軍当局も想定していなかったという描写があるので、もともとはごく内輪の実験だったのだろう) とされている。この一件で奇跡的に死亡者は出なかったとされているが、もし健二が量子コンピューター人間でなかったら日本は滅亡していたかもしれないのである。作品は後日談まで描写してないのだが、その後米軍がかなーりバツのわるい立場に陥ったであろうことは想像に難くないだろう。OZというシステムも、システム内のアカウントはその持ち主の権限に連動しているというが、システムというのは決して万全なもの足り得ないのは自明である。仮想システムという、「地に足のついていない」ものに依存することのダウンサイドをも、この作品は間接的に描いているのではないか。最重要な部分が一晩で侵入されることが想定内であったかどうかにかかわらず (どっちにしても大問題なのだが)、特に人命が関わってくるものを人の手を経ずに操作するのは絶対に危険である。

山下達郎がはかなげに美しいスキャットで歌う「僕らの夏の夢」でこの作品は幕を閉じる。ぼくはこの歌が大好きで、本編が終ってもエンドロールをきき終えるまで席を立たなかったぐらいだ。主題歌や全体の雰囲気も含めて、おすすめしたい映画である。それにしても、明らかに常人の数千倍の計算能力を持つと思われる量子コンピューター男の健二ですら代表選考に落ちた数学オリンピック日本代表とは、一体どんなスタンダードが要求されるポストなのだろう…。

« サマーウォーズの数学・補講 ~数字をアルファベットに置き換える~ | トップページ | ナショナル・プライドの明と暗 ~ロータスT127・コスワース~ »

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/1322474/51832043

この記事へのトラックバック一覧です: サマーウォーズの数学:

« サマーウォーズの数学・補講 ~数字をアルファベットに置き換える~ | トップページ | ナショナル・プライドの明と暗 ~ロータスT127・コスワース~ »

フォト
無料ブログはココログ

リンクリスト

  • Kumaryoong's Paddock
    ソビエト時代の東側諸国におけるモータースポーツ活動について書かれているたいへん誰得なブログ (褒め言葉)。この辺の史料を日本語でまとめたサイトって史上初かもしれません。
  • 作った静止画一覧
    主にMMDで作った静止画を上げています。最近はこっちの頻度のほうが高いですね。
  • Racing Sports Cars
    ル・マンや旧WEC/WSPC/SWC、さらには旧WCMなど、スポーツカー・レースの参戦車両の膨大な資料写真を有するサイト。ドライバー別・車種別検索機能完備。F1もちょびっとだけあります(70年~82年)。
  • F1-Facts
    1950年イギリスGPより、F1に関する全記録を蒐集・公開しているサイト。各年度リザルトページからマシン一覧・写真ページに飛ぶことができます。あなたの知らない名車に出会えるかも。IEは右クリックでの画像保存が出来ないので、PCに保存する際はFireFoxなどを使用してください。
  • 誰得 (boulog)
    謎多きF1マニア(?)、bou_ckさんのブログ。「Wikipediaに載ってないような脳内資料置き場」を標榜するだけあって、その名に恥じぬディープ過ぎるF1マシン解説!Wikiどころか、ネット上にもそうそう無いようなマシンが目白押し。ちなみに「誰得」とは「誰が得するんだこんなもん」的意味合いのフレーズ。 2015.12.13追記: このほどYahooブログからfc2ブログに移転されました。
  • 作ったもの一覧。
    私の動画作品一覧です。気力の低下と更新頻度の低下はすべからく連動しています。
  • アカクテハヤイ フェラーリエフワン
    沖縄在住のフェラリスタ、Shigeoさんのブログ。1日1更新(原則)でフェラーリのさまざまな話題を取り扱います。レア物のフェラーリミニカー募集中だそうな。
  • METMANIA
    私の作るペーパークラフトの大半はここからきています。ヘルメットのぺパクラって多分ここにしかありません。