エニグマを実装してみた
某イベントの某謎解きに参加しました。
このイベントにある謎解きは事前に以下のように考え、エニグマの勉強はちょっとチラ見程度でした。
- エニグマだと仮定して、事前に解くのは困難だったはず。
- 例えば自動で解くツールにしても、どんなパターンでも正しいデータが返ってくるタイプの暗号なので、Base64等のように明らな間違いがわからず結局全部答えを見る必要がある。
- 某法則性で枝払いはできるようだが結局のところ英文として成立するかどうかのチェックが必要で事前に解くのはほぼ不可能だった記憶がある。
- 調べていないが、スペースなしの英文を英単語で区切って文章にするツールがあるなら片っ端からそれに突っ込むという手がある。
- 答えを見る限り使われてそうな単語はほぼ予測不可能だったので、やはり事前に解くのは無理そう。
- Webの変換ツールが見当たらないので、使いやすく作れば当日有利では?とまでは考えていた。
- アルゴリズム系の暗号というより装置としての暗号だったので、Simulatorがつくのが一般的らしい?
- Simulator系は結構たくさんあるし日本人が実装したコードとかもみつかるので、変換ツールがないわけではない。
- ただしちゃんと動くものを作るにはわからないことが多すぎる(後述)
- アルゴリズム系の暗号というより装置としての暗号だったので、Simulatorがつくのが一般的らしい?
こんな感じで考えて別の準備をした結果完敗しました。本当にちょっとだけでもいいからエニグマやっとけばよかった。というか紙に印刷するタイプのエニグマがあるのでこれで予習しておけばよかった!!!
こちら、あまりにも悔しかったのでエニグマを作ろうと思います。リベンジです。
実装の障害
さて、参加記事には書かれていないエニグマ実装についてですが、実は前々からエニグマを実装してみたいなとは思っていました。
ただ今までやってこなかった理由がいくつかあります。
- バリエーションが多く、それの差異について知らない程度の知識では実装しきれない可能性がある。
- 当日使うこと前提なら役に立たない可能性が高い。
- 後から知ったがRingの設定については全く把握していなかったので、おそらくここらへんを漏らした実装になっていたはず。
- 当日使うこと前提なら役に立たない可能性が高い。
- 答え合わせができないと何が間違っているかわからない。
- (上にあるシミュレーターという観点がなかったため)軽く検索して出て来ないので挙動確認などができず厳しい。
- せめて答え合わせのためのサンプルデータが欲しい。
ですがシミュレーターの存在を知ったことやサンプルのデータが手に入ったなど、手を出すための障害はおおよそ排除されました。
そんなわけで、今回は逃げない!!という気持ちを新たに実装してみようと思います。
実装言語はTypeScriptです。
サンプル
今回のエニグマ処理用のライブラリを使ったブラウザ実装です。使いやすさというよりはローター等の中身がわかるような作りになっています。
ちなみに設定や差異が多すぎるので、とりあえずサンプルではEnigmaIで使われてると思われる設定を入れてあります。(おそらく設定や値の準備さえすれば他のバージョンもいけるようにライブラリを作ったはずなので、そのうちちゃんと他の設定で動くものを作るかもしれない。)
注意事項としてエニグマは本来入力ボタンを押した後一番右のローターを回転させてから処理を行いますが、今回はマウスを載せた場合に出力がどうなるかのシミュレーターを兼ねるため、入力前に一度ローターを回転させています。(左下にカウンターがありますが、初期値1となっているので一度回転済みなのが分かります。)
実際の挙動とは多少異なるので気をつけてください。
用語集
- ETW
- Entry wheels
- ローターに入力するアルファベットも円形に並んでたらしいのでwheelsと呼ばれているらしい。
- とりあえず入力列で基本は ABCD…… と並んでいる理解で良さそう。
- 逆にそうじゃない設定がモデルによってあるっぽい。
- Rotor
- 文字を変換するテーブルを回転できる状態にしたもの。
- 複数のローターを繋いだり回転させることで複雑になっている。
- 初期位置を設定できるが、入力前に必ず一度一番右のローターが回転する。
- 初期値を左からAAAにしていても、初めて入力する直前に右のローターが回転してAABになった後変換処理が行われる。
- 実機の場合は必ず回転してしまうが、プログラムの場合は回転と入力を分離できるので状態保持もしやすい。
- ローターごとに隣を回すポイントがあり、そのポイントに到達すると左のローターを一つ回す。
- ローターが左から1,2,3と並んでいる場合、入力前に一度3のローターを回転させる。
- その時3のローターが特定のポイントに到達すると隣の2のローターを回転させる。
- ローターによってポイントが異なり、一周ごとに回転させていたようだが、後期モデルで追加されたローターはポイントが2箇所(半周で1回)回転させていたっぽい?
- Turnover
- 隣のローターを回転させるための印。
- ローター回転時に判定を行う。
- 現在のローターの出力値を見て、Turnoverの文字だった場合にはフラグを立てる。
- ローター回転後フラグを返す。
- ローター回転後のフラグが立っている場合は隣のローターを1回転させる。
- もしそのローターもフラグが立っていた場合は隣のローターを回転させる。
- 後期バージョンでは複数存在するようなので、プログラムも複数に対応しておくべき。
- Ring settings
- Ringstellung
- ローターのリング設定。
- Aを指定すると変化なし。
- A(01)を指定した時、
入力A→ローターI(EKMFLGDQVZNTOWYHXUSPAIBRCJ)→出力E
のところB(02)を指定すると入力A→ローターI(FLNGMHERWAOUPXZIYVTQBJCSDK)→出力K
になるよう回路を回転させる。- 入力もローターもアルファベットをN個ずらす。
- 上のパターンだと入力のZが1つずらしてAになり、ローターのJがKになる。
- ローターのアルファベットの書かれたリングなどは固定されているため変更不可→内部回転のような機能をつけているらしい。
- Reflector
- ローターは左から1,2,3と並んでいる場合、
出力←3←2←1←リフレクター←1←2←3←入力
という流れで変換するらしい。- 右から入った入力が左のリフレクターで折り返し、右から出力として出てくる。
- このようにローターに戻すリフレクターがあり、これもひっくり返すターゲットが異なるらしい。
- ローターは予め回転させてから変換するがリフレクターは回転みたいなものはない。
- プログラム的には結局入力座標を別の出力座標に変換するだけなのでローターと共通処理をある程度持てるかも。
- ローターは左から1,2,3と並んでいる場合、
- UKW
- Umkehrwalze
- reflector
- リフレクターのこと。
- Cタイプのリフレクターは
UKW-C
のように記述されるっぽい。
- Plugboard
- プラグボード。
- 単純なアルファベットのペアを入れ替えるボード。
- ボードにペアとなるアルファベットを線でつなぐとその入出力がひっくり返る。
Converter
まず上にちらっと書いた通り、ローターだのリフレクターだのありますが、基本的には入力に対し一対一の変換表を使って出力を決めています。
そこでローターとリフレクターの共通処理としてテーブルを元にした変換クラスを用意します。
これに対して初期値として入力と出力の対応文字列を与えます。この時注意なのはエニグマを見た時まず入力は右から入ってくるということと左側は ABCDEF……
と規則正しく並んでいるのでここを間違えないようにします。(ここは初期値設定などとして表に出ている箇所になるようです。)
また内部的には配列のポジションを保持してそれを動かすのが良いのでしょうが、速度を重視しているわけでもなくローターを回転させてるっぽい挙動もするので、以下のようにテーブルの先頭から要素を一つ取り出し、それを末尾に追加するという操作を行います。
// ローターの回転
table.push(table.shift());
このような実装のために内部的に対応表を作ることにします。
これのメリットは現在の状態をステータスとして取得しやすく、デバッグに非常に有利というものがあります。
デメリットとしてはリセットしたい場合などに非常に面倒になるということがあります。(ポジションで管理しているならその数値を初期値に戻せばいいだけ。)
しかし、ローターは後述するリング設定にて対応表の変換があり、結局このオフセットまで考えると表を直接書き換えたり並び替えた方が動きとセットでシンプルになりそうということでこのやり方にします。C言語等のように文字をもっと数値で扱いやすい言語ならポジションでもいいかなと思います。
また変換に関しては最初文字を与えられて文字を返すという作りではあるのですが、エニグマのローターは以下のようにして複数接続しています。
Cを入力
C
|
ABCD 入力列
0123 アルファベット順に並べた時のポジションはC=2となる。C(2)と表記する
|
+---|----- ローター1
| 0123
| CABD
| |
| -- ローター内のBとBがつながっているのでポジションが B(2)→B(1)に変更されている
| | ローター内の変換は {2→B→1} と表記する
| ABCD
| 0123
+--|------ 最終的に 2→1 の変換を行った
|
| 隣のローターのポジション1とつながっている
|
+--|------ ローター2
| 0123
| CADB ローター2のポジション1はAなので、C(2) → {2→B→1} → A(1)という変換になる
| |
| --- ローター内のAとAがつながっているのでポジションが A(1)→A(3)に変更されている
| | ローター内の変換は {1→A→3} と表記する
| BCDA
| 0123
+----|---- 最終的に 1→3 の変換を行った
|
0123 アルファベット順に並べた時、ポジション3=Dとなる。D(3)と表記する
ABCD 出力列
|
D
Cの入力に対し
C(2) → {2→B→1} → {1→A→3} → D(3)
となり、Dを出力
ローター内部は同じ文字同士が繋がりポジション(現在地を基準に何番目につながっているか)が変化し、ローター同士は同じポジションでつながっています。
そのため変換に関しては基本的にポジション入力されたら出力としてポジションを返すような作りになります。
対応表
基本的に入力と出力の文字列を配列にしてセットにした配列をテーブルにしますが、厄介な対応があります。それがリング設定です。
リング設定は初期値A(01)でこの状態ならば対応は以下のように単純です。
EKMFLGDQVZNTOWYHXUSPAIBRCJ RotorI
||||||||||||||||||||||||||
ABCDEFGHIJKLMNOPQRSTUVWXYZ ETW
これにB(02)を渡すと一つ内部的にシフトして以下のようになるそうです。
FLNGMHERWAOUPXZIYVTQBJCSDK RotorI
||||||||||||||||||||||||||
BCDEFGHIJKLMNOPQRSTUVWXYZA ETW
ぱっと見何をしているか不明なので順番に変換します。
- オフセットはAの場合0、Bの場合は1、……Zは25という具合にアルファベットの番号とします。
- 入力側はアルファベットをオフセット分だけ次のアルファベットに変更します。
- 例えばリング設定
B(02)
はオフセット1で、F
を1ずらす場合は次のアルファベットであるG
にします。 - オフセットと表記で1ズレがありますが、0始まりか1始まりかの違いなので他の資料にある表記を引き継ぎます。
- 例えばリング設定
- 出力側も同じようにオフセット分だけ次のアルファベットに変更します。
- 例えば
A
を1ずらすと次のアルファベットのB
になり、Z
はA
になります。
- 例えば
実際に先程の例でやってみます。
EKMFLGDQVZNTOWYHXUSPAIBRCJ RotorI ... A(01)
↓アルファベットを1ずらす
FLNGMHERWAOUPXZIYVTQBJCSDK RotorI ... B(02)
||||||||||||||||||||||||||
BCDEFGHIJKLMNOPQRSTUVWXYZA ETW ... B(02)
↑アルファベットを1ずらす
ABCDEFGHIJKLMNOPQRSTUVWXYZ ETW ... A(01)
このように面倒なリング設定があるため、生の入出力用データとそれにオフセットを与えると変換表を作るメソッドを用意して、設定変更のたびに変換表を作り直せる構造にします。
コンバーターの実装
方針が固まったのでコンバーターは以下のように実装します。
- 初期設定を与えて変換表を作る。
- 入力ポジションを与えると、変換表に従って出力ポジションを返すメソッドを用意する。
Reflector
リフレクターはこの変換クラスを継承するだけで基本問題ないです。
ローターにある回転などもないので、単純にポジションの変更だけを行ってもらいます。
Rotor
ローターは変換クラスの他に必要な処理がいくつかあります。
- 文字を入力されたら入力ポジションを返すメソッド
- 一番はじめの入力周りで必要。
- ポジションを入力したらポジションや文字を返す変換メソッド
- 右から左(入力側から)と左から右(出力側へ)の2つ必要。
- ローターを回転させるメソッド
- 入力前にかならず必要。
- 一番右は毎回だがそれ以外はタイミングがあるので回転メソッドは別で用意する。
- 隣のローターも回転させるかどうかの判定を返す必要もある。
- ローターごとに決まっているのでそれも設定できるようにしておく必要あり。
- 入力前にかならず必要。
Plugboard
単純に2つのアルファベットを逆にします。
設置場所はローターの更に右、入力の直後と出力の直前です。
それ以外はスルーするので、プラグボードが AZ
の時に入力が A
の場合は Z
になってからローターに入力が入りますし、ローターから Z
が来た場合は A
に変換してから最終出力します。
ちなみに交換するだけなのでConverterを使い回すのもありですが、今回の場合設定が面倒くさいので独自に作った方が楽です。(今回は KGUSI...
というようなランダムっぽいアルファベット列と ABCDE...
という規則正しく並んだアルファベット列をセットで渡すことになる。)
実際の動作について
以下のように進めていきます。
初期設定
- プラグボード設定
- ローター設定
- 使用するローターの種類を選択する。
- オリジナルも作れるがとりあえずデフォルトのIなどを指定するとその変換表とターンオーバーの位置を設定する。
- リングの設定を行う。
- 使用するローターの種類を選択する。
- リフレクター設定
- 使用するリフレクターの種類を選択する。
- ローターと同じくオリジナルも作れるがデフォルトのBなどを指定するとその変換表を設定する。
- 使用するリフレクターの種類を選択する。
- 初期位置設定
- 各ローターの出力アルファベットが指定アルファベットになるまで回転させる。
- 右のローターを回しても左のローターが連動して回ることはなく、個別に設定する。
- 各ローターの出力アルファベットが指定アルファベットになるまで回転させる。
実際の処理
- 入力を受け取る
- 1文字ごとに処理を行う。
- ローターの回転
- エニグマの一番右のローターを回転させる。
- 今回は変換表の一番手前のデータを抜き、末尾に追加。
- この時ローターから左のローターも回転させるように指示が来た場合は、さらに左のローターを回す。
- エニグマの一番右のローターを回転させる。
- エニグマに1文字入力
- 入力をまずはプラグボードを介して変換する。
- ペアがある場合は変換され、そうでない場合はスルー。
- 現在の入力ポジションを得る。
- 右のローターに入力ポジションを入れ、次のポジションを得る。
- 左隣のローターにポジションを入れて次のポジションを得る作業を繰り返す。
- 一番左のローターにたどり着いたらリフレクターに同じようにポジションを入れ次のポジションを得る。
- その後は一番左のローターから右に向かって同じようにポジションを入れ、次のポジションを得る。
- 入力とは向きが逆になるので注意。
- 最後のローターから得たポジションを文字に変換する。
- ポジションを得るたびにその文字を結果に入れておくと楽。
- 再度プラグボードを介して変換。
- 最後に出力された文字が変換結果となる。
- 入力をまずはプラグボードを介して変換する。
- 最初に戻る。
実際に動かしてみる
実際に動く姿を見ると、エニグマでしんどいのは初期設定(特にリング設定)だけで、それ以外は難しくないかと思います。
というかエニグマはある時点の設定でアルファベットを交換するだけの機械です。同じ設定から始めれば同じ経路で逆の値を得ることができます。
このためエニグマには以下の特徴があると言われています。
- 反転性
- 交換=交換するアルファベットはセットになるため、入力と出力を逆にしても使用される経路は同じになる。
- とある設定で
A
がB
になるなら、同じ設定でB
はA
になる。
- 不完全性
- 絶対に自分と同じ文字に変換されることはない。
- これはリフレクターで別のポジションしてから反転してローターに戻しているため、信号が同じルートで戻ることがないのが影響している。
この特徴は右のボタンの上にカーソルを置いて動かしてみるとよく分かると思います。
A
の上にカーソルを置いて B
につながっているなら、B
の上にカーソルを置くと A
につながっています。
読む方向によって暗号化もしくは復号化になるので、例えば上のページの初期設定で HELLO
と入力すると WXECL
という出力が得られますが、リロード(同じ設定で初期化)後 WXECL
と入力すると HELLO
と出力されます。同じ経路を選びつつ逆向きに読んでいるだけなのが分かります。
参考
-
https://gigazine.net/news/20201123-paper-enigma/
- 紙で簡易的に体験できる
-
https://www.cryptomuseum.com/crypto/enigma/wiring.htm
- 大切な情報は大体ここに書いてある。
-
https://en.wikipedia.org/wiki/Enigma_rotor_details
- リングの設定についての記述とかあるけど全くわからなかった。
-
https://dencode.com/ja/cipher/enigma
- まさかの日本語でリング設定の具体例があった
Discussion