記事一覧

猫が寝床で水滴に? ヴィジュネル暗号って何ぞや?

ヴィジュネル暗号とは何か?

簡単にいえばある文章に他の文字列を融合させて暗号文を作る方法のことである。20行ほどのコードで実装できる古典的な暗号方法ではあるが、解読はそれなりに困難なので、チート防止のため配布するゲームのセーブデータを暗号化しておくなどの用途には充分に利用可能だ。

そこで本稿では、このヴィジュネル暗号のメカニズムについて解説する。

目次

▲PAGE TOP
長い記事になるので、まずは目次を置く。

 ・用語について
 ・シーザー暗号とは何か?
 ・シーザー暗号の作成法
 ・シーザー暗号の長所と欠点
 ・単一換字式暗号の弱点
 ・ヴィジュネル暗号とは何か?
 ・ヴィジュネル暗号の作成法
 ・文字数オーバーの場合の処理
 ・ヴィジュネル方陣
 ・鍵の文字数が足りない場合
 ・平文を変更しない文字の存在
 ・JavaScriptによる検証
 ・コーディング
 ・ヴィジュネル暗号の脆弱性
 ・鍵の周期性
 ・暗号表の対称性
 ・最後に

用語について

▲INDEX
詳細な解説に入る前に、本稿で使用される用語の意味を整理しておこう。

一般に暗号法において暗号にする前の文字列のことは平文ないしプレーンテキスト(Plain text)と呼ぶ。また文書を暗号にすることを暗号化もしくはエンコード(Encode)と呼ぶ。逆に暗号を元の平文に戻すことは復号もしくはデコード(Decode)と呼ぶ。

また、文字をアルファベット順に従い一定の数だけ進めたり戻したりすることをシフト(Shift)という。また、そのシフト回数を決定するために用いられる任意の文字列のことは(Key)ないし、鍵文字列(Key String)と呼ぶ。この2つの用語については後にも適宜説明する。

シーザー暗号とは何か?

▲INDEX
ヴィジュネル暗号について説明するには、まずより原始的な方法であるシーザー暗号について解説しておく必要がある。ヴィジュネル暗号はシーザー暗号を複雑化し解読をより困難にした改良形と呼ぶべきものだからだ。
Wikipedia記事へのリンク:シーザー暗号

シーザー暗号はユリウス・カエサル(英語読みでジュリアス・シーザー)が使用していたとされる最も古典的な暗号法である。この暗号では元の文章の文字と暗号文の文字がそれぞれ常に1対1で対応する関係にある。したがってこの暗号は単一換字式暗号の一種であるともいえる。
Wikipedia記事へのリンク:ユリウス・カエサル 単一換字式暗号

シーザー暗号の作成法

▲INDEX
シーザー暗号は、平文の各文字をアルファベット順に決められた文字数だけ進めることで作られる。たとえばCAPを4文字づつ進めてシーザー暗号をつくるとGETになる。Cの4文字後ろはG、Aの4文字後ろはE、Pの4文字後ろはTだからだ。むろん解読するときは文字を逆向きに戻せばよい。このように文字を進めたり戻したりして別の文字に入れ替える操作のことを一般にシフト(Shift)と呼ぶ。

シフトした結果アルファベットの範囲を超えてしまうときは先頭からループさせる。たとえばYを4文字シフトさせた場合には、返還後の文字はY→Z→A→B→Cと移動して「C」になる。WIZを4文字進めてシーザー暗号を作るとAMDになるというわけだ。

シーザー暗号の長所と欠点

▲INDEX
シーザー暗号は暗号化も復号も非常に容易である。そのため「読もうとすれば読めるが、一瞥した程度では何が書かれているか分からなくする」ときなどに良く使われる。たとえばシフトの回数を13に設定したROT-13(Rotate by 13 places)と呼ばれる方法がある。これは出題したクイズの答えなどを「一見しただけでは分からなくさせる」ための手段として外国の電子掲示板などで広く使われていた。
Wikipedia記事へのリンク:Rot-13

反面、シーザー暗号は少し知識があれば簡単に解読できてしまうため、文書を秘匿するなどの用途には適さない。平文のアルファベットと暗号文のアルファベットは1対1で対応しているので、最悪でも25回(文字数-1回)試行すれば平文に戻ってしまうからだ。

そのうえ欧米の言語では文章中に出現する文字の頻度は全く違う。「いちばん多く出てくるこの文字はきっとeだな」のような推測をされてしまうと、シフト数が判明することによりさらに容易に解読されてしまう。この方法は初歩的な頻度分析であるともいえよう。
Wikipedia記事へのリンク:頻度分析

単一換字式暗号の弱点

▲INDEX
単一換字式暗号とは、暗号文と平文の文字に常に1対1で対応する関係がみられるもののことをいう。そして、先述したようにシーザー暗号はこの単一換字式暗号の一種である。

単一換字式暗号は一般に頻度分析に極めて弱いという欠点を持つ。エドガー・アラン・ポーの「黄金虫」を嚆矢として、コナン・ドイルの「踊る人形」や、江戸川乱歩氏のデビュー作である「二銭銅貨」などといった古典的なミステリー作品では、まさにこの頻度分析による暗号解読が題材とされていた。
Wikipedia記事へのリンク:エドガー・アラン・ポー 黄金虫 アーサー・コナン・ドイル 踊る人形 江戸川乱歩 二銭銅貨

このような単一換字式暗号の欠点は、もちろん暗号を使用する側にも古くから認識されていた。そのため、この種の暗号を用いるにあたってはaやeのような使用頻度の高い文字には二文字以上を割り当てるなどの対処が行われることも多かったようだ。このような方法のことは度数秘匿方式と呼ぶ。

ヴィジュネル暗号とは何か

▲INDEX
このようにシーザー暗号のような単一換字式暗号は、安全性に問題があるものだった。

そこで中世の頃からより秘匿性の高い暗号への需要が高まり、単一換字式暗号の弱点を是正してより堅牢な高い暗号法を実現する必要が生じてきた。むろん先述の度数秘匿方式も、このような弱点を補強する目的で開発されたものである。しかし、度数非匿方式の暗号は必然的に暗号文に使われる文字種が増えてしまうという短所を抱えるものでもあった。

度数非匿方式の暗号を用いる場合、アルファベットで足りない分の文字は記号や数字などで補われる。場合によっては複数の文字をにして平文に対応させるなどの措置がとられることもあったらしい。この文字種の増加に伴うわずらわしさは、度数秘匿方式による暗号の大きな欠点であった。

そこでフランスの外交官であったブレーズ・ド・ヴィジュネルは、これまでと異なるまったく新しい方式の暗号を考案した。この暗号法において使用される文字の数は、平文で用いられる文字の種類数と全く同一である。そのうえその暗号は当時としては極めて秘匿性が強く、その後300年にわたって解読不可能な暗号(indecipherable cipher)の異名で呼ばれるほどに堅牢なものだった。この暗号こそが今日ヴィジュネル暗号と呼ばれているものである。

ヴィジュネル暗号は、一言でいえば文字ごとにシフトする回数が変わるシーザー暗号のことだ。文字ごとにシフトする回数を変えるので暗号化も復号も煩雑になる。そのかわりにシーザー暗号よりもはるかに解読が困難で堅牢性も高い。また、煩雑といってもそれはコンピューターのない時代においてのことだ。現代では長くとも20行程度のコードを組めば簡単に実装することができる。

ヴィジュネル暗号の作成法

▲INDEX
ヴィジュネル暗号では文字ごとにシフト回数が変わる。ではその回数は果たしてどう決定するのだろうか?

それには(Key)と言われる別の文字列を使う。この鍵はアルファベットのみで構成されてさえいれば任意の文字列でよい。ただし鍵に使用される文字の種類は少なくとも2種類以上である必要がある。1種の文字のみで構成された鍵で暗号化しても実質的にシーザー暗号と変わりが無くなってしまうためだ。

ヴィジュネル暗号は、おおむね以下のような方法で作られる。

 ・鍵とした文字列の先頭から一文字ごとに取りだす。
 ・その取りだされた文字が先頭の文字(A)から何回シフトされているかを数える。
 ・得られたその数値だけ対応する平文の文字をシフトさせる。

これを全ての文字について行えば、暗号化が完了する。

たとえば平文がCAT(猫)、鍵がBED(寝床)である場合には、暗号文はDEW(水滴)になるだろう。アルファベットの最初の文字(A)から数えてBは1番目、Eは4番目、Dは3番目である。よってCを1つ先に進めるとD、Aを4つ先に進めるとE、Tを3つ先に進めるとWになる。これを合わせればDEWとなるわけだ。

もちろん暗号文を平文に戻したい場合には同じ鍵をつかって文字をシフトした回数だけ戻せばいい

文字数オーバーの場合の処理

▲INDEX
シフトの結果としてアルファベットの範囲を超えてしまう場合には、シーザー暗号と同じように先頭からループさせる。プログラム上で文字をループさせるばあい、「まず暗号化された文字が先頭から何番目であるかを数え、26以上である場合には総文字数である26を引く」という処理がなされる。

たとえば平文TOYを鍵BEDで暗号化する場合を考えてみよう。YはAから数えて24番目の文字であるから、これを3つ先に進めると27番目の文字ということになる。このような場合は27から26を引いて「先頭(A)から1番目の文字」である「B」を暗号文とする。TOYBEDで暗号化した結果はUSBになるというわけだ。

もちろん暗号化のときに26を引いたのであるから復号のときは26を足す

たとえばBをDで復号する場合、Bは「Aから1番目」の文字であるから、3つ前に戻すと「Aからマイナス2番目」の文字になってしまう。このように復号の結果が負になるのは暗号化のときに26が引かれているからだ。この場合は26を足しなおせばよい。そうすれば先頭(A)から24番目の文字、すなわちYが得られるだろう。

ヴィジュネル方陣


このような暗号のルールを表にしたものはヴィジュネル方陣と呼ばれる。

暗号研究者である長田順行氏の著書「暗号」(1985年・社会思想社刊)によれば、この表はヴィジュネル暗号の考案以前からドイツの聖職者であったトリテミウスにより発表されていたものらしい。
Wikipedia記事へのリンク:長田順行 ヨハンネス・トリテミウス

しかしトリミテウスの考案した暗号は鍵を用いず「A~Z」の文字を順番に用いて一文字づつ暗号化してゆくものである。トリミテウスの方法では平文は常に同じ方法で暗号化されることになっていた。そのためトリミテウスの暗号法は鍵文字列自体を秘匿するヴィジュネルの方法に比べて、遥かに脆弱なものでしかなかったらしい。



ヴィジュネル方陣において上端の列は平文の文字を示しており、左端の行は鍵の文字を示している。平文の行と鍵の列の交わる場所にある文字が暗号化により得られる文字だ。たとえばMをLで暗号化する場合、Mの列とLの行が交わる場所の文字(X)が得られるだろう。



鍵の文字数が足りない場合

▲INDEX
ところで鍵の文字数が足りず、全ての文字を暗号化できない場合にはどうすればよいのだろうか?

もちろん最初から充分な長さの文字列を鍵として用意しておくというのも有効な方法である。平文より長い文字数の鍵を使用した場合には周期の問題がなくなり暗号の安全性が高まる。ゆえにコンピューター・プログラムで使用する場合にはこうした暗号鍵をメモリに保存しておけばよい。XorShiftメルセンヌ・ツイスタといった長周期の乱数生成方法を使用してそのつど鍵を生成してもよいだろう。
Wikipedia記事へのリンク:XorShift メルセンヌ・ツイスタ

しかし、ヴィジュネル暗号は当初は人間が用いる暗号だった。鍵の文字数があまりにも長くなるとこれを覚えておくのは困難になる。かといって紙などに記録すると他者に奪われる危険から秘匿性が弱まってしまう。鍵となる文字列を暗記しておきたい場合には短い文字列を鍵として用いる必要がある。

そこでヴィジュネル暗号については、その考案の当初から「平文の文字数が鍵の文字数よりも長い場合には、もういちど先頭の文字から順番に使用する」という方法がとられていた。たとえば暗号鍵がBEDであるとすれば、これをBEDBEDBED...のように繰り返すのである。

平文を変更しない文字の存在

▲INDEX
ところでアルファベットのうち先頭の文字である「A」だけは鍵に用いても平文の文字列を変更しない。これは「A」自身は「A」から数えて0番目であるためだ。上掲したヴィジュネル方陣を見ても明らかだが、「A」を鍵として用いた場合にはシフト回数はゼロとして計算される。そのため、Aを鍵として使用しても平文と全く変わらない文字が暗号に出力されてしまう

たとえば平文がWONDERLAND、鍵がALICEであるとするならば、暗号文はWZVFIRWIPHとなるだろう。暗号文の1文字目(W)は平文の1文字目(W)から変わっていない。もちろん暗号化に用いた鍵の1文字目が「A」であるためである。

先述のように、鍵の文字数が平文よりも少ないばあい最初の文字がもういちど使われる。そのためALICEを鍵として用いた場合には5文字ごとに平文と同じ文字が出現してしまう。そのため平文の6文字目と、暗号文の6文字目も同じ文字(R)である。

このように暗号文と平文に同じ文字が用いられることが望ましくないばあいには、あらかじめBEDのように「A」を含まない文字列を鍵として採用するべきである。文章を鍵として用いる場合でも「A」を飛ばして他の文字だけを羅列すればよい。たとえばThis is an appleという文章を鍵にしたいばあい、aを除外したthis is n ppleの11文字を鍵として用いればよい。

なお、後述するが、ヴィジュネル方陣のかわりにあらかじめ文字をランダムに配置した暗号表を用いる方法もある。もちろん、この場合にも任意のある一文字ならば平文と暗号文が偶然一致することはあるかもしれない。しかし上記のAのように「どの文字を暗号化しても平文と同じ文字になる」ことはまずない。この方法ならば上記の問題はほぼ解決するだろう。

JavaScriptによる検証

▲INDEX
検証用にJavaScriptを使ってヴィジュネル暗号を生成するフォームを作ってみた。
下記の手順で任意の英文を任意のキーで実際に暗号化してみることができる。

暗号化の方法:
 ・ 上部のテキストエリアに英文をペーストする。
 ・ 下部のテキストボックスに半角のアルファベットでキーを入力する。
 ・ 「暗号化」のボタンを押す。

平文:
Key:

このフォームでは、ボタンを押すたびに「暗号化」「平文化」が切り替わる。
よって、生成した暗号文は以下の方法でいつでも復号できる。

復号の方法:
 ・ ボタンが「復号化」になっている状態で、上部のテキストエリアに英文をペーストする。
 ・ 下部のテキストボックスに半角のアルファベットでキーを入力する。
 ・ 「平文化」のボタンを押す。


コーディング

▲INDEX
上記のフォームを動かしているコードは以下のようなものだ。
このコードは概ね以下のような手順で暗号化と復号を行っている。

 ・鍵から半角のアルファベットを一文字取得する。
 ・大文字であればAの文字コード(65)との差を、小文字であればaの文字コード(97)との差をとる。
 ・暗号化の場合はその値を加算し、平文化の場合は減算する。
 ・計算結果が範囲外のときは、26を加算・減算することで適切な範囲に値を収める。

なお、半角アルファベットの文字コードは、大文字が65~90小文字が97~122である。
文字コードがこの範囲に含まれるかどうかで、文字が半角アルファベットか否かが識別される。

ヴィジュネル暗号の脆弱性

▲INDEX
上述したようにヴィジュネル暗号は、少なくともシーザー暗号よりは安全な暗号であるといえる。
しかしヴィジュネル暗号にもなお下記のような脆弱性が存在する。

 ・ 鍵に周期性があること
 ・ 暗号表に対称性があること

このような脆弱性に対処するにはどうすればよいのだろうか?

鍵の周期性

▲INDEX
ヴィジュネル暗号の脆弱性の一つとして鍵に周期性があることがある。暗号文の周期が判明してしまえば、その数ごとに文字を切り分けてから古典的な頻度分析にかけることで解読できるからだ。この周期を割り出すための方法としては、「暗号文中で反復している文字列の間隔から周期を推定する方法」(いわゆるカシスキー・テスト)などが知られている。

しかし、鍵に平文と同じ長さの文字列を使えば、周期によって解読されることはなくなる。たとえば暗号送信者と受信者が同じ辞書を持っているとき「その辞書の10ページ目の冒頭から順に鍵として用いる」などの方法をとれば、第三者が周期を割り出すことは不可能になるだろう。

さらに受信者と送信者が鍵文字列を羅列した本を一冊づつ持ち、通信後に暗号解読に使用したページは破り捨てるなどの方法をとることもできる。ここまですれば、その暗号を解読することは理論上不可能になるだろう。これはワンタイム・パッドと呼ばれる考え方だ。
Wikipedia記事へのリンク:ワンタイムパッド


暗号表の対象性

▲INDEX
暗号表に極めて強い対称性があることもヴィジュネル暗号の脆弱性とされる。
これを解消するには下の画像のように文字をランダムに配置すればよい。



もちろん各行・各列に異なる文字を一つづつ使用しなければならないため、その意味での対称性は残る。しかし、このように文字をバラバラに配置することによって、より高度な解読方法である線形解読法差分解読法にもある程度の耐性を持たせることができるだろう。
Wikipedia記事へのリンク:線形解読法 差分解読法

最後に

▲INDEX
かつてヴィジュネル暗号は暗号・復号に非常に手間がかかる方法であるとされていた。しかしコンピューターを使用すればこの暗号は非常に短いコードで実装可能だ。

一方、この暗号の解読は現在でもそれなりに難しい。冒頭で述べたようなセーブデータを暗号化しておくなどの用途にはまさに最適の方法であろう。

そうした暗号の使用にあたって本稿が一助になれば幸いである。
スポンサーサイト

コメント

コメントの投稿

非公開コメント