TOUCH THE SECURITY Powered by Security Service G

コラム

2019.03.22

近代暗号物語 ――コンピュータの父・チャールズバベッジが挑んだビジュネル暗号 2/2

写真:サイエンス・ミュージアム(ロンドン)に展示される、チャールズバベッジの肖像と「能」 / Alan Levine from Strawberry, United States [CC BY 2.0]

19世紀の英国の数学者チャールズ・バベッジ(1791~1871)は、人類で初めてプログラム可能な計算機「解析機関(アナリティカル・エンジン)」を考案したことから、コンピュータサイエンスの分野ではよく知られた偉人だ。

ここでは、チャールズ・バベッジの数ある功績の一つとして挙げられる、ある暗号の解読について取り上げてみたい。

(後半)

1.ビジュネル暗号の周期性 ――バベッジの着眼点

1/2より続き)

バベッジはこのビジュネル暗号の攻撃手法を開発した。注目をしたのは、同じ文字列が繰り返し登場する周期性だった。

例えば、鍵語「PERSOL」を使って、hackという文字列が繰り返す原文を暗号化してみる。当然hackはいろいろな文字列に変換される。しかし、まったく同じ文字列に変換されることもある。6文字の鍵語と4文字の原文が、うまくシンクロして、鍵語の同じ部分で暗号化されているからだ。

ビジュネル暗号では、同じ単語が同じ暗号文になるとは限らない。しかし、鍵語とうまくシンクロして、鍵語の同じ部分が使われて暗号化された場合は、同じ暗号文になる。ここから、同じ文字列の距離を調べると、鍵語の文字数が推測できる。この図ではwetzv…という同じ文字列が、12文字の距離(wからwまでを数える)になるので、鍵語の文字数は12、6、3、2、1のいずれかであると推測できる。

バベッジは、暗号文の中に同じ文字列が出現するのは、同じ単語がうまく鍵語とシンクロして、同じ暗号文に変換された可能性があると考えた。ということは、同じ文字列の間の距離(文字数)は、鍵語の文字数の倍数になっていなければならない。

つまり、同じ文字列、同じ文字の距離を数え統計を取り、その距離の最大公約数が鍵語の長さになると推測できる。鍵語の長さが、例えば6文字だと分かれば、暗号文の6文字ごとの文字頻度を数えれば、いちばん多いのがeであるという推測が出きていくことになる。単純な換字暗号から比べれば、解読にはたいへんな労力がかかることになるが、外交電文や軍用電文などは、それだけの手間をかけても解読したいと考える人は多いだろう。

ビジュネル暗号を使った暗号文。見やすさを考えて、5文字ごとに分けて並べている。この中に繰り返し登場する文字列がいくつかある。xywは3回登場する。これは原文の同じ単語が暗号化された可能性がある。この文字列の距離(文字数)から、鍵語の文字数が推測できる。

2.カシスキーテスト

この性質を利用して、暗号文から同じ文字列、同じ文字の距離を数える攻撃手法は、カシスキーテストと呼ばれる。この名称は、10年後にドイツの暗号解読者フリードリッヒ・カシスキーが独自に発見、公表した結果に基づく。

バベッジ自身はこの手法を発見していても、公表しなかった。本人が大した発見だとは思っていなかったとも、イギリス陸軍が非公表にすることを命じたとも言われる。

繰り返し登場する文字列、文字の距離(文字数)を数えるカシスキーテスト。6文字置き、2文字置き、3文字置き、12文字置きに同じ文字列、文字が登場することが多い。鍵語の文字数はこのような数の公約数である可能性が高い。

3.「クリブ」という着眼点から鍵語を推測

これが突破口となり、次々とビジュネル暗号の攻撃手法が開発されていく。その中でも、有力だったのがクリブ攻撃だ。

クリブとは「虎の巻」といったような意味。暗号文の種類によっては、原文に使われていそうな単語を推測できることがある。

例えば、軍用電文であれば、「ロンドン」「リバプール」といった地名、「快晴」「濃霧」といった気象用語が使われている可能性が高い。そこで、Londonであれば、暗号文の1文字目から6文字目までがLondonだと仮定し、ビジュネル方陣を逆算して、どのような鍵語になるかを調べてみる。

鍵語は意味のある単語が使われることが多いので、この推測した鍵語がデタラメな文字列であれば攻撃は失敗。次に2文字目から7文字目までがLondonではないかと仮定して同じことを繰り返していく。もし、原文のどこかにLondonが使われていれば、どこかで意味の通る鍵語が現れるはずだ。

もちろん、暗号を使う側もさまざまな対策をし、ビジュネル暗号も進化をしていった。頻出する単語London、Liverpoolは、LDN、LVPなどという略号にするのは軍用電文では基本中の基本になっている。

4.ビジュネル暗号も進化、鍵語を原文へ内包

さらにビジュネル暗号も自己鍵式と呼ばれるものが考案されたりした。これは原文の先頭部分は、PERSOLなどの定められた鍵語で暗号化するが、それ以降は原文の文字列を鍵語に使って暗号化する方式だ。受信者は定められた鍵語で暗号文の解読を始めると原文が現れるので、以降はそれを鍵として解読していけばいい。一般のビジュネル暗号のような周期性は稀にしか現れないので、カシスキーテスト攻撃が通用しない。

自己鍵を使ったビジュネル暗号。暗号化する時は、鍵語に続いて、原文そのものを鍵語として使う(上)。復号化する時は、まず定められた鍵語で解読、原文が現れるので、以降の鍵として復号化を進めていく(下)。同様の暗号強度を増すテクニックは、エニグマ暗号でも使われた。

5.クリブとエニグマ暗号

暗号技術は、考案者と解読者の知恵比べで進化をしていく。

大きな転換点が、1925年にドイツ軍に採用されたエニグマ暗号機だ。アルファベット26文字分の歯がついた歯車3枚によって暗号化がなされる。3枚の歯車はリムーバブル方式になっていて、暗号機にセットする順番も変えることができる。つまり、(3×2×1)×(26×26×26)=10万5456通りの変換方法があることになる。

WW2における最強の暗号生成機、ナチスドイツのエニグマ

といっても原理はビジュネル暗号と根本のところは変わらず、ただ鍵語の長さが10万5456文字になるため、カシスキーテスト攻撃が通用しない。

このエニグマ暗号もドイツ軍は「解読不能」と謳っており、敵の前線の弱点に爆撃機と戦車を一点集中させる電撃作戦、敵輸送船団にUボートを一点集中させて攻撃する群狼作戦が可能になったのも、エニグマ暗号により前線部隊同士で安全に通信ができ、密な連携が可能になったからだ。

ドイツの敵国であったポーランドの暗号解読者マリヤン・レイエフスキーは、バベッジのアイディアとは異なるが、やはりエニグマ暗号の周期性を探って、これを元に解読をしようとした。その周期性を発見するのは、紙とペンでは無理な話で、ボンブと呼ばれる機械まで開発している。

イギリスの暗号解読拠点「ブレッチリーパーク」で暗号解読の仕事をしていた数学者アラン・チューリングは、エニグマ暗号をクリブ攻撃の手法で解読しようとした。そのために電子式のボンブを開発した。

さらに、ドイツ軍は、電子式の暗号機を開発し、ビット演算をするローレンツ暗号を使い始めた。

エニグマよりも更に複雑な構造であったローレンツ暗号機

ブレッチリーパークのトミー・フラワーズは、このローレンツ暗号にクリブ攻撃をするために、電子式の解読機械「コロッサス」を開発した。このコロッサスが世界で最初の電子計算機であるという人もいる。

クリブ攻撃解読が試みられたローレンツ暗号の解読機コロッサス

6.そして現代へ

バベッジが紙とペンと思索で解読した暗号は、第2次世界大戦中に機械式、そして電子式に急速に進化した。

コロッサス以降、電子計算機も急速に進化し、今、私たちが使っているコンピュータやスマートフォンにつながっている。今や、SSLやRSAといった暗号技術は、ネットショッピングやオンラインバンキングをするにはなくてはならないものになっている。バベッジの時代から200年、暗号技術は常に進化を続けている。

記事一覧に戻る