理系男子が世界一輝くアニメ映画(RSA暗号)
こんにちは。赤沢です。よろしくお願いします。 本日はあの超人気アニメ映画に出てくる「暗号」がどんなものなのか解読していきたいと思います。 暗号理論は大学で勉強しますが、話は完全に整数論の単元なので3月まで受験生だった大学1年生にはぜひとも読んでもらいたい内容です(いずれ大学入試で必ず出題されると私は考えています)。 ではいってみましょう。
健二 (サマーウォーズ)
健二「先輩の誕生日いつですか？」
夏希先輩「7月19日。平成4年の。」
健二「日曜日です。1992年の7月19日は、日曜日でした。」
夏希先輩「・・・(何やこいつ)」
2009年8月1日に公開された細田守監督のアニメ映画「サマーウォーズ」。 東京のとある高校に通う冴えない理系男子、小磯健二は先輩である篠原夏希から夏休みにバイトを頼まれ、夏希のおばあちゃん家に一緒に泊まりに行くことになります。 泊まった日の夜、健二の元に数字が羅列された謎の暗号メールが送られてきます。 数学に関しては健二は数学オリンピックの補欠に選ばれるくらいの実力がある健二は、一晩でその暗号を解いてしまい解答を送り返します。
翌日、健二が目覚めると世界が大パニックになっています。 世界中の人々が利用している登録者10億人以上のインターネット上の仮想世界「OZ」のセキュリティ暗号を解いた人がいるらしく、それによって人工知能「ラブマシーン」に世界が乗っ取られてしまいます。 それによってOZと密接に連携していた現実世界の各種インフラがストップし、挙げ句の果てにはおばあちゃん家に小惑星探査機が降ってくることになります。 大混乱の最中でラブマシーンを止めるために、健二は立ち上がります。
健二とRSA暗号
健二はOZのセキュリティ暗号を最初のメールで送られてきた時に1回、小惑星探査機の軌道をズラす時に3回、計4回解いています。 ここで用いられている暗号はRSA暗号と呼ばれ、ネットワークセキュリティで実際に現在も広く使われている暗号方式です。 RSA暗号はどのような暗号方式でどのように使用されているかは様々なサイトで紹介されているので、ここでは健二がいかにして解いたか、すなわち解読方法のみに焦点を絞って話していきたいと思います。
RSA暗号の解読
健二に送られてきた暗号はとってもとっても長い数字の羅列だったのですが、説明を簡単にするために次のようなものだったとします。
020144130115e51n11
健二はこの暗号を見た瞬間に(RSA暗号だ！)とピーンと来たみたいですね。変人ですね。
このような暗号文が与えられた時、RSA暗号を解読する手順は次の通りです。
次のセクションからそれぞれ詳しく見ていきます。
暗号文を区切る
暗号文を一目見るだけでは分かりにくいので、意味のある単位で区切っていきます。 まずeとnというアルファベットが入っていますが、これはe51、n11と区切って読むことができ、e=51、n=11としてRSA暗号で使用される2つの数字eとnの値を表しています。 また、この暗号はA=01、B=02、...Z=26、のようにアルファベットを二桁ごとの数字に割り当ててあります。 つまり暗号文を区切ってみるとこのようになります。
(暗号部)02 01 44 13 01 15, e=51, n=11
※これは暗号化されているのでこのままアルファベットに当てはめてもダメですよ(BA?MAOとかいうワケの分からない文字列になります)。 この見やすくなった暗号をこれから解読していきます。
秘密鍵dを求める
暗号文からeとnを取り出せたらいよいよ暗号を解くための鍵を求めていきます。 RSA暗号におけるeの値は、必ず2つの素数の積となっています。(ここめちゃめちゃ大事。) それらの数字をp, q(すなわちe = pq)とすると、RSA暗号では解読に必要な秘密鍵dは次の式で求められます。
d = {(p-1)(q-1) + 1} / n
今回はe=51なのでこれを素因数分解し、p=3、q=17とします。 n=11なので秘密鍵d = {(p-1)(q-1) + 1} / n = 3と求めることができました。
秘密鍵dを使って暗号を解読する
秘密鍵dを求めることができたら暗号部の復号作業に入ります。 暗号部で区切られたそれぞれの数字をd乗し、それをeで割った余りが元の数字となります。 最初の区切られた数字は02で、d=3、e=51なので2の3乗を51で割った余りを計算します。
23 / 51 = 0 余り 8
(合同式で書くと23 ≡ 8 (mod 51))
この8が復号された値となります。 「02」と書かれていたのは実際は「08」が暗号化されたものだったんですね。 01、44、13、01、15に対しても同様の操作を行うと、復号された数字はこのようになります。
08 01 14 04 01 09
これを先述したA=01、B=02、...Z=26として割り当てるとこのようになります。
HANDAI
見事暗号文を解読することができました。
健二が解いたRSA暗号
今までのセクションでは、RSA暗号を比較的簡単な例を用いて解読してきました。 それでは実際に健二の元へ送られてきた暗号を見てみましょう。
長すぎて見切れてますが、よく見ると数字の羅列の中に一文字だけちゃんとeが入っているのが確認できます。 nの記載は無いようですが、nは昨今では65537を使うのが一般的みたいなのでn=65537として解読していきましょう。
どんなに暗号が長くなっても皆さんはもう解読方法を知っているので解読できるわけですが、上記の手順の中で一番の肝となる作業はどこかお分かりでしょうか。 それは「秘密鍵dを求める」セクションでさらっと書いた次の一文です。
今回はe=51なのでこれを素因数分解し、p=3、q=17とします。
私がさらっと書いたので皆さんもさらっと読み流したと思うのですが、健二の元へ送られてきた暗号文のeは次の値です。
e = 765434576345637173823138479813768765238613741311236937264827654778277325473898928152422542515522536131313315113131436465191945461216494600604573790464767487277872182954748299792393745245635321521251762851642417215462185215216524128156631535133635135624373234146484945914624245144655937545243151552364728646254632586421653765268752146364216452966051582166316165298691556167867525411656512513466425667026216616514563466741256352312000214153442514256547456176523156416857441156514555136515571345216351461342355314575145551352534665275245434123524164512514854135513552515115617195661675681735681361373613725382416248275264278352381658327184562416554631567452166375415676516659156451553145235234613252553232516852127126451621572321315221367251321433642212341623226546564323221637261423214278263167424542351254254143654215461524423554259418149422453565065652624639606225635206461462565251661258214063232062267640333141325426372633225334823727365243212325634253834253324362370285630743325310023223052360452321456631647857143521514557163023223522423243624702260270285607962516432235723674724715613526215523165518237142314221623715637261634153471
eの値は、必ず2つの素数の積となっているので、秘密鍵dを求めるにはこの長ったらしいeを2つの素数p,qに因数分解しなければなりません。
さてみなさん、どうでしょうか。 これを解くことができないから、このRSA暗号は暗号として今現在も機能しています。 素因数分解は意外と今の技術では解くのが難しく、これほど大きな数値だとスーパーコンピュータを使っても100億年以上かかってします(冗談抜きで本当にかかります)。 なのでこの暗号は「今のところは」安全とされており、世界中でこれを使用したシステムが使われています。 逆に言えば、どんな値でも瞬時に素因数分解できるようなコンピュータが開発されたら、この暗号は全く意味のないものになるってことですね。
よくよく数えてみると暗号文全体は2056桁あり、eは1138桁ありました。 健二は、このeの素因数分解をやっていたのです。 上記の手順に則って、eを素因数分解し、出た素数(これもめちゃめちゃ大きな値)とn(=65537)から導かれる秘密鍵dで暗号部の値をべき乗をした後、その値を再びeで割った余りを求める、という作業を鼻血を出しながら必死にやっていたんですね。 本編の最後ではこの規模のRSA暗号を隕石が落ちてくるまでの10分間で3回、うち最後の1回は何と暗算で解いてしまうわけです。 そりゃあ「よろしくお願いしまぁぁぁぁぁぁす！！！！」ってなるやん。笑
終わりに
本編では全く触れられていませんが、健二がどれほどスゴいことをやっていたか分かって頂けたと思います。 「サマーウォーズ」の見所はおばあちゃんが電話をかけるシーンでもなければ、夏希が「コイコイ！」するシーンでもありません。 鉛筆と頭脳を使って莫大な量の計算をこなし、最初から最後まで一貫して暗号を解き続けたことで世界を救った健二。冴えない理系男子がこれほど頼もしく、大暴れする作品はどこを探しても無いのではないでしょうか。
また夏になると金曜ロードショーでこの映画が放映される日が来るでしょう。 その時に、友達にドヤ顔で「サマーウォーズ」の見所を教えてあげましょう。 そして健二が解いたのがどんなにスゴい暗号か説明する時に、このブログの記事を「どうぞ使って下さい。」 今回はそんなお話でした。 読んで頂いてありがとうございました。
夏希先輩「がんばれ！」
健二「はい！」
