隠れたポーランドのヒーロー
ホフスタッターの「ゲーデル・エッシャー・バッハ」によりチューリングのエニグマ解読のことを知りました。ポーランドにおいても解読の試みがあったことは知ってはいたのですが、その詳細は知りませんでした。多くはチューリングの業績に負うのだろうと思い込んでいました。ところが、どうもポーランド人数学者による業績の方が大きいようです。ナチスドイツのポーランド軍事侵攻の際、ポーランドで開発された解読マシンは秘密保持のために破壊されたそうです。そのこともあってその業績はあまり知られていないようです。この人はレイエフスキさん（Marian Adam Rejewski）という人です。
暗号文からローター配線を推測
参照先の動画が詳しくレイエフスキさんの群論を応用したエニグマ解読について解説しています。時間の制約からあまり詳しい解説がなされていないのですが、これを手掛かりに私もその業績を追いかけてみることにしました。
https://www.youtube.com/watch?v=GG1zIELCb6k&t=1370s
ポーランドではドイツの軍事進攻にそなえてエニグマの解析を進めていました。商用エニグマは入手できたものの、軍事用エニグマは入手できません。膨大な暗号文から群論を応用してローター配線を推測したのだそうです。初期のドイツ軍は暗号文を送る手順として、予め決められていた日鍵をもとにローターの設定を2度打ちしてから本文を送信していました、3枚のローター設定をxyzxyzやabcabcのように2度打ちしたものを暗号化していました。このため1文字目と4文字目、2文字目と5文字目、3文字目と6文字目は同じ文字を暗号化したものでありそれらには一定の規則性があることを見出しました。
サイクル
エニグマは1文字ごとにローターが回転する仕組みになっています。あえて回転させないでa-zの文字をエニグマに与えて1文字目と4文字目を計算させます。そしてこれらを組にしてみます。手計算で確認したのち、Lispでその組を生成するものを書きました。
Easy-ISLisp Ver2.65
> (load "tests/enigma.lsp")
T
> (combination 0 0 0)
((#\b #\r) (#\a #\f) (#\x #\g) (#\u #\t) (#\i #\p) (#\j #\b) (#\w #\c) (#\s #\l) (#\e #\j) (#\f #\i) (#\o #\q) (#\m #\h) (#\l #\s) (#\t #\v) (#\k #\w) (#\v #\e) (#\y #\k) (#\z #\a) (#\h #\m) (#\n #\d) (#\d #\z) (#\p #\n) (#\g #\o) (#\c #\y) (#\q #\x) (#\r #\u))
>
ｂからｒ、ｒからuとサイクルになっているものを手繰ります。Lispでサイクルを抽出しました。
> (cycle (combination 0 0 0))
((#\m #\h) (#\s #\l) (#\w #\c #\y #\k) (#\x #\g #\o #\q) (#\a #\f #\i #\p #\n #\d #\z) (#\b #\r #\u #\t #\v #\e #\j))
>
レイエフスキーの定理によれはこのサイクルの数は必ず偶数になるのだそうです。そして、この結果を使うとローター配線のか調べなければならない可能性を数十程度までに減少させることができるのだそうです。このあたりになると群論の知識が必要になります。書棚から本を引っ張り出してきて勉強を開始したところです。
何歳になっても勉強は楽しい
戦争に使われた道具ということはさておき、こういった現実の問題に数学が応用されている場面を見ると勉強の意欲がそそられます。私は気が付いたら還暦を超えていました。しかし、まだまだ頭は冴えています。いろいろと勉強したいものです。
ソースコード
ここにおいてあります。test/enigma.lspです。OSSです。
https://github.com/sasagawa888/eisl