BeneDict 地球歴史館

BeneDict 地球歴史館
menu

週刊スモールトーク (第72話) チューリングとエニグマ暗号機

カテゴリ : 科学

2006.11.12

チューリングとエニグマ暗号機

■エニグマ暗号機

第一次世界大戦が終わり、ヨーロッパが一息ついた頃、ポーランドはまだ暗号解読に精を出していた。ポーランドは、東西をロシアとドイツにはさまれ、地政学的には最悪の位置にある。そして、第一次世界大戦でそれを身をもって体験した。ドイツとロシアに同時に攻め込まれたのである。

ポーランドは、事が起こる前に、必ずサイン(兆候)があると考え、情報収集に余念がなかった。もちろん、重要な情報はすべて暗号化されている。1926年のある日、ポーランド暗号解読班は、突如、解読できない暗号に遭遇した。ドイツのエニグマ暗号である。

エニグマ(enigma)はドイツ語で「謎」を意味するが、その名に恥じない難攻不落の暗号だった。ただし、方式はオーソドックスな「文字の置き換え」。平文の文字を「変換ルール」に従って、置き換えるのである。当然、変換のルールが鍵となる。平文を秘密の鍵で暗号文に変換すれば、同じ鍵をもつ人だけが、暗号文を平文に戻すことができる。この鍵は、文字どおり、「暗号の鍵」となる。もし、考えられる鍵が数個なら、鍵をすべて試してみればいい。意味のある文章が現れれば、その鍵がアタリだ。

ところが、エニグマ暗号の鍵は
159,000,000,000,000,000,000通り
これを全部試すには、現在のスーパコンピュータでも難しい(2006年現在)。解読できないというのではなく、解読に要する時間が問題なのだ。エニグマ暗号の鍵は毎日変更されたので、解読に1日以上かかっては意味がない。そもそも、この時代、スーパーコンピュータどころか、パソコンもない。

ここで、エニグマ暗号の運用をみてみよう。エニグマ暗号の鍵は毎日変更されるので、あらかじめ、1ヶ月分の鍵(コードブック)が、すべてのエニグマ暗号機のもとに配布される。次に暗号の送受信。例えば、12月24日、A点からB点にメッセージを送るとする。A点とB点では、先ず、コードブックに記載された12月24日の鍵に従い、エニグマ暗号機を設定する。次に、A点でメッセージ(平文)をエニグマ暗号機に入力すると、暗号文が出力される。次に、この暗号文をB点に送信する。B点で受信した暗号文をエニグマ暗号機に入力すると、平文で出力される。すべてのエニグマ暗号機は、同じ12月24日の鍵に設定されているので、正しく変換されるのである。

エニグマ暗号は、毎日、鍵が変更されたが、送信される暗号文が多ければ、その分、解読されるリスクも増大する。そこで、ドイツ軍は、素晴らしいアイデアを思いつく。送信するメッセージごとに異なる「鍵」を使うのである。この方法は、現代の暗号でも使われている。まず、メッセージの先頭に、そのメッセージだけに使う「メッセージ鍵」を、「その日の鍵」で暗号化する。次に、メッセージ本文を、この「メッセージ鍵」で暗号化する。この方法だと、「その日の鍵」が使われるのはメッセージ鍵だけで、メッセージ本文には使用されない。つまり、「その日の鍵」が使用されるメッセージが激減する。こうして、エニグマ暗号の解読は劇的に難しくなった。

■チューリング・ボンベ

1938年、アラン・チューリングは留学先のアメリカからケンブリッジ大学に戻った。第二次世界大戦が始まると、チューリングはブレッチレイ・パークにある暗号解読センターに送り込まれた。エニグマ暗号を解読するためである。ポーランドはドイツに占領され、ポーランドのエニグマ暗号解読の成果は、チューリングのチームに引き継がれた。

暗号は古くからあるが、暗号解読は言語学者の仕事と決まっていた。暗号解読は未知の言語の解読に似ており、言語能力に依存すると考えられたからだ。その良い例が、エジプト象形文字「ヒエログリフ」の解読である。フランスのフランソワ・シャンポリオンが、エジプトで発見されたロゼッタ・ストーンから、ヒエログリフの解読に成功したのである。

シャンポリオンは語学の天才だった。18歳で十数カ国語をマスターし、すでに大学の教壇に立っていた。このような天賦の才と寿命を縮めるほどの努力が、不可能とされたヒエログリフの解読を成功に導いたのである。シャンポリオンは古代エジプト学に多くの業績を残したが、41歳の若さで亡くなっている。

一方、チューリングをリーダーとする暗号解読チームは、数学者を中心に編成された。エニグマ暗号の鍵は、159,000,000,000,000,000,000通りもあり、この中からたった1つのアタリ鍵を見つけるの至難である。総当たりで捜すのは時間的にムリなので、近道を見つける必要があった。そこで、役に立ったのが数学である。

クリスマスに欠かせないクリスマスツリー。ツリーの枝葉には、たくさんの飾りがぶら下がっているが、その1つがエニグマ暗号の鍵だとする。暗号解読をこのツリーにたとえると、ツリーの根元からスタートし、試行錯誤を繰り返しながら、鍵にたどりつくことになる。だが、飾りが159,000,000,000,000,000,000もある巨大なツリーを、一つづつたどるのは気が重い。もっと手っ取り早い方法はないのか?例えば、ツリーを大きく左半分と右半分にわけ、目当ての鍵がツリーの左側にあると分かれば、右半分は調べる必要がない。これだけで手間は半減する。

つまり、総当たりではなく、探索空間をせばめればいいわけだ。そこで、役立つのが数学である。さらに、高速な計算機械を使って、探索時間も短縮する、というのがチューリングたちの手法だった。その計算機械というのが「チューリング・ボンベ」だった。チューリング・ボンベは、電気式のアナログ探索装置で、膨大な可能性の中から「当たり鍵」を15分ほどで見つけることができた。こうして、チューリングは解読不可能といわれたエニグマ暗号を解読したのである。まさに、現代のシャンポリオンであった。

■チューリングマシン(TM)

エニグマ暗号を解読する数年前の1936年、まだコンピュータが影も形もなかった頃、アラン・チューリングはデジタルコンピュータの原型を創り上げた。このアイデアは、チューリングの数学論文の中で提唱されたが、脳が問題を解くプロセスを、仮想コンピュータで真似ようとしたのである。つまり、数学の問題を解く脳をモデル化し、それを仮想のコンピュータに置き換え、これに解かせたのである。こんなこと、一体どうやったら思いつくのだ?!

気を取りもどして、具体的にみていこう。脳は、通常、いくつかの状態がある。例えば、喜・怒・哀・楽。これを脳の内部状態と呼ぶことにする。この内部状態は、脳への入力によって変化する。例えば、「侮辱」が脳に入力されると、内部状態は「怒」に変化する。

このことから、脳は次のような性質をもつことが分かる。

1.有限個の内部状態をもつ(喜・怒・哀・楽)。

2.内部状態が入力によって変化する(侮辱→怒)。

3.どの入力でどの状態に変化するかの手順が内蔵されている(性格?)。

このようなものを「オートマトン」と呼んでいる。有り体には「自動機械」だが、このような機械は世界中にあふれている。認めたくはないが、脳=人間もその1つかも知れない。

アラン・チューリングは、このオートマトンに記憶装置をつけ加え、脳を真似たのである。これがチューリングマシン(Turing Machine)だ。頭文字をとって、「TM」とも呼ばれている。記憶装置は無限長のビデオテープをイメージすると分かりやすい。ヘッドががテープ上を両方向に移動し、データを読み書きするわけだ。

チューリングマシンの動作はいたってシンプルである。まず、ヘッドがテープからデータを読み取り、オートマトンに入力される。次に、入力に従って、オートマトンの内部状態が変化し、その結果がテープに書き込まれる。その後、ヘッドが移動し、テープからデータを読み取り・・・この処理が繰り返される。また、入力と出力の関係はオートマトン内部に内蔵されている。(詳しくはこちら→チューリングマシンの原理

■万能チューリングマシン(UTM)

このチューリングマシンをさらに発展させたのが、万能チューリングマシンである。「Universal Turing Machine」の頭文字をとって「UTM」とも呼ばれる。このマシンは、チューリングマシンの入出力を保持するテープの他に、オートマトンの入力・内部状態・出力の対応表を記録したテープを備えている。第1のテープは、データを読み書きするメモリ、第2のテープはプログラムを格納するメモリに対応している。これは、現在のノイマンマシンにほかならない。ただし、チューリングマシンとノイマンマシンでは構造が全く異なる

チューリングマシンは概念上のモデルだが、実体化すれば、立派なコンピュータになる。アラン・チューリングは、計算可能な問題は、すべてチューリングマシンで計算できることも証明した。ここでいう計算は、広く「問題解決」を意味し、数値計算に限らない。同じことを、数学者ゲーデルが純粋数学で証明したらしいが、専門外なので説明不可。

ただし、「チューリングがどんな問題も計算できる」とは言っていない。「計算可能な問題」という制限つき。ここでいう「計算可能な問題」とは、チューリングマシン上で、有限ステップで実行できる手順が存在することを意味している。具体的には、オートマトンで、
「入力→内部状態→出力」
の対応表がきちんと記述できること。ノイマン型コンピュータ(ノイマンマシン)で言えば、アルゴリズムで表せるもの、プログラムで書けるものである。

■計算不能が意味するもの

チューリングはもう1つ重要な証明をしている。
「チューリングマシンの実行結果は、実行する前に、予測することはできない」
つまり、
プログラムの実行結果を予測する普遍的なプログラムは存在しない
これは非常に重要な事実である。

まず、プログラムの実行結果の正否を判定できないのだから、バグを見つける普遍的なプログラムは作れない。そのプログラムが何をするかは、実行してみないと分からないのだ。年季の入ったプログラマなら感覚的に理解できるが、数学的に証明されたことが重要だ。

こう言うと、プログラマからツッコミが入りそうだ。
「コンパイラがエラーを返すのは、どういうわけ?」
コンパイラは、C言語などのプログラミング言語で書かれたプログラムを、コンピュータのネイティブ言語「機械語」に変換するソフトである。確かに、コンパイラはプログラムのミスを見つけてくれる。だが、コンパイラーは形式上のミスを見つけているだけで、プログラムの「アルゴリズム」までチェックしているわけではない。これは、何ごとも各論でやればうまくいく、というまやかしの一つで、「普遍的法則」ではない。

■万能ウィルス対策ソフト

もし、あなたが「未知のウィルスを検出する」画期的なソフトで起業を目論んでいるなら、チューリングの証明を思いだそう。実行結果を予測するプログラムは作れないのだから、それがウィルスかどうか見分ける普遍的なプログラムも作れない。実行しない限り、ウィルスかどうか分からないのだ。もちろん、実行してからでは遅い。というわけで、万能ウィルス対策ソフトは永久機関と同じ。できそうに見えて、できない。しかも、それが科学的に証明されている。

ところが・・・

最近のウィルス対策ソフトには、未知のウィルスを検出する「ヒューリスティック機能」がついている。それをウリにしているのがウィルス対策ソフト「NOD32」だ。ただし、この機能は、過去に検出されたウィルスに”類似した”プログラムを検出するだけで、アルゴリズムを読み切って判定しているわけではない。既知のウィルスパターンを参考に、各論的に推論しているだけ。重要なのは普遍的か各論的か?前者は真実で、後者はまやかしである。

では、ウィルス対策ソフトは、どうやってウィルスを見つけているのか?じつは、既に発見されたウィルスと照合して判定しているだけ。そのため、ウィルス対策ソフトは、自社サイトからウィルスパターンを定期的にダウンロードしている。次々と出現する新しいウィルスに対応するためだ。

2006年11月現在、世界最高のウィルス検出率と噂されるのが「カスペルスキー」。そのカラクリは、ウィルスパターンの更新スピードにある。カスペルスキーのパターン更新は、1時間~2時間に1度のペースで行われる。こちらは、ウワサでなく本当だ。ということで、無敵のカスペルスキーも、命綱はヒューリスティック機能ではなく、既知のウィルスデータベースである。やはり、未知のウィルスを発見する普遍的プログラムなど夢物語なのだ。

とはいえ、各論的にやっても、そこそこ成果は見込めればそれで十分、という考え方もある。数学には「絶対」が必要だが、商売なら「そこそこ」で十分。一方で、大きな問題も起こっている。ウィルス対策ソフトが高機能化した結果、処理が非常に重くなったのだ。少し前なら、「ノートン」はウィルス検出率は高いが処理が重い、「マカフィー」は検出率は低いが軽いなど、分かりやすい図式があったが、現在は(2006年11月)、どのソフトも重い。それも、非常に重い。処理の重いソフトを使っているなら、DualCoreのCPU、メモリ1GBは必要だろう。しつこいが、それでも重い。仕事をするためにパソコンを買ったのに、パワーの半分近くがウィルス対策に盗られている。いったい、どうなっているのだ?

先日、Maya、Max、Director、AfterEffects、Photoshopなど重いグラフィックソフトを使っているデザインチームに、ウィルス対策ソフトを導入することにした。台数は25~30台。事前に、試用版を試してみたが、やはり、重い。ワンクリック何円という激しいマウス操作で生計を立てるグラフィックデザイナーにとっては死活問題。

■チューリングテスト

話をアラン・チューリングに戻そう。チューリングの業績は難解なもの多いが、中にはなじみやすいものもある。「チューリングテスト」だ。
「機械が知能と呼べるかどうか?」
を判定するテストである。まず、人間がキーボードとモニターを介して、機械と対話をする。その人が、その機械を人間と誤認すれば、機械は「知能」と認定される。だが、2006年現在、チューリングテストに合格した機械(プログラム)はない。そのほとんどが、言葉を並べ替えて、人間を惑わしているだけ。やはり、チューリングテストに合格するには正真正銘の「人工知能」が必要だ。

しかし・・・

ノイマン型コンピュータでは人工知能は実現できない
と、個人的には思っている。

チューリングは、
「プログラムの実行結果を予測する普遍的なプログラムは存在しない」
を数学的に証明した。よって、
「プログラムのアルゴリズムを理解できる普遍的プログラムは存在しない」
ところが、
「知能とはプログラムのアルゴリズム(思考手順)を理解できるもの」
だから、チューリングマシンやノイマンマシンでは、人工知能は創れない・・・ただのプログラマーの独り言である。

■脳の謎

1997年、アメリカのマンハッタンの一室で、歴史的チェスゲームが行われた。チェスの世界チャンピオン「ガルリ・カスパロフ」と機械の「ディープブルー」の一戦である。結果は、2勝1敗3引分で、ディープブルーの勝ち。マスコミはこぞって、
「人間の知性が機械に負けた」
と喧伝した。だが、ディープブルーは「人工知能」ではない。もし、ディープブルーがホンモノの知能の持ち主なら、チューリングテストに合格し、今頃、人間と世間話を楽しんでいただろう。

ディープブルーは、チェスを数値化して計算しているだけ。思考しているのではなく、チェスの手順をなぞっているだけである(シミュレーション)。
知能とは思考手順をなぞるのではなく、創発すること
そう考えると、脳の本質が見えてくる。

じつは、脳は「考える」ことはできるが、考える「仕組み」まで理解することはできない。同じように、ゲームに登場するキャラは敵を「倒す」ことはできるが、「倒す」仕組みは理解できない。仕組みを理解できるのは、その仕組みの作り手のみ。つまり、ゲームのキャラならプログラマー、知能ならこの世界の創造主。ということで、遺伝子操作やタイムマシン同様、人工知能は神の領域なのかもしれない。

《つづく》

参考文献:
星野力「蘇るチューリング」NTT出版
サイモン・シン青木薫約「暗号解読」新潮社

by R.B

関連情報