この記事は古典暗号の中でも複雑で解読しにくいとされている多表式換字式暗号であるVigenere暗号と、多くの場合に効果的な解読法であるカシスキー・テストを理解することを目標に書く。

Vigenere暗号

Vigenere暗号は頻度分析が発達し単一換字式暗号がある程度簡単に破られるようになってきた頃に発明された。名前は最終的な発明者であるBlaise de Vigenèreの名を取っている。(便宜上VigenèreではなくVigenereと書いているが、正しいのはVigenèreである。)

古典的な見方

この暗号は、多表式換字式暗号の形を取っている。そのため、同じ文字でも場所が違えば違う文字に暗号化される。

最初に、暗号鍵を決める。これはアルファベットであれば何でも良いが、安全性のためにはできるだけ長い方がよい。また、暗号鍵は平文の大きさに合わせて繰り返して使う。例えばCTFという暗号鍵を長さ7の平文に適用する場合、実際に使われる暗号鍵はCTFCTFCになる。

Vigenere暗号は、Vigenere方陣と呼ばれる以下の表を用いて暗号化される。

この表は、最上段を平文、左段を暗号鍵、それ以外が暗号文として扱われる。

例として、VIGENERE CIPHER IS POLYGRAPHIC SUBSTITUTION CIPHERという文章をCTFという鍵で暗号化することを考える。

1文字目は平文がV, 鍵がCなので横列がV, 縦列がCの位置にあるXが暗号文
2文字目は平文がI, 鍵がTなので横列がI, 縦列がTの位置にあるBが暗号文 ...

というように暗号化していく。最終的な暗号文はXBLGGJTX HKIMGK NU ITNRLTTUJBH UNGUMNVNYKHS EBUJXWとなる。

最初に書いたように、この方法はある文字が幾つもの文字に入れ替わる可能性がある。そのため、非常に解読が難しい暗号となっている。復号については暗号文と鍵から一意に平文が定まるため、単純に表を反対に見れば良い。

数学的な見方

数学的にVigenere暗号を考える。まず、Vigenere方陣に注目すると、1列目(暗号鍵がAの時)はそのまま、2列目(暗号鍵がBの時)はB, C, D, ...のように1つずれていることがわかる。シーザー暗号のように考えれば良いかも知れない(key = 1のシーザー暗号と同じ)。同様に3, 4, ...列目はk=4, 5, ...のシーザー暗号の配列と同じだ。

ベクトルを用いて考えてみる。暗号化鍵の配列をベクトル\(\vec{k}\)、平文の配列をベクトル\(\vec{p}\)とすると、次のように書くことができる。

\( Enc(\vec{p}) := \vec {p} + \vec{k} \mod 26 \)

実例を挙げてみる。平文がWEARECTFER、つまり数列にすると(22, 4, 0, 17, 4, 2, 19, 5, 4, 17)とし、暗号化鍵をESHIHOつまり(4, 18, 7, 8, 7, 14)を必要なだけ伸長したものとする。計算すると次のようになる。

鍵の長さは平文よりも短いので、伸長する。伸長後の鍵は(4, 18, 7, 8, 7, 14, 4, 18, 7, 8)となる。
\(Enc(\vec{p})\)を計算する。

\( \begin{align} \vec{p} &= (22, 4, 0, 17, 4, 2, 19, 5, 4, 17)\cr \vec{k} &= (4, 18, 7, 8, 7, 14, 4, 18, 7, 8)\cr \vec{p} + \vec{k} \mod 26 &= (0, 22, 7, 25, 11, 16, 23, 23, 11, 25) \end{align} \)

アルファベットに変換すると、AWHZLQXXLZとなる。これが暗号文である。平文の配列をベクトル\(\vec{c}\)、暗号化鍵の配列をベクトル\(\vec{k}\)とした時に復号関数Decを次のように定義する。

\( Dec(\vec{c}) := \vec{c} - \vec{k} \mod 26 \)

これはEncの自明な逆関数となっている。実例は省略する。

カシスキー・テスト

カシスキー・テストとは、最初にチャールズ・バベッジが考案したVigenere暗号の効率的な解読法だ。バベッジが公開する前にカシスキーが公開したという歴史的背景から、カシスキー・テストと呼ばれている。今回はある英文を暗号化した以下の文章を解読する。

OWBSEOLUSIGTPZHUPJDMTBIPEDKPFRUWGYSBPBYHIQTQENQMJRPIIHETISTKIBFZYTUBYFMINPPFATLQPVHELFXFZTMMPQLJAUTQFIOOLFEBWOFLGLMUPGFPMGXTXIOPORPIISEEBICIFAPYWTPFXLBUBYHKIQSIUPOZAUPFPESBIHETKPCVVXUTRHWEDWJOIEEOLXLWGCMWSGDJZPFVDPKPLTLAIWXNSSZVAXUPFPESBISEEJFNSNMGZVBTMELFXFZTMMPYIBZUSLBLDZVSCQEIEBIPMSEBJWTWHZHTIJOXPVPLLJINRSJVHESQCULRFVEESBTMAIPXMPJPZUSIFISELJAGTPMMEHMUPWTSMMONICMDLYTMPQXIMNTENAVCIMGHZMOOUZHFAUCSZJPELUPFXEOLUSIFISELTWNLOFGPFVTMMQEOISVSGKZAVFATHSPLNLOFZPZQTQOTXBVENSBBJEAJBIAMUKITRTQEPEOLPFXUPJDMTPPHCPCBCIUWCFMMLJEXIMBCOJAUZFFBICIFPVYHSMENYCQUDPPVHQMGBZNYCQUDAJLFLREBITVUGDFFJBTSMHPNLOFISZSGNPCMUTFLZJVHMIMWXELFZPZJBVPAIOQORSOMDFFJBITKIIMWESWVYHQCULHPWSTRUPFDMEMPQXIMBCOBVEXELMMZAFZNTHETFLRECQAISLFNOTQBXKPQORXPJSTRHNMZSEEBEISAPYXIMFLVUPUZHFAUCSZIMWPJNFFREMSELFPFLZFVTPZFZZNVFIUFVFBILXIITELFJSPEUPPQPJNFTRJBFGISGUSMOOPYIBZUSAJTMAISQTSFVBJHMMTFDXBJMTWIUZNSWMOLRUEJELZWVLREGPFAJTMPRUMSELFISVCPCBYHZWVCWPVTLREGPFVXQGPEOLZZYSAPYWXQWPWXQUSCPCZZYBZFESCZJYKJVUZXIMBCOUEPZJBTMWMWQORGSMBEYSMTXEMMBYHGMNLPFBPVIFXUSINIMTZFEJELZWVEAPWGPZFZZVMOLPQFJZEZJFDFCCLQOOSGIOTQBTBYHPNFGISGLTREWGNVFIUFVFBILXNWWPWBTPYKUPFRVPCOOAJTMNSNMUZCPCUZFFSFAXBTJGIZWVLVFBPEELMFGISGLTREWGQSPLUSEUQTESCMFLXFVBYHTBPCIJBBHEZITQSPLGZVZWVLRENPCXIMN

この方法は、暗号文のみから鍵を推定することを考えたものである。鍵の繰り返しがキーとなっているため、非常に長い(大体鍵の長さが1/2以上)場合には効力を発揮しない。

最初に、間隔を開けて何度か繰り返されている文字列を探す。例で考えると、ELFという文字列が6回繰り返されていることがわかる。ここでは、この文字を使う。
次に見つけた文字列同士の間隔を見る。ここではELFの間隔を数える。すると、次の結果が得られる。

1つ目から2つ目: 170
2つ目から3つ目: 360
3つ目から4つ目: 150
4つ目から5つ目: 30
5つ目から6つ目: 95

これが何を意味するのだろうか。これらは、ELFという文字列の元が同じ文字列だと仮定すると、同じ鍵で暗号化されているものだろうと考えられる。つまり、この間隔は鍵の長さの倍数だと考えられる。これらの公約数を取ると、5という数値が出る。これは、鍵の長さが5であることを仮定できる材料となる。
鍵の長さがわかれば簡単だ。というのも、Vigenere暗号の性質として鍵がn文字周期であるなら、n文字毎に同じ鍵が使われる事になる。更に、数学的な見方で書いた通り、一文字単位で暗号化処理を見るとシーザー暗号に他ならない。つまり、Vigenere暗号の解読問題がシーザー暗号の解読問題に変換され、結果的に26^鍵の長さという大きさまで鍵の候補の量を減らすことが出来た。
ここで、頻度分析を利用することを考える。文が英文であることは与えられているため、英文の頻度分析を用いてシーザー暗号の鍵を割り出すことができる。
以上によって、かなりの割合でVigenere暗号を解読することができる。

カシスキー・テストは非常に強力で、鍵の長さの制限さえ通れば殆どの場合に適用できる。なお、今回の例では平文をGenesis 6 NIV - Wickedness in the World - When human - Bible Gatewayより引用させて頂いた。暗号化鍵は、このカシスキー・テストを利用して探してみて欲しい。