ヴィジュネル暗号

ヴィジュネル暗号(ヴィジュネルあんごう、Vigenere cipher)とは、フランスの外交官ブレーズ・ド・ヴィジュネルによる多表式の換字式暗号のことである。多表式の暗号は、単一換字式暗号が安全でなくなってきた15世紀後半から16世紀後半にかけて考え出された暗号で、ヴィジュネル暗号はその中で恐らく最も有名なものである。

発明

1460年代、レオン・バッティスタ・アルベルティが、多表式の暗号の原型を思いついた。それは、今までの換字式暗号は一つの暗号アルファベットを使ってきた。そうではなく、2つ以上の暗号アルファベットを使ってはどうかと考えたのだ。これを引継いだのが、ドイツの修道院長、ヨハネス・トリテミウス、次は、イタリアの科学者、ジョヴァンニ・ポルタ。そして、フランスの外交官、ブレーズ・ド・ヴィジュネルにバトンされていった。各々がこの暗号に重要な発展をもたらしたが、最終的な形に仕上げたヴィジュネルの名前が付いている。ヴィジュネルは1586年、『秘密の書記法について』を出版した。ここまでくるのに100年以上費やした「難産」の暗号だったが、しばらくの間、無視された。その理由として、いまだ単一換字式が虫の息ながら残っていたこと、単一換字式に対して暗号化・復号が難しいこと、が挙げられる。

暗号化と復号

右図（ヴィジュネル方陣）を使って暗号化を行う。以下、平文を大文字、暗号文を小文字で表す。例としてarmを鍵、平文をCODEとすると、ヴィジュネル方陣で、aとCの交わりはcであり、rとOはf、mとDはpというように暗号文 c, f, p が得られる。平文が鍵よりも長い場合、鍵を繰り返して用い、最後の平文Eはaとの交わりでeとなる。すると、平文「CODE」は暗号文「cfpe」となる。ここで平文が暗号文と同一の文字になる箇所があるが、解読者にそれは分からない。大事なのは鍵の周期（今回なら3）を解読者は知らないということだ。また、この鍵は文字数の制約がないので、鍵の個数は無数である。実際利用するという観点からみれば、覚えやすいほうがよい(紙に書くとそれが漏れる場合があるので)が、逆に敵に推測されやすいという危険もある。今回の鍵は単に例として「arm」つまり「腕」という覚えやすい単語とした。
復号はこの逆をすればよい。つまり、鍵がaで暗号文がcならば、左端のAの行でcの場所を探し、そこから上に辿った最上段の文字が平文Cである。当たり前のように感じられるが、現代暗号には、公開鍵暗号のように暗号化と復号の方法が異なるものもある。

ヴィジュネル暗号の解読

単一換字式暗号が解読者たちによって息の根を止められると、皆、このヴィジュネル暗号を注目しだした。暗号化、復号が面倒だが、情報の保護はそれ以上に値したからだ。

カシスキー・テスト

この解読法を発見したのはコンピュータの原型を造ったチャールズ・バベッジであるが、これにもエピソードがある（解読のエピソードにて）。
解読方法は、頻度分析よりも難しくなるが、不可能ではない。しかし、前述の「cfpe」など、短すぎる場合はほぼ解読できない。以下は、相当長い暗号文が与えられ、しかもそれがヴィジュネル暗号だと分かっているときの解読法である。

鍵推理による解読法

たとえば、暗号文「talsyvbaeifvmssmms」が与えられたとしよう。最初に種明かしをしてしまえば、この暗号文に使われた鍵は平文と同じ長さ、つまり18文字で、鍵にある規則があり、平文は英語である。前述のカシスキー・テストが使えない。（以下、*は未知の文字）
平文　:******************
鍵　　:******************
暗号文:talsyvbaeifvmssmms
まず、英語にありふれた「The」などの単語を仮に平文として考えてみる。たとえば、最初の3文字が「THE」ならば、
平文　:THE***************
鍵　　:ath***************
暗号文:talsyvbaeifvmssmms
鍵は「ath***************」である。鍵は意味のある文だから、得られた仮の鍵は文章の一部として成り立つ。しかし、たとえば、4文字目から平文「THE」があるならば、
平文　:***THE************
鍵　　:***lrr************
暗号文:talsyvbaeifvmssmms
鍵は「***lrr************」と不可思議な文字列となり、ここに「The」は入らないと仮定できる。
次に、鍵が「ath***************」の場合、「ath」に続くものを探す。「athabaskan」(アサバスカ諸語)「athanasius」(アタナシオス)などがあるが、実際に鍵として用いたとき、平文が意味のある文字を探す必要がある。そうして見ていくと、「athens************」で平文「THEOLD」が得られる。同様に、また、先に得られた鍵が都市名であることも踏まえて考えていくと、
平文　:THEOLDMANANDTHESEA
鍵　　:athensparisstlouis
暗号文:talsyvbaeifvmssmms
鍵「Athens Paris St.Louis（アテネ、パリ、セントルイス）」が考えられ、平文「THEOLDMANANDTHESEA（『老人と海』）」が得られるのだ。なお、アテネ、パリ、セントルイスは、夏季オリンピックの第1回、2回、3回大会の都市であるので、もし鍵が長くなった場合は「london」（ロンドン）が追加された可能性を考えるのもいいだろう。

ヴィジュネル暗号の弱点と暗号史に与えた影響

ヴィジュネル暗号も含み、それ以前の暗号すべてに言えることであるが、これには、鍵に周期性があるということだ。たとえば、鍵「arm」は、4文字目の鍵もaになるし、7文字目もaになる。これが、解読者にとって唯一の手がかりだった。鍵の周期性の問題性に気付かなかったのは、よりアルゴリズム(暗号化の方法)を複雑にすることによって安全にしようとしていたからで、誰も「鍵」の重要性に気付いていなかったのである。では、鍵長を平文と同じにしたら、完全か。確かに、周期性の問題は解決する。しかし、上記のように周期が起こらない鍵であっても、推理することによって解決する場合がある。
そのため、この問題を乱数を利用することで打開しようとしたのだ。また、その数も多くすれば一つの周期も長くなるため、鍵の長さは膨張の一途をたどっていくようになる。また、後に、人力では限界が見えてきた時代に「暗号を行う機械」も出てくるが、これも、周期の長さ、鍵が乱数であることが、大きな目標とされた。
現在の暗号においても、鍵が乱数であるかは、最も重要とされ、アルゴリズムが公開されているからこそ、偏った数を鍵に使用すると、すぐに解読されてしまう。また、鍵の長さも、安全性をはかるものさしとなっている。

ヴィジュネル暗号の弱点の改良と現代暗号

ヴィジュネル暗号の弱点は鍵の周期性だけではなく、表にきわめて強い対称性（線形性）があることである。これは解読の大きな手がかりとなる。そこで考えられたのはヴィジュネル表の対称性をなくすために、表の中の文字をランダムに配置することであった（各行と列に26文字が1文字ずつあるという対称性は残る）。これによってカシスキーテストの有効性が著しく減少し、紙とペンだけではほとんど解読できなくなる。もっとも、表の作成と解読に時間がかかるためと、ヴィジュネル暗号が解読できないと思われていたためあまり利用されなかったと言われる。このランダムに配置するという考え方は現代暗号でも線形解読法、差分解読法に対して耐性を持たせるためのSボックスの実装として利用されている。（ランダムに配置した表の実物は「暗号」（長田順行）のp165にある。ヴィジュネル自身が1586年に発表したが「ヴィジュネル表」とは呼ばれていない。）（ランダムに配置するときわめて解読しにくくなるが、確率論的にきわめて脆弱な表ができることがあるので、脆弱性を検定する必要がある。）。

解読のエピソード

チャールズ・バベッジが解読方法を探った理由は単純なものだった。ある日、「私は新しい暗号を発明した」という人物（ジョン・ホール・ブロック・スウェーツといわれている。一般人）が現れて、（その100年以上も前に発明されていたが、世に広く出回らなかった為、「新しい」となってしまった）「学芸協会誌」に論文を発表した。バベッジは「古くからある暗号だ」と主張。しかし、スウェーツは「ならば、この暗号を解いてみろ」と反論。解ける解けないと古い新しいは、全く関係なかったものの、バベッジはその挑戦を受けてたった。
解読に成功したのは、スウェーツとの論争のしばらく後の1854年だと考えられている。「考えられている」というのは、バベッジはこれを公表しなかったのである。1863年にカシスキー（en:Friedrich Kasiski）が、同じ手法を発見し、『暗号文と解読技術』という本にまとめて出版している。これをバベッジが先に発見したということは20世紀に入ってから分かったことである。長らくの間、この手法が「カシスキー・テスト」と呼ばれていたのもそのせいである。
バベッジが発表しなかったことについては、単にその気がなくなってしまっただけ、発見同時期に勃発したクリミア戦争を踏まえて、イギリスの情報局がバベッジに秘密にするように要請した（これが本当ならばイギリスはおよそ9年間、各国の機密情報を漏らさず知っていたことになる）、などの憶測を呼んでいるが、いずれも仮説の域を出ていない。