« 三途の川の五合目あたり ~ロータス107・フォード~ | トップページ | サマーウォーズの数学 »

2013年5月27日 (月)

サマーウォーズの数学・補講 ~数字をアルファベットに置き換える~

さて、ぼくが記事「サマーウォーズの数学」のなかで少し言及した「数字をアルファベットに置き換える暗号」。今回はこれを集中的にお話したいと思う。戦争ものの映画が好きな人は、数字の羅列をアルファベットに置き換えるのを考えて「おお、乱数表だ!」とピンときたかもしれない。乱数表は古典的スパイのステレオタイプのひとつであり、今日でも紙と鉛筆で暗号を製作するには欠かせないものである。余談になるのを承知で、数字をアルファベットに置き換えるメカニズムを解説しよう。どうせこのブログの記事なんて、それ自体が大いなる余談の寄せ集めみたいなもんである。

文字を数字に置き換える方法として、一番簡単なのはアルファベット順に番号を振っていくことである。Aは01、Bが02で、Zが26という具合だ。しかしこれでは小学生にも破られるヘロヘロな暗号しか作れないのは明らかである。そうしたものを人は「暗号」とは呼ばない。もう少し頭のいい方法として、「ポリュビオスの暗号表」というものがある。5×5ないし6×6のマス目を作り、そこにアルファベット (25マスの場合、iとjを同じに扱うことが多い。第二次大戦中のナチス・ドイツの同種の暗号では、「j」を「ii」と音記していた。「jagdflieger」なら「iiagdflieger」である。36マスの場合、アルファベット26文字に加えて、必要に応じた十種類までの記号や0~9の数字を入れることができる。ちなみに、この36マス式暗号表はもともと旧制キリル文字三十五文字が入るように帝政ロシア時代の政治犯たちが考案した方法で、政権転覆を企図していた彼らのイデオロギーにちなんで「ニヒリスト式」と呼ばれている) を埋めていく。小学生には破れまいが、頭のキレる高校生あたりに破られないようにするためには、単にアルファベット順ではなく一定の順序にしたがってランダムに埋めるのが望ましい。たとえば十分長く、しかし覚えやすいキーワードを決めておいて、である。キーワードがGROSJEANならば、最初の8つのマス目にG、R、O、…と順に埋めていき、残りをアルファベット順に埋めることになる。Gは11、その隣りのRは12、というふうに、文字はXY座標にも似たふたつの数字の組み合わせで表わされることになる。ちなみに単語間をあらわすのに「00」を使うことが多い。

しかし、これでも実はまだ足りないのである。 上に記した方法である文章を暗号化したとする。25マスの暗号表を使ったとすると、Gは常に11だし、Eは常に21である。平文の文字数にかかわらず、暗号文の文字数がすべて偶数となっていることに気づく人もあるかも知れない。当然である。暗号数はつねに2桁の数字を一文字として扱うからである。偶数に2をかけても、奇数に2をかけても、答えの数は偶数である。これでもし、誰か気のきいたヤツが「数字二文字でアルファベット一文字を対応させているのではないか」と気づいたとしたら、実質的にこの暗号はオシマイである (こういう、元の字と暗字が一対一の対応関係を持つ暗号を、「単一換字式暗号」と呼ぶ。暗号の中ではもっとも簡単に破れる部類である)。英語では、統計学的にある文章の中にもっとも頻出する文字はEであることがわかっている (ドイツ語もそうである。ポルトガル語はAである) し、どの文字がどのぐらいのパーセンテージで出てくるか、ということもすでに知られている。暗号の書かれた言語を推察し、十分な数の暗号文を入手し、片っ端から文字を統計学的に解析していけば、どのアルファベットがどの数字の組に対応しているかがわかり、暗号文は解読できる。この手法は、数字ではなくピクトグラフを使った換字暗号として、ポーの「黄金虫」やドイルのホームズ・シリーズの一篇「踊る人形」にも登場する。それなりの経験や勘、また十分な解読材料があればあっという間に破れることから、この種の暗号は近代以降、しばしば純粋な暗号というよりは一種の判じ物やクイズ遊びのような扱いを受けている。この方式を考えたジュリウス・シーザーはどう思うだろうか。

単一換字式暗号にならないように文字を置き換えるのに、「ヴィジネル式暗号」という方法がある。十五世紀ごろに考案された方式で、この方法でもアルファベットを別の記号に置き換えることに変わりはない。しかし、単一換字式の暗号とはその鍵の扱い方が異なる。単一換字式の場合、暗号の鍵はひじょうにシンプルである。「どの文字がどの文字と入れ替わっているか」がわかれば暗号はすぐに破れる。ヴィジネル式の場合、この「どの文字がどの文字と入れ替わるか」のパターンがひとつではないのである。このような暗号のことを「多表換字式暗号」とか、この理論を完成した人物の名前にちなんで「ヴィジネル式暗号」と呼ぶ。詳しくはこの図表を見てほしい (Wikipediaより画像を引用)。一番上に並んでいる「A~Z」が平文の文字に、その下の一文字ずつずらされたアルファベットの行はそれぞれ上から「Aの行」「Bの行」…と呼び表される。



この方法を最初に考えたのは、ドイツ・シュポンハイムの修道院長だったヨハネス・トリテミウスという男だった。彼は十五世紀の人物だが、時代精神に影響されて錬金術や占星術、秘術のたぐいの研究を行い、「歴史には354年の周期があること」だとか「世界はキリスト生誕の5206年前に創造された」だとか「天使を介して情報を伝達する法があること」といった研究成果を上げたとされる。そのせいで彼は修道院を追い出されてしまったが、その後ヴルツブルグの修道院に落ち着き、そこで六巻からなる暗号に関する書を著した。その中にこの暗号が紹介されている。その後十六世紀になって、この暗号はニヴェルネー公爵大使だったブレーズ・ド・ヴィジネルという男によって完成された。初期の多表換字式暗号は単に「一文字目を暗号表の一行目で、二文字目を二行目で…」という杓子定規なものだったが、ド・ヴィジネルはこの順序に「鍵語」、「キーワード」の概念を与えたのである。しかし当時はまだ単一換字式暗号のシェアが広く、この相対的に複雑な暗号は十九世紀に至るまで日の目を見ることはなかった。

さて、この表を使って暗号化する場合を考える。数字の話はもうすこし後で出てくるのですこしばかり辛抱していただきたい。平文をGROSJEANとする。この方式 (ド・ヴィジネルのやりかた) で暗号化を行う場合、キーワードを事前に取り決めておく必要がある。たとえばCRASHとしよう。暗号化するには、まず平文の一文字目をキーワードの一文字目の行のアルファベットで暗号化する。上図Cの行ではGはIに変換される。同様にRをRの行で、OをAの行で、というふうにして暗号化していく。キーワードCRASHは五文字だが、GROSJEANは八文字である。六文字目以降はキーワードの一文字目に戻って変換を続ける。比較的長い平文の場合、平文をずらっと並べて書いた下の行にキーワードを繰り返して書く (「CRASHCRASHCRASHCRA…」という具合に) と作業がやりやすい。こうしてできた暗号文は「IIOKQGRN」である。

この暗号を解読するには、まずキーワードの字数を知っている必要がある。キーワードを知っていたり、推察でキーワードを導出できれば簡単である。平文がもっと長い文章の場合を考えると、キーワードは五文字しかないのを繰り返して使っているのだから、上の例でもあるように平文の一文字目と六文字目、十一文字目、十六文字目…は暗号表の同じ行で暗号化されていることになる。二文字目と七文字目、十二文字目…についても同様である。そのようにして、同じ行で暗号化された暗字のみを抜き出してならべれば、その文字の羅列はもはや単一換字式暗号と変わらない。十分な長さの暗号文を十分な数だけ取り揃えれば、どの文字が頻出しているかといった統計学的手法で解読できることになる。

ではキーワードの字数を知らない場合はどうするか。これについては、十九世紀のプロイセン軍人であったフリートリヒ・カシスキが画期的な解読法を提案している。ド・ヴィジネルの著作より三百年もあとのことである。文字で説明するのはなかなか難しい方法である。例えば、英語において特に頻繁に現れる綴り字は「he」、「ing」、「th」、「er」といったものがある。ここでは平文中の「ing」という綴り字を考えてみよう。この三文字の綴り字は、キーワード「CRASH」のうちの連続した三文字によって暗号化される。長い文章や特に頻出する綴り字の場合、特定のキーワード部分、たとえば「CRASH」の「RAS」部分で暗号化される回数が多くなる。「ing」を「RAS」で暗号化した暗字がたとえば「NME」だったとすると、暗号文中に「NME」の綴り字が頻出することになる (平文中「ing」と「ing」の間隔の字数がキーワードの字数の倍数となった場合にこうなる)。この「NME」の頭文字部分「N」と、次に出てくる「NME」の頭文字「N」の間の字数をすべて列記する。仮に「NME」が三回出てきて、あいだの字数がそれぞれ25、125、75文字だったとする。この三つの数字は共通して「5」という約数を持っている。キーワードの字数は五文字であることがわかるのである。無論、たとえば平文中のまったく別の「the」という綴り字が、同じキーワードの「CRA」で変換されても同じ暗字「NME」となるかもしれない。暗号文に出てくる共通の綴り字の組み合わせが、常にキーワードの同じ部位を示すとは限らないのである。この辺は解読者の注意力と、ある種の「勘」が必要になる部分である。

このように、ある一定の字数のキーワードを使う暗号は、単一換字式よりはずっと困難ながら、解読は出来るのである。そこで二十世紀初頭に入ってから、このキーワードに無限の長さをもたせようという動きが出てきた。例えばある一冊の本だとか、ある特定の文章をまるまるキーワードとして使う方法である。しかし、文字をキーワードとして使う場合、キーワードの長さはあまり関係がないのである。確かに平文と同じ長さのキーワードを使えば、上に述べたようなキーワードの重複はなくなるだろう。しかしその場合、今度は平文だけでなく暗号文にも統計学的特徴が現れてしまうのである。たとえば平文・キーワードともに英語なら、両方の文章にもっとも頻出する文字はEだから、「E」が「E」の行で暗号化されるということが比較的頻繁に起きる。これでは、有限字数のキーワードより更に困難ではあるものの、解読は可能である。少なくとも安全性が保証される程ではない。

キーワードの「気配」を隠すには、ある特定の自然言語で書かれた文章のような、有意な特徴を持つ要素を使ってはならない。そこで乱数表の出番である。無限に続くランダムな数列をはじめて広く暗号に使用したのは、第一次大戦後のドイツ/ワイマール共和国とされている。敗戦とそれに次ぐ新国家建設にともない、各国に点在する共和国大使館から秘密のメッセージを本国に転送する新しいシステムとして、この乱数を鍵に使うヴィジネル式暗号が使われたのである。ドイツ大使館員には、五桁のランダムな数字が延々五十ページにわたってずらりと記された小冊子を渡されることになった。ひとつとして同じページはなく、また一度使ったページは二度使ってはならず、その場で破棄するよう命じられた。このようなページが「使い捨て」の暗号帳を「ワンタイムパッド」と呼ぶ。戦争映画などでスパイが持っている「乱数表」とはだいたいこれのことである。

乱数表によって平文を暗号化するおおまかな手順はつぎのようなものである。まず、ポリュビオスの暗号表などを使って平文を一度数値化する。その数値化された平文に、乱数表の数字を繰り上がりなしで足し算する。「8+6=4」であり、「7+5=2」である。受信側は、暗号文から乱数を繰り下がりなしで引き算すると平文を得られる。送信方と受信方は、暗号表と乱数表以外に、たとえば「1日に1ページを使う」とか、「特定の日付に特定のページを使う」といった規則も共有する必要がある。乱数表のかわりに、例えば電話帳の下二桁とか統計年鑑の特定の数値のような、無作為な数字が並んだ書籍を代わりに使うこともある。これなら万一スパイが家探しされても比較的怪しまれずにすむ (ランダムな数字がびっしり書き込まれた小冊子は明らかに常人が携帯するような本ではない)。電話帳なら都市名と最初の氏名だけを、統計年鑑なら何ページ目のどの項目かを伝えておけばすむので便利である。太平洋戦争中、日本から秘密情報をソ連に送って逮捕されたリヒャルト・ゾルゲは、ドイツ帝国の統計年鑑を乱数表がわりに使って暗号文を組み立てていた。この方法でつくられた暗号を、日本の特高警察は最後まで解読できなかったという。電話帳や統計年鑑も用意する余裕が無いような場合は、コンピューターの助けを借りる事になる。特定の演算処理によってランダムな数字の羅列を生成するプログラム、いわゆるランダム・ジェネレーターは、暗号以外にもいろいろと便利なことから、現在ではほとんどすべてのコンピューターに搭載されている。この場合、ランダム・ジェネレーターに入力する初期値 (「種」と呼ばれる) を伝達する必要がある。

暗号化の手順そのものはただの足し算、引き算なのだが、原則として一通々々の暗号文がすべてちがう鍵を使うため、他の方式のような鍵を入手しないままでの解読は理論上は不可能である。この方式の暗号が解読されたという場合、だいたいは乱数表が盗まれたとか、スパイ本人が買収されたとか、そういった暗号とは関係ない次元の話であることが多い。しかし例外もある。1953年、ニューヨークで処刑されたソ連のスパイであるジュリウス・ローゼンバーグと妻エセルは、この方式の暗号を米国当局に解読されたことが原因で捕らえられた。ソビエト情報機関が、同じ乱数表を複数回使うというミスを犯したために足がついたのである (この事実は1995年になるまで機密解除されることはなく、そのため当初は夫妻の逮捕は冤罪なのではないかと騒がれた)。また50年代から60年代にかけて、東側諸国のスパイが乱数表を紛失したり、処分できぬまま逮捕される事件があいついだ。彼らの乱数表はじつに巧みに隠匿されており、たとえば「ヴィック」というコードネームで呼ばれた亡命スパイのライノ・ハイハーネンは、内部に穴がくりぬかれたルーブル金貨内に乱数表を隠し持っていた。硬貨に刻印された「C.C.C.P」の文字の「P」の部分にある小孔を針などで押すとフタが開く仕組みだった。アメリカはこの「ソ連流乱数表」の特徴を研究し、たとえば1~5の数字と6~0の数字がほぼ必ず交互に出てくること (タイピストが両手を交互に動かして数字を打っていたということ) や、同じ数字が二度や三度重複することがほとんど無いこと (「同じ数字を繰り返すことは偶然の法則に反する」という考えが無意識のうちに働いていたのかもしれない) を見ぬいた。それは真に偶発的な「乱数」ではなかった。このソ連流乱数の特徴のおかげで、1991年に行われた反ゴルバチョフ・クーデター計画は実行前に挫かれた。首謀者であったクリュチコフKGB長官とヤゾフ国防相の間の交信はアメリカによって解読され、エリツィン方に逐一転送されたのである。乱数は生身の人間に作らせてはならない。乱数とは、袋の中からカードを引くとか、真に客観的な計算処理を行うといった、人間の意志によらない事柄によってのみ生成される数字のことをいうのである。

さて、文字を数字に変換するタイプの暗号については、これぐらいで止めておくことにする。「サマーウォーズ」劇中では2056桁の乱数が健二の携帯電話に送られてきたが、乱数表を使ったヴィジネル式暗号の場合、平文の文字数は基本的に暗号文の桁数の半分である。平文は「The Magic Words Are Squeamish Ossifrage To Know Is To Know You Dont Know Anything」 (後半節は記憶が曖昧なので「だいたいこんな感じだった」という程度。前半は前の記事でも書いたMITの暗号文、後半はソクラテス「無知の知」のことか) と100字弱なので、乱数鍵を使用したヴィジネル式暗号の可能性はほぼ除外できることがわかるのである。

« 三途の川の五合目あたり ~ロータス107・フォード~ | トップページ | サマーウォーズの数学 »

コメント

コメントを書く

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

トラックバック

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

この記事へのトラックバック一覧です: サマーウォーズの数学・補講 ~数字をアルファベットに置き換える~:

« 三途の川の五合目あたり ~ロータス107・フォード~ | トップページ | サマーウォーズの数学 »

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

リンクリスト

  • 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
    私の作るペーパークラフトの大半はここからきています。ヘルメットのぺパクラって多分ここにしかありません。