17世紀の暗号が20世紀の暗号の基礎に

2015年9月28日

歴史の本や小説に登場する暗号は、どれもほとんどが「単表式換字暗号」という種類に属しています。前にも取り上げましたが、この暗号化手法の主な脆弱性は、符号の出現頻度のパターンを分析すれば解読できることです。この事実は、コンピューターが登場するずっと前から知られていました。

この欠陥を補うべく考案された暗号の中でも特に有名で興味深いのは、ヴィジュネル暗号です。17世紀のフランスの外交官ブレーズ・ヴィジュネル(Blaise Vigenere)氏によるものと言われていますが、実際に作ったのは2人の人物です。それも共同ではなく別々に活動していました。面白いことに、ヴィジュネル氏はどちらの人物でもなく、ヘンリー三世にこの暗号の使用を進言しただけです。この暗号が現在の名前で呼ばれるようになったのは19世紀になってからです。

この暗号が最初に言及されているのは、レオン・バッティスタ・アルベルティ(Leon Battista Alberti)氏の本『Trattati in cifra』(暗号論)です。同氏は、絵画における線遠近法の前身となる理論を初めて提唱した人物として知られています。この暗号の基礎となる考え方は、ごく単純なものですが、暗号方式をそれまでにない新しいレベルに引き上げ、多表式換字暗号の黎明を告げるものとなりました。

単表式換字暗号では、平文を構成するそれぞれの符号を常に同じ符号に(たとえばアルファベットの別の文字に)置き換えて暗号文を作ります。置き換えに使う符号はランダムに選ぶ場合もあれば、一定のシフト数に従って選ぶ場合(シーザー暗号など)もあります。置き換え用の符号は文字、数字、記号のいずれでも構いません。

アーサー・コナン・ドイル卿の『踊る人形』で印象的に使われたように、置き換え用の符号を象形文字にすることもできます。しかし、その場合でも、周知の脆弱性がなくなるわけではありません。暗号文に使われたキーワードについて仮説を立てる、暗号文に現れる特定の符号の頻度を分析する、といった方法で推測することは可能です。

不肖私も以前、この手法を使って、普段とは別のエンコーディング形式で受信したメールを(遊びで)解読してみたことがあります。特別なスキルや十分なコンピューター処理能力がなくとも、解読はそれほど難しくありませんでした。

多表式換字暗号では、置き換え用の符号を周期的に繰り返して使います。たとえばヴィジュネル暗号では次のパターンを使用します。シーザー暗号を基礎として、考えられるすべての置き換え符号を網羅した方陣です。

vigenere-cipher-0

置き換え用のアルファベット26文字を用意したら、置き換えのルールを決める必要があります。それぞれの文字をアルファベットの次の文字に置き換えるだけでも、ある程度は複雑になりますが、併せてキーワードも使えば、解読は非常に難しくなります。

この記事は歴史の話から始まりましたから、ここではキーワードを「VINTAGE」としましょう。たとえば「THINK ABOUT IT」というフレーズを暗号化する場合、キーワードが平文よりも短いので、足りない分は最初の符号から繰り返す必要があります。

JA_vigenere-cipher-1

次に、平文をそれぞれの符号に置き換えます。平文の文字で始まる列と、キーワードの文字で始まる行を探し、その列と行が交差する位置にあるのが置き換え用の符号です。たとえば、平文の最初の文字「T」を、Tで始まる列とVで始まる行が交差する位置にある符号、つまり「O」に置き換えます。

JA_vigenere-cipher-2

解読は暗号化と逆の手順を行います。キーワードの文字で始まる行を探し、その行の中から暗号文の文字を探し、その文字のある列の最上段にある文字を書き出せば、平文が復元されます。

興味深いことに、アルベルティ氏が考案した当初の手法では、アルファベットが刻まれた特別な円盤を回転させて使うことを想定しており、上記のような方陣は後になって別の改良者が発案しました。1446年の論文に書かれていたような円盤は、米国の南北戦争で南軍に使用されました。

cipher_FB

画像出典:Wikipedia

一般的に、この暗号は非常に信頼性が高いという評判を得ました。数学者チャールズ・ラトウィッジ・ドジソン(Charles Lutwidge Dodgson)(別名ルイス・キャロル(Lewis Carrol))氏には「解読不可能」とまで言われ、Scientific American誌にも称賛されました。しかしその後、ヴィジュネル暗号の改良型であり、さらに有名になった「グロンスフェルド暗号」が登場しました。ヴィジュネル暗号との大きな違いは、置き換え用の文字の数が(十進法で用いる数字の数に合わせて)10通りに制限されていることと、キーワードが数字であることです。

実はヴィジュネル暗号も、一定の条件が揃えば解読される恐れがあります。特性を分析するとキーワードの長さを特定できます。さらに、方陣内の同じ行を使って暗号化された文字の行を分析すると、その言語において特定の文字が出現する頻度に基づく標準的な手法を当てはめることができます。

1854年に初めてヴィジュネル暗号の改良型の解読に成功したのは、他でもない、電子計算機技術の先駆者であるチャールズ・バベッジ(Charles Babbage)氏でした。なお、分析結果は9年後に別の研究者フリードリヒ・カシスキー(Friedrich Kasiski)氏が発表しました。

一見不思議なようですが、この一件は却ってヴィジュネル暗号の強化につながりました。暗号文そのものと同じ長さのキーワードを使用するなどの改良を施し、頻度分析が行われないようにしました。

ところが、その改良によって新たな脆弱性が生まれました。意味を成す文字列をキーワードにすると、暗号分析者にキーワードについてある種の統計情報を提供することになり、新たな解読の手がかりを与えてしまうからです。

しかし、この考え方がさらに次の改良につながりました。符号をランダムに並べたものをキーワードに使うことにしたのです。

やがてこの考え方は、ワンタイムパッド(OTP)のコンセプトに活かされました。そうして生まれた各種暗号は解読不可能とされ、民間および軍事分野の暗号法として利用されました。それについてはまた、別の機会に紹介します。