ヴィジュネル暗号

出典: フリー百科事典『ウィキペディア（Wikipedia）』

ブレーズ・ド・ヴィジュネル

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

1 発明
2 暗号化・復号の仕方
- 2.1 数式でみる暗号化・復号
3 ヴィジュネル暗号の解読
- 3.1 カシスキー・テスト
- 3.2 鍵推理による解読法
4 ヴィジュネル暗号の弱点と暗号史に与えた影響
5 解読のエピソード
6 ヴィジュネル暗号の登場する作品
7 参考文献

[編集] 発明

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

[編集] 暗号化・復号の仕方

ヴィジュネル方陣：最上段の行が平文、左段が鍵。平文がC、鍵がaの場合、最上段がCの列、左端がAの行の交わったcが暗号文になる。

右図（ヴィジュネル方陣）を使って暗号化を行う。以下、平文を大文字、暗号文を小文字で表す。

例として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 = \left(P_i + K_i \right) \bmod 26$

また $P i$ を求める式は、

$P_i = \left(C_i - K_i + 26 \right) \bmod 26$

となる。

発明当時は暗号化、復号が「難しい」とされてきたヴィジュネル暗号であるが、このように、加減算と剰余の計算ができれば済み、また、10行足らずのコードを書くだけでコンピュータに計算を任せることができる。

[編集] ヴィジュネル暗号の解読

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

[編集] カシスキー・テスト

この解読法を発見したのはコンピュータの原型を造ったチャールズ・バベッジであるが、これにもエピソードがある(解読のエピソードにて)。

解読方法は、頻度分析よりも難しくなるが、不可能ではない。しかし、前述の「cfpe」など、短すぎる場合はほぼ解読できない。以下は、相当長い暗号文が与えられ、しかもそれがヴィジュネル暗号だと分かっているときの解読法である。

方法

まず、同じ文字の(反復している文字の)羅列を探る。(ただし頻度分析ではないので、cが多いなどは関係ない)また、文字列は長いほうが確実である。(1文字から3文字程度ならいくらでも現れる可能性があるので)
次にその羅列の間隔を数える。(例えば、cdfkkuihycdfkgの場合、cdfkが反復して現れる。この間隔は9である。
以下、同じように探していくと発見された文字間隔が例えば、9、63、180、であったとき、この三つの数に共通する因数は3と9である為、鍵の文字数は3か9であると仮定できる。
すると、この暗号の最大の関門、鍵の文字数が分かってしまったのだ。すると、頻度分析が使える(ここでは、文字数を3としたが、それで答えが出なければ9でやってみる)。つまり、間隔が3の文字同士は、同じ行のヴィジュネル方陣が使われているということだ。
頻度分析にかけるが、大事なのは1つだけの行を使った場合、単なるシーザー暗号になるということだ。つまり、暗号文の3の間隔同士の文字の頻度をグラフで見ると、平文で行った頻度分析と似ているようで似ていない形になる。しかし、シーザー暗号を使っているということは、文字いくらかずらせば、平文の頻度解析を行ったものとほぼ同じになる。
以上を使うとほぼ、ヴィジュネル暗号を解くことができる。

解説

「反復している文字の羅列」というのは、平文が同じ文字のとき、同じヴィジュネル方陣の行に当たって出来たものと考えられる。
「間隔を数える」。その通りである。
「共通の因数を求める」これは、平文が同じであった場合、使われている鍵は、その間隔の因数でなければいけないからで、逆を言えば、鍵の文字数の倍数でなければならないからだ。
「文字数が分かる」これは、ヴィジュネル暗号の最大の欠点である。これを突破できれば、昔ながらの解読法で解ける。
「頻度分析にかける」シーザー暗号と聞いて、「なんだ26つしか鍵がないから全て調べればいいじゃん」と思うかもしれないが、これは、続いた文字列ではないことに注意してもらいたい。全て調べても、意味がある言葉にはなり難い(等間隔で文字を拾ったのだから、平文でも意味が分からない)。これを全て調べる場合、鍵の文字数をnとしたとき、26のn乗を調べなくてはならない。
「解くことができる」しかし、文章が短くなると難しい。

[編集] 鍵推理による解読法

例えば、暗号文「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になる。これが、解読者にとって唯一の手がかりだった。鍵の周期性の問題性に気付かなかったのは、よりアルゴリズム(暗号化の方法)を複雑にすることによって安全にしようとしていたからで、誰も「鍵」の重要性に気付いていなかったのである。では、鍵長を平文と同じにしたら、完全か。確かに、周期性の問題は解決する。しかし、上記のように周期が起こらない鍵であっても、推理することによって解決する場合がある。

そのため、この問題を乱数を利用することで打開しようとしたのだ。また、その数も多くすれば一つの周期も長くなるため、鍵の長さは膨張の一途をたどっていくようになる。また、後に、人力では限界が見えてきた時代に「暗号を行う機械」も出てくるが、これも、周期の長さ、鍵が乱数であることが、大きな目標とされた。

現在の暗号においても、鍵が乱数であるかは、最も重要とされ、アルゴリズムが公開されているからこそ、偏った数を鍵に使用すると、すぐに解読されてしまう。また、鍵の長さも、安全性をはかるものさしとなっている。

[編集] 解読のエピソード

チャールズ・バベッジが解読方法を探った理由は単純なものだった。ある日、「私は新しい暗号を発明した」という人物（ジョン・ホール・ブロック・スウェーツといわれている。一般人）が現れて、（その100年以上も前に発明されていたが、世に広く出回らなかった為、「新しい」となってしまった）「学芸協会誌」に論文を発表した。バベッジは「古くからある暗号だ」と主張。しかし、スウェーツは「ならば、この暗号を解いてみろ」と反論。解ける解けないと古い新しいは、全く関係なかったものの、バベッジはその挑戦を受けてたった。

解読に成功したのは、スウェーツとの論争のしばらく後の1854年だと考えられている。「考えられている」というのは、バベッジはこれを公表しなかったのである。1863年にカシスキー（en:Friedrich Kasiski）が、同じ手法を発見し、『暗号文と解読技術』という本にまとめて出版している。これをバベッジが先に発見したということは20世紀に入ってから分かったことである。長らくの間、この手法が「カシスキー・テスト」と呼ばれていたのもそのせいである。

バベッジが発表しなかったことについては、単にその気がなくなってしまっただけ、発見同時期に勃発したクリミア戦争を踏まえて、イギリスの情報局がバベッジに秘密にするように要請した（これが本当ならばイギリスはおよそ9年間、各国の機密情報を漏らさず知っていたことになる）、などの憶測を呼んでいるが、いずれも仮説の域を出ていない。

[編集] ヴィジュネル暗号の登場する作品

アンフェア the special 『コード・ブレーキング～暗号解読』

登場する暗号がヴィジュネル暗号とされ、暗号化の方法が解説されているが、単なるパスワード入力であり、何ら関係ない。

[編集] 参考文献

サイモン・シン著、青木薫訳『暗号解読 - ロゼッタストーンから量子暗号まで』新潮社 ISBN 4-10-539302-2

"http://ja.wikipedia.org../../../%E3%83%B4/%E3%82%A3/%E3%82%B8/%E3%83%B4%E3%82%A3%E3%82%B8%E3%83%A5%E3%83%8D%E3%83%AB%E6%9A%97%E5%8F%B7.html" より作成

カテゴリ: 暗号