チャールズ・バベッジとは？ヴィジュネル暗号を解読するコンピュータの父

19世紀英国の数学者、チャールズ・バベッジ（1791～1871）は、人類で初めてプログラム可能な計算機「解析機関（アナリティカル・エンジン）」を考案しました。コンピュータサイエンスの分野では、よく知られた偉人です。コンピュータの父とも呼ばれています。

今回は、チャールズ・バベッジの数ある功績の一つとして挙げられる、ヴィジュネル暗号の解読について説明します。

チャールズ・バベッジとはどんな人か

チャールズ・バベッジ（1791年12月26日 - 1871年10月18日）は、イギリスの数学者です。計算機科学者や哲学者でもあるとされています。コンピュータの父とも呼ばれており、「階差機関（ディファレンス・エンジン）」という、階差数列を利用して、数表を次々と計算する機械を開発しました。その後、発展型として模索された「解析機関（アナリティカル・エンジン）」の開発・研究も行い、世界で初めてプログラムができる計算機を考案した人物です。

ケンブリッジ大学ルーカス講座の教授を務めていたことも

バベッジは数学者としても優秀で、ケンブリッジ大学のルーカス講座の教授を務めていたこともあります。これは数学講座としては最も権威あるものです。2代目教授はアイザック・ニュートンでした。近年ではスティーブン・ホーキングが務めています。

バベッジの考案した計算機は、当時の主要エネルギー源であった蒸気機関が動力源だったという特徴を持っています。しかしこの計算機は、極めて実用性の高く、暗号解読に欠かせないものだったといわれています。

バベッジは人力で作成する数表に課題を抱く

電卓やGPSなどがなかった当時、航海をするには、三角関数表などの数表を使って星の測量をして自分の位置を計算していたといいます。しかし、この数表は人の手で作られていたため、数が大きくなればなるほど正確な数表を作ることが困難になります。精度が落ち、間違いだらけになった数表を見て、バベッジは、この数表を自動的に計算して、印刷する機械を作ろうと考えました。そこで試作されていたものが、階差数列を利用して、数表を次々と計算する機械「階差機関（ディファレンス・エンジン）」です。

そしてバベッジは当時、機関開発だけでなく、暗号解読にも熱中し、当時「解読不能」と言われていたヴィジュネル暗号の攻撃法を開発します。

後継者によって完成された「解析機関（アナリティカル・エンジン）」

さらにその発展型として研究された「解析機関（アナリティカル・エンジン）」は、パンチカードでプログラムを組むことが可能な機関です。プログラムをカードで用意し、それを機械に入れ交換することで、さまざまな数表の印刷が実行できるという機関を亡くなる直前まで研究していたといいます。その後、バベッジのアイデアを理解していたエイダ・ラブレスという人物によって、解析機関のプログラムは実際に作成されます。エイダ・ラブレスは、世界初のプログラマーと呼ばれています。

ヴィジュネル暗号とは？近代まで解読不能だった？

ヴィジュネル暗号の概要について説明します。 ヴィジュネル暗号とは、フランス外交官ブレーズ・ド・ヴィジュネル（1523年～1596年）によって完成された多表式の換字式暗号のことです。単一換字式暗号が安全ではないと考えられるようになった15世紀後半から16世紀後半と約100年かけて考案された暗号です。

ヴィジュネル暗号は、ブレーズ・ド・ヴィジュネルが考案したわけではなく、まず1460年頃にレオン・バッティスタ・アルベルティが多表式の原型を思いつきます。それまでの換字式暗号は1つの暗号アルファベットを使っていましたが、そうではなく、2つ以上のアルファベットを使うことを考案します。

引き継いだのはドイツの修道院長ヨハネス・トリテミウスでした。レオン・バッティスタ・アルベルティによる多表式の原型の研究を引き継ぎ、その次にはイタリアの科学者ジョヴァンニ・ポルタが継承し、最終的に、ブレーズ・ド・ヴィジュネルが当初レオン・バッティスタ・アルベルティが考案した暗号を完成させます。各々がこの暗号の完成までに重要な貢献をしましたが、最終的に形として仕上げたヴィジュネルの名が暗号につけられています。

そもそも換字式暗号とはどんなものか？

換字式暗号は、アルファベットの文字を別の文字に置き換えることを基本的な暗号化方式として考えられた暗号になります。単一換字式暗号と呼ばれることもあります。換字式暗号の中でも最も単純なものに、それぞれの文字を3文字前の文字に置き換えるシーザー暗号があります。

単一換字式暗号について詳しく知りたい方はこちらの記事も参考にしてください。

シーザー暗号について詳しく知りたい方はこちらの記事も参考にしてください。

ヴィジュネル暗号の仕組み

ヴィジュネル暗号は、ヴィジュネル方陣と呼ばれる表を元に換字表を作っていきます。これは、図にあるようにアルファベットをずらしながら並べた表です。

ビジュネル暗号に使われるビジュネル方陣。アルファベットをずらしながら並べた単純なもの。簡単に作れるため、送受信者間で受け渡しをする必要がない。

まず、鍵語を決めます。文字数に制限はなく、長ければ長いほど暗号強度は高くなりますが、暗号化と復号化の手間がかかるようになるのがデメリットです。今回は、6文字の「PERSOL」を鍵語として扱っていきましょう。

ヴィジュネル方陣から「PERSOL」の6行を抜き出して、換字表として使います。原文の1文字目は、「P」の行を使って暗号化、2文字目は「E」の行を使って暗号化、7文字目は再び「P」の行に戻って暗号化をしていきます。

復号化をしていくときは、換字表を逆に見ていけば原文が現れます。

鍵語を「PERSOL」に定めたら、ビジュネル方陣から鍵語の各行を抜き出して並べる。これが暗号表になる。原文の1文字目はPの行で、2文字目はEの行で…と暗号化していく。送受信者間で鍵語を受け渡すだけで、暗号化、復号化ができる。

ヴィジュネル暗号のメリット

ヴィジュネル暗号のメリットは、送信者と受信者の間で、鍵語や換字表のやりとりをしなくて済む点です。両者が同じ本を持ち、たとえば送信日が7月23日であれば「23ページの7番目の単語を鍵語にする」と定めておくだけでやりとりが完了します。

もうひとつのメリットは、頻度分析に強いことです。

英文の場合、出現する頻度が多い文字は「e」、その次に「t」、「a」、「o」、「i」、「n」…と続くことがわかっています。単純な換字暗号では、「e」は必ず別の同じ文字に置き換えられるため、暗号文にその文字が頻出することになります。

そのため、暗号文にある文字の出現回数を数えて、「いちばん多い文字がeである」という推測が可能です。さらに、「th」、「he」、「in」などといった2文字の出現頻度、「the」、「ing」などの3文字の出現頻度も手がかりとなり、クロスワードパズルの要領で暗号を解読することができます。

しかし、ヴィジュネル暗号では、1文字目から6文字目までは、同じ文字であってもまったく別の文字に置き換えられるため、このような頻度分析が使えません。鍵語を長くすれば、暗号文のどの文字もほぼ同じ割合で出現することになってしまうため、「解読不能」といわれています。

しかしバベッジは、このヴィジュネル暗号の攻撃手法を開発します。注目したのは、同じ文字列が繰り返し登場する周期性です。

バベッジは、ヴィジュネル暗号の周期性に着眼点を置く

上述のとおり、バベッジがヴィジュネル暗号の攻撃手法として注目したのは、同じ文字列が繰り返し登場する周期性です。

例えば、鍵語「PERSOL」を使って、「hack」という文字列が繰り返す原文を暗号化してみます。「hack」はいろいろな文字列に変換されてしまいますが、6文字の鍵語と4文字の原文がうまくシンクロして、まったく同じ文字列に変換されることもあります。鍵語の同じ部分で暗号化されているからです。

ビジュネル暗号では、同じ単語が同じ暗号文になるとは限らない。しかし、鍵語とうまくシンクロして、鍵語の同じ部分が使われて暗号化された場合は、同じ暗号文になる。ここから、同じ文字列の距離を調べると、鍵語の文字数が推測できる。この図ではwetzv…という同じ文字列が、12文字の距離（wからwまでを数える）になるので、鍵語の文字数は12、6、3、2、1のいずれかであると推測できる。

この法則を見つけたバベッジは、暗号文の中に同じ文字列が出現するとき、同じ単語がうまく鍵語とシンクロして、暗号文が変換された（複号された）可能性があると考えました。そして、同じ文字列の間の距離（文字数）は、鍵語の文字数の倍数になっていなければならない、ということにも気づきました。

同じ文字列、同じ文字の距離を数え統計を取り、その距離の最大公約数が鍵語の長さになると推測できると考え、鍵語の長さが、例えば6文字だと分かれば、暗号文の6文字ごとの文字頻度を数えれば、いちばん多いのがeであるという推測が出きていくことになると考えました。

単純な換字暗号から比べれば、解読には大きな労力がかかりますが、外交電文や軍用電文などは、それだけの手間をかけても解読したいと考える人は多いでしょう。

カシスキーテスト

上述の性質を利用して、暗号文から同じ文字列、同じ文字の距離を数える攻撃手法は、カシスキーテストと呼ばれます。

カシスキーテストとは、繰り返し登場する文字列、文字の距離（文字数）を数える暗号解読の手法のことです。6文字置き、2文字置き、3文字置き、12文字置きに同じ文字列、文字が登場することが多く、鍵語の文字数はこのような数の公約数である可能性が高いという特徴を持っています。この名称は、10年後にドイツの暗号解読者フリードリッヒ・カシスキーが独自に発見、公表した結果に基づいてつけられました。

バベッジ自身はこの手法を発見していても、公表はしませんでした。本人が大した発見だとは思っていなかった、またはイギリス陸軍が非公表にすることを命じたとも言われています。

「クリブ」という着眼点から鍵語を推測

暗号または暗号解読におけるクリブ (crib) とは既知のもしくは想定されうる平文のサンプルのこと。仮定語、対照平文ともいう。第二次世界大戦中、英国の暗号解読作戦の本拠地であったブレッチリー・パークにおいてこの語が使われ始めた。

難解で不可解に思える暗号文でも、手がかりとして元となる平文中の数語から数フレーズが既知もしくは想定可能であれば解読の糸口をつかむことができる。また総当たり攻撃の場合でも、復号した文中にクリブが見つかれば、試みた復号方法が正しいらしいと知ることができ、全文の解読につながる。（引用：出典: フリー百科事典『ウィキペディア（Wikipedia）』既知平文攻撃）

暗号文の種類によっては、原文に使われていそうな単語を推測できることがあります。

例えば、軍用電文であれば、「ロンドン」「リバプール」といった地名、「快晴」「濃霧」といった気象用語がよく使われます。そこで、Londonであれば、暗号文の１文字目から６文字目までがLondonだと仮定し、ヴィジュネル方陣を逆算して、どのような鍵語になるかを調べてみます。

鍵語は意味のある単語が使われることが多いので、この推測した鍵語がデタラメな文字列であれば攻撃は失敗します。

次に２文字目から７文字目までがLondonではないかと仮定し、以降は同じことを繰り返していきます。もし、原文のどこかにLondonが使われていれば、どこかで意味の通じる鍵語が現れるはずでしょう。

これが突破口となり、次々とヴィジュネル暗号の攻撃手法が開発されていきます。その中でも有力だったのが、クリブ攻撃でした。

もちろん、暗号を使う側もさまざまな対策をし、ヴィジュネル暗号も進化をしていきます。例えば、頻出する単語London、Liverpoolは、LDN、LVPなどという略号にするのが、軍用電文では基本中の基本になっています。

クリブとエニグマ暗号

暗号技術の大きな転換点が、1925年にドイツ軍に採用されたエニグマ暗号機です。アルファベット26文字分の歯がついた歯車3枚によって暗号化され、3枚の歯車はリムーバブル方式になっており、暗号機にセットする順番も変えることができます。つまり、(3×2×1)×(26×26×26）＝10万5456通りの変換方法があります。

WW2における最強の暗号生成機、ナチスドイツのエニグマ

原理はヴィジュネル暗号と根本は変わらず、ただ鍵語の長さが10万5456文字になるため、カシスキーテスト攻撃が通用しない状態になります。

エニグマ暗号も、ドイツ軍は「解読不能」と謳っており、敵の前線の弱点に爆撃機と戦車を一点集中させる電撃作戦、敵輸送船団にUボートを一点集中させて攻撃する群狼作戦が可能になったのも、エニグマ暗号により前線部隊同士で安全に通信ができ、密な連携が可能になったからだとされています。ドイツ軍は、電子式の暗号機を開発し、ビット演算をするローレンツ暗号を使い始めました。

エニグマよりも更に複雑な構造であったローレンツ暗号機

ドイツの敵国であったポーランドの暗号解読者マリヤン・レイエフスキーは、バベッジのアイディアとは異なりますが、エニグマ暗号の周期性を探り、それを基に解読をしようとしました。その周期性を発見するのは、紙とペンでは無理な話で、ボンブと呼ばれる機械まで開発しています。

イギリスの暗号解読拠点「ブレッチリーパーク」で暗号解読の仕事をしていた数学者アラン・チューリングは、エニグマ暗号をクリブ攻撃の手法で解読しようとします。そのために電子式のボンブを開発しました。

ブレッチリーパークのトミー・フラワーズは、このローレンツ暗号にクリブ攻撃をするために、電子式の解読機械「コロッサス」を開発しました。このコロッサスが世界で最初の電子計算機であるという説もあります。

クリブ攻撃解読が試みられたローレンツ暗号の解読機コロッサス

ヴィジュネル暗号も進化、鍵語を原文へ内包

自己鍵を使ったビジュネル暗号。暗号化する時は、鍵語に続いて、原文そのものを鍵語として使う（上）。復号化する時は、まず定められた鍵語で解読、原文が現れるので、以降の鍵として復号化を進めていく（下）。同様の暗号強度を増すテクニックは、エニグマ暗号でも使われた。

まとめ

バベッジが紙とペンと思索で解読した暗号は、第2次世界大戦中に機械式、そして電子式に急速に進化しました。

コロッサス以降、電子計算機も急速に進化・発展し、現在私たちが使っているコンピュータやスマートフォンにつながっています。

今や、SSLやRSAといった暗号技術は、ネットショッピングやオンラインバンキングを行うには欠かせないないものになっていたりと、バベッジの時代から200年経ちますが、暗号技術は常に進化を続けています。