ヴィジュネル暗号
ヴィジュネル暗号(ヴィジュネルあんごう、Vigenère 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である。鍵が同一であることは当たり前のように感じられるかもしれないが、現代の暗号には、公開鍵暗号のように暗号化と復号の鍵が異なるものもある。
文字を数値としてみれば (a = 0, b = 1, ..., z = 25)、次の式が成り立つ。ただし、P_i は平文の i 文字目、K_i は鍵の i 文字目、C_i は暗号文の i 文字目である。
C_i = (P_i + K_i ) \bmod 26
逆に、C_i から P_i を求める式は、
P_i = (C_i - K_i ) \bmod 26
となる。mod 26 は、演算結果が 0〜25 の範囲からはみ出した場合には、26 を加算または減算することを表している(剰余演算)。
発明当時は暗号化、復号が「難しい」とされてきたヴィジュネル暗号であるが、このように、加減算と剰余の計算ができれば済むので、10 行足らずのコードを書くだけでコンピュータに計算を任せることができる。
単一換字式暗号が解読者たちによって息の根を止められると、皆、このヴィジュネル暗号に注目しだした。暗号化、復号が面倒だが、情報の保護はそれ以上に価値があったからだ。
この解読法を発見したのはコンピュータの原型を造ったチャールズ・バベッジであるが、これにもエピソードがある(解読のエピソードにて)。
解読方法は、頻度分析よりも難しくなるが、不可能ではない。しかし、前述の「cfpe」など、短すぎる場合はほぼ解読できない。以下は、相当長い暗号文が与えられ、しかもそれがヴィジュネル暗号だと分かっているときの解読法である。
まず、同じ文字の羅列を探る。また、文字列は長いほうが確実である。
次にその羅列の間隔を数える。
以下、同じように探していくと発見された文字間隔がたとえば、9、63、180、であったとき、この3つの数の公約数は3と9なので、鍵の文字数は3か9であると仮定できる。
すると、この暗号の最大の関門、鍵の文字数が分かってしまったのだ。すると、頻度分析が使える。つまり、間隔が3の文字どうしは、図の同じ行が使われているということだ。
頻度分析にかけるが、大事なのは1つだけの行を使った場合、単なるシーザー暗号になるということだ。つまり、暗号文の3の間隔同士の文字の頻度をグラフで見ると、平文で行った頻度分析と似ているようで似ていない形になる。しかし、シーザー暗号を使っているということは、文字をいくらかずらせば、平文の頻度解析を行ったものとほぼ同じになる。
ヴィジュネル暗号が解ける。
「反復している文字の羅列」というのは、平文が同じ文字のとき、同じヴィジュネル方陣の行に当たって出来たものと考えられる。
「間隔を数える」。その通りである。
「共通の因数を求める」これは、平文が同じであった場合、使われている鍵は、その間隔の因数でなければいけないからで、逆を言えば、鍵の文字数の倍数でなければならないからだ。
「文字数が分かる」これは、ヴィジュネル暗号の最大の欠点である。これを突破できれば、昔ながらの解読法で解ける。
「頻度分析にかける」シーザー暗号と聞いて、「26しか鍵がないから、すべて調べればよい」と思うかもしれないが、これは、続いた文字列ではないことに注意してもらいたい。すべて調べても、意味がある言葉にはなりにくい(等間隔で文字を拾ったのだから、平文でも意味が分からない)。これをすべて調べる場合、鍵の文字数をnとしたとき、26のn乗を調べなくてはならない。
「解くことができる」しかし、文章が短くなると難しい。
たとえば、暗号文「talsyvbaeifvmssmms」が与えられたとしよう。最初に種明かしをしてしまえば、この暗号文に使われた鍵は平文と同じ長さ、つまり18文字で、鍵にある規則があり、平文は英語である。前述のカシスキー・テストが使えない。(以下、*は未知の文字)
<pre>
平文 :******************
鍵  :******************
暗号文:talsyvbaeifvmssmms
</pre>
まず、英語にありふれた「The」などの単語を仮に平文として考えてみる。たとえば、最初の3文字が「THE」ならば、
<pre>
平文 :THE***************
鍵  :ath***************
暗号文:talsyvbaeifvmssmms
</pre>
鍵は「ath***************」である。鍵は意味のある文だから、得られた仮の鍵は文章の一部として成り立つ。しかし、たとえば、4文字目から平文「THE」があるならば、
<pre>
平文 :***THE************
鍵  :***lrr************
暗号文:talsyvbaeifvmssmms
</pre>
鍵は「***lrr************」と不可思議な文字列となり、ここに「The」は入らないと仮定できる。
次に、鍵が「ath***************」の場合、「ath」に続くものを探す。「athabaskan」(アサバスカ諸語)「athanasius」(アタナシオス)などがあるが、実際に鍵として用いたとき、平文が意味のある文字を探す必要がある。そうして見ていくと、「athens************」で平文「THEOLD」が得られる。同様に、また、先に得られた鍵が都市名であることも踏まえて考えていくと、
<pre>
平文 :THEOLDMANANDTHESEA
鍵  :athensparisstlouis
暗号文:talsyvbaeifvmssmms
</pre>
鍵「Athens Paris St. Louis(アテネ、パリ、セントルイス)」が考えられ、平文「THEOLDMANANDTHESEA(『老人と海』)」が得られるのだ。なお、アテネ、パリ、セントルイスは、夏季オリンピックの第1回、2回、3回大会の都市であるので、もし鍵が長くなった場合は「london」(ロンドン)が追加された可能性を考えるのもいいだろう。
ヴィジュネル暗号も含み、それ以前の暗号すべてに言えることであるが、これには、鍵に周期性があるということだ。たとえば、鍵「arm」は、4文字目の鍵もaになるし、7文字目もaになる。これが、解読者にとって唯一の手がかりだった。鍵の周期性の問題性に気付かなかったのは、よりアルゴリズム(暗号化の方法)を複雑にすることによって安全にしようとしていたからで、誰も「鍵」の重要性に気付いていなかったのである。では、鍵長を平文と同じにしたら、完全か。確かに、周期性の問題は解決する。しかし、上記のように周期が起こらない鍵であっても、推理することによって解決する場合がある。
そのため、この問題を乱数を利用することで打開しようとしたのだ。また、その数も多くすれば一つの周期も長くなるため、鍵の長さは膨張の一途をたどっていくようになる。また、後に、人力では限界が見えてきた時代に「暗号を行う機械」も出てくるが、これも、周期の長さ、鍵が乱数であることが、大きな目標とされた。
現在の暗号においても、鍵が乱数であるかは、最も重要とされ、アルゴリズムが公開されているからこそ、偏った数を鍵に使用すると、すぐに解読されてしまう。また、鍵の長さも、安全性をはかるものさしとなっている。
ヴィジュネル暗号の弱点は鍵の周期性だけではなく、表にきわめて強い対称性(線形性)があることである。これは解読の大きな手がかりとなる。そこで考えられたのはヴィジュネル表の対称性をなくすために、表の中の文字をランダムに配置することであった(各行と列に26文字が1文字ずつあるという対称性は残る)。これによってカシスキーテストの有効性が著しく減少し、紙とペンだけではほとんど解読できなくなる。もっとも、表の作成と解読に時間がかかるためと、ヴィジュネル暗号が解読できないと思われていたためあまり利用されなかったと言われる。このランダムに配置するという考え方は現代暗号でも線形解読法、差分解読法に対して耐性を持たせるためのSボックスの実装として利用されている。(ランダムに配置した表の実物は長田順行『暗号』165頁にある。ヴィジュネル自身が1586年に発表したが「ヴィジュネル表」とは呼ばれていない。)(ランダムに配置するときわめて解読しにくくなるが、確率論的にきわめて脆弱な表ができることがあるので、脆弱性を検定する必要がある。)。
チャールズ・バベッジが解読方法を探った理由は単純なものだった。ある日、「私は新しい暗号を発明した」という人物(ジョン・ホール・ブロック・スウェーツといわれている。一般人)が現れて、(その100年以上も前に発明されていたが、世に広く出回らなかったため、「新しい」となってしまった)「学芸協会誌」に論文を発表した。バベッジは「古くからある暗号だ」と主張。しかし、スウェーツは「ならば、この暗号を解いてみろ」と反論。解ける解けないと古い新しいは、全く関係なかったものの、バベッジはその挑戦を受けてたった。
解読に成功したのは、スウェーツとの論争のしばらく後の1854年だと考えられている。「考えられている」というのは、バベッジはこれを公表しなかったのである。1863年にカシスキー (Friedrich Kasiski) が、同じ手法を発見し、『暗号文と解読技術』という本にまとめて出版している。これをバベッジが先に発見したということは20世紀に入ってから分かったことである。長らくの間、この手法が「カシスキー・テスト」と呼ばれていたのもそのせいである。
バベッジが発表しなかったことについては、単にその気がなくなってしまっただけ、発見同時期に勃発したクリミア戦争を踏まえて、イギリスの情報局がバベッジに秘密にするように要請した(これが本当ならばイギリスはおよそ9年間、各国の機密情報を漏らさず知っていたことになる)、などの憶測を呼んでいるが、いずれも仮説の域を出ていない。