暗号化アルゴリズム

(2) 暗号機の発達

前回は、第一次大戦前までに利用されてきた暗号について紹介しました。中世までは、暗号作成者が平文の文字をひとつずつ手作業で暗号文字に変換していましたが、20世紀になって電気工学が発達すると、それを利用した暗号化処理ができるようになりました。いわゆる「暗号機」の誕生です。
第二次世界大戦時、ドイツの「エニグマ」をはじめ、日本の「パープル暗号機」やアメリカの「シガバ暗号機」など様々な暗号機が活躍しました。この暗号を解読する作業は、戦局を大きく左右するほどの重要な役割を果たしており、もし連合国による暗号解読が失敗していれば、戦争は大幅に長引いていただろうとも言われています。

この章では、ドイツが利用した「エニグマ」の仕組みと、連合国がどのようにそれを解読したのかを中心に紹介したいと思います。

1) 暗号円盤

前章で紹介した多アルファベット暗号は、手作業での暗号化・復号化が面倒であることから普及するのに時間がかかりました。この作業の負担を軽減するために、多アルファベット暗号の生みの親であるアルベルティが考案したのが暗号円盤と呼ばれる暗号機で、暗号機としては最も古いものになります。
暗号円盤の構造は非常に単純で、アルファベットが周囲に並んで記述された大小二つの円盤を重ねて、中心をピンで留めた形になっています。内側と外側にアルファベットが並んだ構造になるので、内側の円盤を任意の位置まで回転させれば、カエサル暗号に利用することができ、さらに、キーワードに従って位置を変化させることで、ヴィジュネル暗号にも利用することができます。

暗号円盤の構造は単純ですが、暗号化作業を効率よく行うことができる実用的な道具であり、実際にアメリカの南北戦争でも利用されていました。

2) エニグマ

1918年、ドイツの技術者であるアルトゥール・シェルビウス(Arthur Scherbius)は、親友のリヒャルト・リッター(E. Richard Ritter)と会社を設立し、その中で新しい暗号機を発明しました。この暗号機こそが、第二次大戦中にドイツ軍によって利用されていた「エニグマ(Enigma)」でした。
シェルビウスが目指したものは、今まで手作業で行われていた暗号化と復号化の処理を当時の最新技術によって効率よく行うことができ、さらに解読が非常に困難な暗号機を作成することでした。エニグマが完成すると、彼は、軍部とビジネス界に対してそれを売り込み始めました。強力で解読不可能な暗号機は大きな需要があるに違いないと考えていたわけですが、実際には、エニグマが高価だったこともあって売り込みに失敗、最初はほとんど売れなかったようです。
ドイツ軍がエニグマの購入に踏み切ったのは、第一次大戦時のドイツ軍の暗号がイギリスに傍受・解読されていたことに気づいてからでした。1925年、シェルビウスはエニグマの大量生産を開始し、その翌年、ドイツ軍はエニグマを暗号機として採用しています。

エニグマは、いくつかの部品から構成されています。入力した文字をスクランブルするためのローター(Rotor)、文字を入力するためのキーボード(Keyboard)、暗号化した文字をランプで示すためのランプボード(Lamp Board)、入力された電気信号をスクランブルしつつ逆順に送り返すためのリフレクタ(Reflector)、そしてキーボードからローターへの電気信号の流れをスクランブルするためのプラグボード(Plugboard)を組み合わせることで、複雑なスクランブル処理を行うことが可能になっています。

2-1) ローター

エニグマの中で、ローターは非常に重要な役目を担っています。ローターは、内部をワイヤで配線した円盤形の部品で、円盤の片側から入力された電気信号が配線を通ってもう一方より出力されるのですが、この配線がスクランブルされており、ローターを一つ使うことで、単アルファベット換字式暗号化処理ができるようになっています。さらに、ローターは一文字入力する度に一文字分ずつ(アルファベットが円盤に並んでいるのであれば26分の1)回転するようになっているため、同じ文字を入力したとしても、ローターに入力する箇所は毎回変化することになります。これで、ローターを使って多アルファベット換字式暗号化処理が実現できることになります。
しかし、これだけでは、ローターが一回転する度に同じパターンが繰り返されることになるため、ヴィジュネル暗号と同じ弱点を持つことになります。そこで、この弱点を補うため、エニグマではローターを三つ組み込んで、スクランブルの仕方をさらに複雑にしました。第一のローターが一回転すると、第二のローターが一文字分だけ回転し、さらに第二のローターが一回転すると第三のローターが一文字分だけ回転するようになっているため(車の走行距離計と同じ仕組みです)、ローター内の配線の組み合わせはアルファベット全てが円盤上に並んでいる場合

26 X 26 X 26 = 17,576通り

になります。さらに三つのローターの配置も変更が可能になっていて、例えば一番めと三番めのローターを入れ換えるようなこともできるため、配置の仕方は6通りになり、それを掛けると配線の組み合わせは105,456通りにもなります。

左側の状態では、例えばAを入力すると、三つのローターを通過した結果Dが出力されます。一文字を入力すると、一番右端にあるローターは一文字分回転し(図では下側にシフトしています)、配線構造が変化します。その結果(図の右側の状態)、同じAを入力しても結果はDではなくFになります。

以下にローター部のサンプル・プログラムを示します。今回はC++を使い、部品ごとにクラスを作成してからそれらを組み合わせてエニグマ装置を組み立てる形式を取ってみたいと思います。オブジェクト指向言語もJavaやC#をはじめとしてかなり普及しているので、もはやC言語にこだわる必要もないと判断しての変更になります。

/* swap Vectorの要素を交換する vector<T>& vec : 対象のVector unsigned int i1, i2 : 交換する要素のインデックス */ Template<class T> bool swap( vector<T>& vec, unsigned int i1, unsigned int i2 ) { if ( i1 >= vec.size() || i2 >= vec.size() ) return( false ); if ( i1 == i2 ) return( true ); T buff = vec[i1]; vec[i1] = vec[i2]; vec[i2] = buff; return( true ); } /* エニグマ用ローター */ class Rotor { vector<unsigned int> inShift; // 入力時のシフト量 vector<unsigned int> outShift; // 出力時のシフト量 unsigned int location; // ローターの位置 public: // コンストラクタ Rotor( unsigned int length, unsigned int randomizeCount = 1000 ); unsigned int size() const { return( inShift.size() ); } unsigned int encode( unsigned int i ) const; // 暗号化 unsigned int decode( unsigned int i ) const; // 復号化 bool rotate(); // ローターを回転させる void init() { location = 0; } // ローター位置の初期化 void init( unsigned int i ) { location = i % size(); } // ローター位置の初期化 unsigned int current() const { return( location ); } // ローターの現在位置 }; /* Rotor コンストラクタ unsigned int length : ローターの文字数 unsigned int randomizeCount : ローターの配列をスクランブルする回数 */ Rotor::Rotor( unsigned int length, unsigned int randomizeCount ) : location( 0 ) { for ( unsigned int i = 0 ; i < length ; i++ ) inShift.push_back( i ); outShift.resize( length ); for ( unsigned int i = 0 ; i < randomizeCount ; i++ ) { unsigned int i1 = (unsigned int)( (double)rand() * length / ( (double)RAND_MAX + 1 ) ); unsigned int i2 = (unsigned int)( (double)rand() * length / ( (double)RAND_MAX + 1 ) ); swap( inShift, i1, i2 ); } for ( unsigned int i = 0 ; i < length ; i++ ) { int value = inShift[i]; value -= i; if ( value < 0 ) value += length; inShift[i] = value; outShift[( i + value ) % length] = value; } } /* Rotor::encode 暗号化 unsigned int i : 入力位置 戻り値 : 出力位置(範囲外の場合は入力位置をそのまま返す) */ unsigned int Rotor::encode( unsigned int i ) const { if ( i >= size() ) return( i ); i += inShift[( i + location ) % size()]; i %= size(); return( i ); } /* Rotor::decode 復号化 unsigned int i : 入力位置 戻り値 : 出力位置(範囲外の場合は入力位置をそのまま返す) */ unsigned int Rotor::decode( unsigned int i ) const { if ( i >= size() ) return( i ); i += size() - outShift[( i + location ) % size()]; i %= size(); return( i ); } /* Rotor::rotate ローターを回転させる 戻り値 : 回転後に元に戻ったらtrueを返す */ bool Rotor::rotate() { location++; if ( location >= size() ) location = 0; return( location == 0 ); }

ローターは、入力と出力とのずれ量(inShiftとoutShift)で表現しています。コンストラクタでは、引数として渡された文字数を元に0から始まる整数列を用意して、これをランダムにスクランブルします。その後、スクランブルした数列の各要素とその位置との差をシフト量としてinShiftに登録すると同時に、inShiftの位置に要素を加えた値をoutShift上の位置として(これが出力位置を意味することになります)、その位置に、inShiftに登録したシフト量と同じ値を登録します。
シフト量は必ず正の整数となるように、シフト量が負になった場合は数列のサイズを加えます。また、outShiftの位置を決めるとき、サイズを越えた場合は逆にサイズ分だけ引き算をします。説明だけではわかりにくいと思いますので、下図を参考にしてください。

入力値 in を暗号化する場合は、inShift[in]をinに加えることで処理することができます(この時、数列のサイズを越えた場合はサイズ分だけ引き算します)。逆に、反対側から入力したデータ out を復号する場合は、outShift[out]をoutから引くことで処理することになります(負数の場合はサイズを加算します)。要素をシフト量で表しているのは、ローター自体が回転して全体の要素自体がシフトしてしまうため、出力位置を固定されたインデックスで表現することができないためです。要素をシフト量で表しておくことで、数列全体がシフトしても出力位置を正しく特定することができます。

ローターを回転させるためには、数列の全要素をシフトすればいいわけですが、実際にシフト処理を行うと重くなるので、数列の先頭位置を変化させることで仮想的にシフトさせる形にします。そのためのパラメータがlocationになります。locationの初期値は0ですが、メンバ関数のinitを使うことで任意の位置に変更することができます。例えば、locationが2に初期化された場合、数列の3番めの要素が先頭になります。入力信号にlocation分だけ加算した値の位置にある数列の要素をシフト量として、前述したように、入力信号にinShift上の要素を加算することで暗号化を、入力信号からoutShift上の要素を減算することで復号化を、それぞれ行うことができます。実際の処理はencodeとdecodeで行っています。

ローターの回転はメンバ関数のrotateで行っています。単純にlocationの値に1を加算して、一周したら0に戻しているだけですが、一周した時は戻り値としてtrueを返すようにして、複数のローターを組み合わせた場合に備えてあります。

2-2) リフレクタ

リフレクタは、ローターと同じような内部配線を持った円盤形の部品ですが、ローターのように回転することはなく、信号が入力されたのと同じ側から出力される点がローターと異なっています。信号をスクランブルしつつ反射させることからリフレクタ(反射器)という名称が付けられています。
下図は、ローターにリフレクタを組み込んだ時の模式図を示しています。例えば、Aから入力された信号はリフレクタで反射された後再びローターを通り、Fを出力することになります。

リフレクタは、暗号を複雑にすることに貢献しているわけではありませんが、この部品のおかげで、復号化処理を簡単に行うことができるようになっています。上図を見れば明らかなように、暗号化されたアルファベットを入力すると必ず平文アルファベットが出力されるようになっています。これは、暗号化したときと復号化したときとで、ローターの配線内容・並び方・位置が同じである限り保証されます。つまり、暗号化と復号化で同じ条件にローターがセットされていれば、暗号化された文字をそのまま入力すれば正しい平文が得られることになります。

以下にリフレクタ部のサンプル・プログラムを示します。

/* vector内の要素をスクランブルする vector<unsigned int>& vec : スクランブルするvector unsigned int length : vectorの処理後の要素数 unsigned int count : スクランブル回数 */ void scramble( vector<unsigned int>& vec, unsigned int length, unsigned int count ) { vector<unsigned int> numSeq; vec.clear(); for ( unsigned int i = 0 ; i < length ; i++ ) { numSeq.push_back( i ); vec.push_back( i ); } for ( unsigned int i = 0 ; i < count ; i++ ) { if ( numSeq.size() < 2 ) break; unsigned int i1, i2; do { i1 = (unsigned int)( (double)rand() * numSeq.size() / ( (double)RAND_MAX + 1 ) ); i2 = (unsigned int)( (double)rand() * numSeq.size() / ( (double)RAND_MAX + 1 ) ); } while ( i1 == i2 ); vec[numSeq[i1]] = numSeq[i2]; vec[numSeq[i2]] = numSeq[i1]; numSeq.erase( numSeq.begin() + ( ( i1 > i2 ) ? i1 : i2 ) ); numSeq.erase( numSeq.begin() + ( ( i1 > i2 ) ? i2 : i1 ) ); } } /* エニグマ用リフレクタ */ class Reflector { vector<unsigned int> reflector; public: // コンストラクタ Reflector( unsigned int length ); unsigned int size() const { return( reflector.size() ); } unsigned int operator[]( unsigned int i ) const; }; /* Reflector コンストラクタ unsigned int length : リフレクタの文字数 */ Reflector::Reflector( unsigned int length ) { scramble( reflector, length, length / 2 ); } /* Reflector::operator[] 入力データに対する応答値を返す unsigned int i : 入力データ 戻り値 : 応答値(範囲外の場合は入力データをそのまま返す) */ unsigned int Reflector::operator[]( unsigned int i ) const { if ( i >= size() ) return( i ); return( reflector[i] ); }

ローター部に比べると、往復それぞれの入出力や回転を考慮する必要がないためシンプルな作りになっています。コンストラクタでは、ローター同様にサイズ分の数列を用意して、ヘルパ関数のscrambleで二つずつ要素を抽出しながらペアを作り、それぞれの要素を交換する処理を行っています。入力信号に対する反射時の位置は、添字演算子を多重定義することでobj[index]の形で取得することができます。

2-3) プラグボード

三つのローターを使って暗号化を行った場合、その初期設定は、前にも述べたように105,456通りの組み合わせがあります。この場合、一人の解読者が一つの組み合わせで解読を試みるのに要する時間が仮に一分だったとすると、全てを試すのに約73日かかります。エニグマが敵の手に渡った場合、10名の人員を投入して解読作業が行われれば、最長でも約一週間で解読ができてしまうことになります。そこで、さらに安全性を高める目的で、エニグマには、キーボードと一番目のローターとの間にプラグボードという部品が挿入されています。
プラグボードは、キーボードから入力された電気信号をローターに渡す前に、別の信号と交換する役割を持っています。例えば、AとCの信号を交換して、Aが入力された場合はCの信号が通る経路を、逆にCが入力された場合はAの信号が通る経路を伝わるようにすることができます。
下図に、プラグボードの働きを模式図で示します。

初期のエニグマ機は、六つのケーブルを使って六組のペアを選択することができました。26個のアルファベットから六組のペアを抽出する時の組み合わせは、26個のアルファベットから12個のアルファベットを抽出する組み合わせに、12個のアルファベットを六組のペアにするときの組み合わせを掛けることで求めることができます。

26個のアルファベットから12個のアルファベットを抽出する組み合わせは

₂₆C₁₂ = 26! / ( 12! X ( 26 - 12 )! ) = 9657700 通り

12個のアルファベットを6組のペアにする組み合わせは

3 X 5 X 7 X 9 X 11 = 10395 通り (*)

なので、実に100,391,791,500通りもの組み合わせがあります。

以下にプラグボード部のサンプル・プログラムを示します。

/* エニグマ用プラグボード */ class PlugBoard { vector<unsigned int> plug; public: /* PlugBoard コンストラクタ unsigned int length : 入力できる文字の数 unsigned int exchangeCount : 文字の交換が可能な数 */ PlugBoard( unsigned int length, unsigned int exchangeCount = 6 ) { scramble( plug, length, exchangeCount ); } // プラグを交換する bool exchange( unsigned int i1, unsigned int i2 ); unsigned int size() const { return( plug.size() ); } /* encode/decode 暗号化と復号化(処理は全く同じ) unsigned int i : 入力インデックス 戻り値 : 暗号値(範囲外の場合は入力インデックスをそのまま返す) */ unsigned int encode( unsigned int i ) const { return( ( i >= plug.size() ) ? i : plug[i] ); } unsigned int decode( unsigned int i ) const { return( encode( i ) ); } }; /* PlugBoard::exchange プラグを交換する unsigned int i1, i2 : 交換する要素 */ bool PlugBoard::exchange( unsigned int i1, unsigned int i2 ) { if ( i1 >= size() || i2 >= size() ) return( false ); // 既に交換されたプラグならば元に戻す if ( plug[i1] != i1 ) { plug[plug[i1]] = plug[i1]; plug[i1] = i1; } if ( plug[i2] != i2 ) { plug[plug[i2]] = plug[i2]; plug[i2] = i2; } if ( i1 == i2 ) return( true ); plug[i1] = i2; plug[i2] = i1; return( true ); }

コンストラクタの第二引数で、ランダムにプラグを交換する回数を指定することができます。また、後でプラグを交換するために、メンバ関数のexchangeが用意されています。
exchangeではプラグの交換ができますが、すでにプラグが交換済みだった場合は一度元に戻してから改めて交換処理を行うようにしてあります。これは、実機でプラグ交換をする場合の操作に合わせるためです。

上図の中で、L₁からL₄は、各入力文字がプラグボードで変換された時の未知の文字を示しています。一台目のエニグマでは、入力されたWがプラグボードでL₁に変換され、さらにローター三台とリフレクタによってL₂になってから、プラグボードで再び変換されてRを出力しています。この結果は、二台目のエニグマで同じくRとして入力されますが、ここで、一台目のエニグマと同様に、プラグボードによってL₂に変換されていることに注目してください。プラグボードの設定はどのエニグマも同じなので、上記のようなループ構成にすることによりプラグボードによる変換処理は互いに打ち消し合うことになります。つまり、ループ構成によって、プラグボードの設定は全て無視することができることを意味します。
残念ながら、プラグボードによって変換された未知の文字を知ることはできないため、以下のような操作によって解読を試みることになります。

1. プラグボードの設定をリセットしておく。

2. ローターの設定を全エニグマに対して同一とした上で、クリブのループ構造に合わせて各エニグマにあるローターの位置を調節する。

3. 一台目のエニグマの出力文字(L_aとする)を任意に決め、二台目のエニグマの入力文字L_aと接続する。

4. 入力文字L_aによって二台目のエニグマから出力される文字(L_bとする)をチェックして、三台目のエニグマの入力文字L_bと接続する。

5. 操作4を、最後のエニグマと接続するところまで繰り返す。

6. 最後のエニグマの出力文字(L_xとする)を、一台目のエニグマの入力文字L_xと接続する。このとき回路が閉じた状態になったら、それが求めているローターの設定になる。

7. 操作3から操作6までを、L_aの取りうる個数分繰り返す。

8. 操作2から操作7までを、ローターの設定の組み合わせ数分繰り返す。

しかし、L_a以外(L_bからL_xまで)はあらかじめ全て接続しておいても問題はないため、操作方法は次のように簡略化できます。

1. プラグボードの設定をリセットしておく。

2. n台目(n>1)のエニグマの全出力文字を、n+1台目のエニグマの入力文字と、同じ文字同士で接続する。また、最後のエニグマの全出力文字は、1台目のエニグマの入力文字と、同じ文字同士で接続する。

3. ローターの設定を全エニグマに対して同一とした上で、クリブのループ構造に合わせて各エニグマにあるローターの位置を調節する。

4. 一台目のエニグマの出力文字(L_aとする)を任意に決め、二台目のエニグマの入力文字L_aと接続する。このとき回路が閉じた状態になったら、それが求めているローターの設定になる。

5. 操作4を、L_aの取りうる個数分繰り返す。

6. 操作3から操作5までを、ローターの設定の組み合わせ数分繰り返す。

ローターの配線の組み合わせは17576通り。五つのローターから三つのローターを選択して並べる時の組み合わせは60通りになり、ローターの配置と位置をチェックする操作は

17576 X 60 = 1,054,560通り

となります。仮に、上記操作を自動化したとして、ひとつの組み合わせを一秒で処理することができた場合、全ての処理を完了するのに約12日必要となります。また、ローターの配置の組み合わせ数分だけ回路を用意することができれば、操作すべき回数はさらに減少して、五時間以内に処理することもできるようになります。
ローターの設定が判明すれば、あとはプラグボードの設定を見つけ出すだけですが、これは前にも述べた通り、プラグボードの設定を初期化した上で暗号文を平文化して、交換されたアルファベットを意味のわかる単語から類推することで実現できます。

ローターの設定を解読するためにチューリングが考案した装置はレイェフスキの製作したそれに類似しているためやはりボンブと呼ばれ、1940年3月14日に試作品第一号(VICTORY)がブレッチレーに到着しました。ところが、試運転の結果は予想をはるかに下回ったため、性能改善のための改造が必要となります。そうしている間にドイツ軍はとうとう、メッセージ鍵の反復送信をしないよう送信プロトコルを変更し、新しいボンブが到着するまでの間は解読できる暗号の数が激減、プロトコル変更が行われた1940年5月10日から、新たなボンブ(AGNES DEI ; 神の子羊)が到着した1940年8月8日までの約三ヶ月間、チューリングをはじめとするブレッチレー・パークのメンバは居ても立ってもいられない状況だったのではないでしょうか。しかし、新しいボンブは期待どおりの性能を示し、エニグマ解読における重要な役割を果たすことになります。

以下は、ボンブによる解読のシミュレーションを行ったサンプル・プログラムになります。

まずは、クリブからループ構成を得るためのプログラム部分を紹介します。

// Crib クリブの構成要素 struct Crib { unsigned int rotorLoc; // 初期状態を'0'としたときのローターの相対位置(クリブ上の文字の位置と同じ) unsigned char crypto; // 暗号化した結果の文字列 // コンストラクタ Crib( unsigned int _rotorLoc = 0, unsigned char _crypto = ' ' ) : rotorLoc( _rotorLoc ), crypto( _crypto ) {} // '=='の多重定義 bool operator==( const Crib& crib ) const { return( crypto == crib.crypto ); } }; typedef vector<unsigned int> VecUInt; typedef map<unsigned char, Crib> MapCrib; /* makeLoop クリブの構成要素からループを作成する const MapCrib& mapCrib : クリブの構成要素を持ったMap unsigned int startIdx : ループ読み込みの開始位置 戻り値 : 作成したループの要素(Vector) */ VecUInt makeLoop( const MapCrib& mapCrib, unsigned int startIdx ) { vector<Crib> vecCrib; VecUInt vecInt; // ループ読み込みの開始位置がクリブの範囲外なら空のベクタを返す if ( startIdx >= mapCrib.size() ) return( vecInt ); MapCrib::const_iterator mapIt = mapCrib.begin(); // クリブ上の対象要素 for ( unsigned int i = 0 ; i < startIdx ; i++ ) ++mapIt; int loopStart; do { // 対象要素がすでにベクタ上にあれば、ループが構成されたことになる vector<Crib>::iterator vecIt = find( vecCrib.begin(), vecCrib.end(), mapIt->second ); loopStart = ( vecIt == vecCrib.end() ) ? -1 : vecIt - vecCrib.begin(); vecCrib.push_back( mapIt->second ); // 対象要素の暗号化結果から次の対象要素を探す mapIt = mapCrib.find( ( mapIt->second ).crypto ); // 対象要素が見つからなければループ構成できない if ( mapIt == mapCrib.end() ) return( vecInt ); } while ( loopStart < 0 ); // ループの先頭より前の部分を削除 vecCrib.erase( vecCrib.begin(), vecCrib.begin() + loopStart + 1 ); for ( unsigned int i = 0 ; i < vecCrib.size() ; i++ ) vecInt.push_back( vecCrib[i].rotorLoc ); return( vecInt ); } /* hasSameLoop 同じループが登録されているかチェックする const vector<VecUInt>& vecVecInt : ループを登録したベクタ const VecUInt& vecInt : 対象のループ 戻り値 : true ... あった ; false ... なかった */ bool hasSameLoop( const vector<VecUInt>& vecVecInt, const VecUInt& vecInt ) { for ( unsigned int i = 0 ; i < vecVecInt.size() ; i++ ) if ( findFromVector( vecVecInt[i], vecInt[0] ) >= 0 ) return( true ); return( false ); } /* makeAllLoop メッセージとその暗号から、構成可能なループを全て作成する const string& plain : 平文メッセージ const string& crypto : 暗号化メッセージ unsigned int minSize : ループとして採用する最小要素数 bool debugFlag : デバッグ用 戻り値 : 作成したループを持つベクタ */ vector<VecUInt> makeAllLoop( const string& plain, const string& crypto, unsigned int minSize, bool debugFlag ) { vector<VecUInt> vecVecInt; MapCrib mapCrib; // ループ構成要素をメッセージから抽出してMapを作成する for ( unsigned int i = 0 ; i < plain.length() && i < crypto.length() ; i++ ) { if ( mapCrib.find( plain[i] ) == mapCrib.end() && plain.find( crypto[i] ) != string::npos ) { Crib c( i, crypto[i] ); mapCrib[plain[i]] = c; } } if ( debugFlag ) { cout << "Crib : "; for ( MapCrib::iterator it = mapCrib.begin() ; it != mapCrib.end() ; it++ ) cout << it->first << "-" << ( it->second ).crypto << " "; cout << endl; } // ループ開始位置を変えながらループ作成 for ( unsigned int i = 0 ; i < mapCrib.size() ; i++ ) { VecUInt vecInt = makeLoop( mapCrib, i ); if ( vecInt.size() >= minSize ) if ( ! hasSameLoop( vecVecInt, vecInt ) ) // 同じループ構成がすでにないかチェック vecVecInt.push_back( vecInt ); } return( vecVecInt ); }

makeAllLoopは、与えられたクリブから得られる全てのループを返します。最初に、クリブの中からループ構成可能な部分だけを抽出します。ループ構成可能となる条件として、必ず暗号化された文字が平文文字列に含まれていることを満たす必要があるため、そうでない部分は除外します。また、平文文字列の中で同じ文字が存在した場合、最初に登録された文字だけを登録しています(この部分については改良の余地はあります)。次に、ループチェックの開始位置を先頭より一つずつ順にずらしながら、makeLoopを使ってループを構成し、hasSameLoopで、すでに登録されたループの中に一致するものがないかをチェックします。
makeLoopはループ作成のメインルーチンになります。暗号化された文字が平文文字列のどの位置にあるかを開始位置から順にチェックしながら繋いでいきます。ここで、追加した要素と同じものがすでにループ内に存在していれば、ループが閉じたことになります。しかし、暗号化文字が平文文字列に含まれているものだけが登録されていても、必ずループが閉じるとは限りません。平文文字列の中から除外された文字が暗号化文字となっている場合は、その個所でループが切れてしまします。サンプル・プログラムではこの場合に空のベクタを返すようにしています。ループが閉じた場合は、ループが繋がった個所より前の要素を削除すれば、完全なループが形成されます。

以下に、処理の例を示します。

クリブの内容

ローター位置	0	1	2	3	4	5	6	7	8	9
平文文字列	A	B	C	D	E	F	G	H	I	J
暗号化文字列	H	C	F	G	X	J	C	B	L	D

ループ構成可能な要素

ローター位置	0	1	2	3	5	6	7	9
平文文字列	A	B	C	D	F	G	H	J
暗号文字列	H	C	F	G	J	C	B	D

Aからスタートして順に連結。

A→H→B→C→F→J→D→G→C

Cがすでにループ内に存在しているため、ここでループが閉じます。Cより前にある要素を全て削除してループが完成します。

C→F→J→D→G→C

ここで、Jからスタートして順に連結してみます。

J→D→G→C→F→J

今度もループは形成されましたが、その内容は開始位置が異なる以外、前のループ構成と全く同じです。このようにループが重なった場合、重複して登録しないようにする必要があります。重複しているかどうかの判定は、構成したループの中の一つの要素(例えば先頭の要素)が、別のループの要素として存在しているかチェックすることで行うことができます。平文文字→暗号化文字のルートは一意なため、重なった要素がひとつでも存在すれば、そこから続くルートも同じ内容になります。つまり、ループ自体も同一となってしまうわけです。

次は、ボンブによる解読のシミュレーションを行ったサンプル・プログラムです。

// Bombクラス class Bomb { vector<Enigma*> vecEnigma; // エニグマによるループ構造 VecUInt cribLoc; // クリブ上での、ローターの相対位置 bool debugFlag; // デバッグ用 public: /* Bomb コンストラクタ const Enigma& enigma : 解読する対象のエニグマ vector<unsigned int> _cribLoc : クリブ上での、ローターの相対位置 */ Bomb( const Enigma& enigma, VecUInt _cribLoc, bool _debugFlag = false ); // ローター位置の解読を実行する // ローター位置の全パターンで解読 vector<string> decode(); // 一つのローター位置で解読 bool decode( const string& rotorLoc ); // ローター位置のリストにある要素で解読(不一致のものはベクタから削除) void decode( vector<string>& vecStr ); }; /* Bomb コンストラクタ const Enigma& enigma : 解読する対象のエニグマ VecUInt _cribLoc : クリブ上での、ローターの相対位置 */ Bomb::Bomb( const Enigma& enigma, VecUInt _cribLoc, bool _debugFlag ) { cribLoc = _cribLoc; debugFlag = _debugFlag; for ( unsigned int i = 0 ; i < cribLoc.size() ; i++ ) { vecEnigma.push_back( new Enigma( enigma ) ); vecEnigma[i]->resetPlug(); // プラグボードはリセットしておく } } /* Bomb::decode 全てのローター位置の組み合わせに対して ループが閉じるかをチェックする 戻り値 : ループが閉じた組み合わせを持ったベクタ */ vector<string> Bomb::decode() { vector<string> vecStr; if ( vecEnigma.size() < 2 ) return( vecStr ); // ローター位置は全て0にリセット vecEnigma[0]->init(); string rotorLoc = vecEnigma[0]->current(); while ( 1 ) { // ループのチェック if ( decode( rotorLoc ) ) vecStr.push_back( rotorLoc ); // ローター位置をひとつ進める vecEnigma[0]->init( rotorLoc ); if ( vecEnigma[0]->rotate() ) break; rotorLoc = vecEnigma[0]->current(); } return( vecStr ); } /* Bomb::decode ローター位置のベクタにある要素でループが閉じるかをチェックする (不一致のものはベクタから削除) vector<string>& vecStr : ローター位置のベクタ */ void Bomb::decode( vector<string>& vecStr ) { if ( vecEnigma.size() < 2 ) return; for ( unsigned int i = vecStr.size() ; i > 0 ; i-- ) { if ( ! decode( vecStr[i - 1] ) ) vecStr.erase( vecStr.begin() + i - 1 ); } } /* Bomb::decode 指定したローター位置でループが閉じるかをチェックする const string& rotorLoc : ローター位置 */ bool Bomb::decode( const string& rotorLoc ) { if ( vecEnigma.size() < 2 ) return( false ); // ループ上の各エニグマのローター位置を初期化 for ( unsigned int i = 0 ; i < vecEnigma.size() ; i++ ) { vecEnigma[i]->init( rotorLoc ); for ( unsigned int j = 0 ; j < cribLoc[i] ; j++ ) vecEnigma[i]->rotate(); } // 入力可能な文字全てに対して繰り返す for ( unsigned int i = 0 ; i < vecEnigma[0]->ioSize() ; i++ ) { vector<string> message; char c = vecEnigma[1]->keyOut( i ); string s( 1, c ); // ループ上で順次暗号化 for ( unsigned int j = 1 ; j <= vecEnigma.size() ; j++ ) { message.push_back( s ); s = vecEnigma[j % vecEnigma.size()]->convert( s ); } if ( s[0] == c ) { // ループが閉じたか？ if ( debugFlag ) { cout << "Rotor Location=" << rotorLoc << " : "; for ( unsigned int j = 0 ; j < message.size() ; j++ ) cout << message[j] << "->"; cout << s << endl; } return( true ); } // ローターを反転して元の位置に戻す for ( unsigned int j = 0 ; j < vecEnigma.size() ; j++ ) { vecEnigma[j]->negRotate(); } } return( false ); }

ボンブの作成には当然、エニグマのオブジェクトを利用しています。解析したいエニグマとクリブから作成したループ構成を引数として、ボンブを構築します。コンストラクタでは単純に、ループの要素数だけエニグマを並べているだけです。ローターの位置の設定などは全て解読時に行います。また、プラグボードは、意味をなさないためリセットしてあります。これは、各エニグマの入出力結果を見たい場合、その内容が見やすくなるようにするための処置です。

解読のためのメンバ関数であるdecodeは全部で三種類あります。引数を持たないdecodeは、ローター位置の全組み合わせに対して処理を行うためのもので、ループが閉じた組み合わせのベクタを返します。この返り値を引数として、二番目のdecodeを使ってさらに候補を絞りこみます。利用方法としては、最初のループを、引数を持たないdecodeを使って、全てのローター位置の組み合わせに対して解読し、次のループからは、候補となるローター位置の組み合わせのベクタを渡してさらに絞りこむような形になります。
実際の解読処理は最後のdecodeが行っています。指定したローター位置に従って各エニグマのローター位置をセットした後、入力文字を変えながら各エニグマで処理を行い、最後に出力された結果が入力した文字と一致するかを確認してループが閉じたかをチェックします。

今回作成したサンプルを使い、簡単なテスト・プログラムで動作試験をして見ましたが、絞りこんだ結果はたいてい、アルファベットの数だけになりました。例えば、ローターの位置にPSWを指定すると、候補はASWからZSWまで、つまり先頭だけが、取りうる全ての文字を持つことになり、候補を一つだけに絞りこむことはできませんでした。いろいろと原因を考えてみましたが、今のところは判明していません。

今回のサンプル・プログラムのソースをアップロードしておきます。御自由にお使い下さい。

zip形式(Enigma.zip)

tar-gzip形式(Enigma.tar.gz)

動作確認はVine Linux 4.1上で行いました。特殊なライブラリは使用していないため、どんな環境でもビルド・動作は可能だと思います。

1. 「暗号解読」 サイモン・シン著 (新潮社)
2. Wikipedia

前に戻る

タイトルに戻る