発端
ホフスタッターの「ゲーデル・エッシャー・バッハ」にチューリングのことが記載されていました。イギリスを救ったヒーローであるにも関わらず不遇な生涯を送った天才でした。戦時下、秘密裡に行われたエニグマ暗号解読について資料を読みつつ自分でも実装、検討することを試みました。
エニグマの実装
エニグマは第二次世界大戦中にドイツが利用した暗号装置です。平文を暗号化しモールス信号をもってユーボートなど最前線との連絡に使われていました。その仕組みについてはwikipediaをご覧ください。エニグマ装置の概略は３つのローターとプラグボードです。ローターが1文字入力されることに回転する仕組みになっています。このことが解読を困難にしていました。ローターはアルファベット26文字からなっており3枚のローターの初期設定は26^3＝17,576通りあります。さらにローターの順番の入替、プラグボートでの差し替えによりその組み合わせは京単位となっており、当時最強の暗号と言われていました。
実行例
Easy-ISLisp Ver2.65
> (load "tests/enigma.lsp")
T
> (enigma "hello")
"sirhd"
> (enigma "sirhd")
"hello"
>
平分を文字列として与えると暗号文に変換されます。暗号文は同じ方法で復号化できます。
ローターの初期設定は０－２５の数値を３つ与えることで行います。
> (set-init 2 5 7)
7
> (enigma "hello")
"wlsbp"
> (enigma "wlsbp")
"hello"
>
このようにローターの初期設定を変更すると変換される暗号文は変化します。
メイン関数
Easy-ISLispに付属のパイプマクロを使って見通しをよくしています。
;; Enigma main function
(defun enigma (str)
(count-init)
(pipe str |> (convert <list>) |> (enigma1) |> (charlist->string)))
;; use pipe macros to show transform process easier
(defun enigma1 (ls)
(cond ((null ls) nil)
(t (let ((l (pipe (car ls)
|> (connecta (elt counter 2)) |> (ica)
|> (connecta (elt counter 1)) |> (iica)
|> (connecta (elt counter 0)) |> (iiica)
|> (reflect)
|> (iiicb) |> (connectb (elt counter 0))
|> (iicb) |> (connectb (elt counter 1))
|> (icb) |> (connectb (elt counter 2)))))
(count-up counter) ;rotate
(cons l (enigma1 (cdr ls)))))))
ica iica iiicaは順方向でのローターにおける変換を表しています。icb iicb iiicbは逆方向での変換です。reflectはプラグボーデでの変換です。パイプを使うことによりその変換過程を見やすくしています。
ローター、リフレクター
連想リストによっています。
;rotor1
;ABCDEFGHIJKLMNOPQRSTUVWXYZ
;DMTWSILRUYQNKFEJCAZBPGXOHV
(defconstant rotor1
'((#\a #\d) (#\b #\m) (#\c #\t) (#\d #\w) (#\e #\s) (#\f #\i)
(#\g #\l) (#\h #\r) (#\i #\u) (#\j #\y) (#\k #\q) (#\l #\n)
(#\m #\k) (#\n #\f) (#\o #\e) (#\p #\j) (#\q #\c) (#\r #\a)
(#\s #\z) (#\t #\b) (#\u #\p) (#\v #\g) (#\w #\x) (#\x #\o)
(#\y #\h) (#\z #\v)))
(defun ica (x)
(finda x rotor1))
(defun icb (x)
(findb x rotor1))
文字列をキャラクタを要素とするリストに変換し、そのキャラクタごとに連想リストで変換をしています。findaはassocを利用し、findbは第二要素をキーとして検索するreverse-assocを用意して計算しています。
回転をどうするか？
実際のエニグママシンではローターが回転をするのですが、Lispコードでこれを素朴にやると非効率です。与える文字をずらすことにより同様の効果を得ています。
;; e.g. connecta(#\a 3) = #\d
(defun connecta (x shift)
(let ((base (convert #\a <integer>)))
(convert (+ (mod (+ (- (convert x <integer>) base) shift) 26) base)
<character>)))
;; e.g. connectb(#\a 3) = #\x
(defun connectb (x shift)
(let ((base (convert #\a <integer>)))
(convert (+ (mod (- (- (convert x <integer>) base) shift) 26) base)
<character>)))
順方向ではz方向へシフトし逆方向ではa方向へシフトします。
チューリングボンベの実装
映画「イミテーション・ゲーム」が感動的な場面を表現していました。たくさんのローターがついたマシンが作成されローターをモーターで動かすことで解読作業をさせていました。映画中ではチューリングはこのマシンにクリストファーという名前を付けていますね。
エニグマのシミュレータみたいなものです。3つのローターが回転することにより解読しています。36の並列処理だったそうです。26^3＝17,576通りを計算するのに6時間かかったそうです。1つの場合を処理するのに1.2秒程度だったそうです。さて、これをLispで計算することを考えます。現代のコンピューターは高速です。逐次処理でも大丈夫じゃないのか？ やってみました。
(defun tb (str1 str2)
(block exit
(set-init 0 0 0)
(while t
(if (string= (enigma str1) str2)
(return-from exit t))
(count-up initial)))
(gbc); for compile code
initial
)
上記で実装したエニグマをひたすらwhileで回しています。3要素のベクトル #(0 0 0) をカウントアップして#(25 25 25)までひたすら調べます。さてどのくらい時間がかかるのかな？
Easy-ISLisp Ver2.65
> (load "tests/enigma.o")
T
> (tb "hello" "oikrw")
#(25 25 25)
> (time (tb "hello" "oikrw"))
Elapsed Time(second)=1.013919
<undef>
>
さすが、現代のコンピューターは高速です。1秒程度で計算を終えました。しかし、この計算例では３つのローターの初期設定の解析だけです。さらにプラグボードやローターの順番の入替が入ると場合の数は急増します。ドイツ海軍はローターを４，５と増加、強化を図りました。チューリングは場合の数を減らすべく工夫をしたようです。映画ではこのあたりは描かれていませんね。このあたりの数学的な工夫を考えてみるのは楽しそうです。映画はエンターテーメントのために作られてるので仕方がありませんが、あれはポーランド人が見たら怒るよね。(笑）
ポーランド人数学者の業績
その後、あれこれと調べていますと、ポーランド人たちが暗号解読にかなり貢献していたことがわかりました。ポーランド製のbombaも実際に作られて3ローターのものは解読に成功していたそうです。その装置はドイツのポーランド侵攻の際に、情報が漏れないために破壊されたのだっそうです。理論的には数学者のレイｪフスキさんという人が群論を応用して理論構築、暗号機も作っていたみたいです。
群論の応用については下記の動画がとても参考になりました。
https://www.youtube.com/watch?v=GG1zIELCb6k&t=1060s
ソースコード
Easy-ISLispのテストフォルダに収録しています。Easy-ISlispはOSSです。