1918年11月の、崩れた ADFGVX メッセージ22通

01 リストとは何か

1918年にフランス軍に配属されていたアメリカの暗号解析者 James Rives Childs は、東部戦線で傍受されたドイツの ADFGVX 通信の写しを保管していた。2017年、George Lasry、Ingo Niebel、Nils Kopal、Arno Wacker は転置に対する山登り法による攻撃でこのコーパスを破り、1918年9月から12月までの14個の3日間有効の鍵のもとで618通の暗号文を復元した。その後 Lasry は、それらの鍵のどれでも復号できなかったメッセージのリストを Klaus Schmeh に渡し、Schmeh はそれを鍵を添えて「Unsolved ADFGVX messages from World War I」として公表し、後に自身の Top 50 の no. 46 とした。

そのページにある Lasry 自身の注記が問題の所在を述べている。鍵は「most certainly all the keys used during the period」であり、したがって「the challenge is to understand how the cryptograms were mutilated」というのである。ADFGVX は長さに容赦がない。列転置は文字の流れを鍵の長さで分割するので、1文字が失われたり加わったりすると、それ以降のすべての列の境界がずれ、メッセージの残りが雑音になる。2箇所が崩れたメッセージは、鍵がわかっていても、もはやその鍵では復号できない。

2017年2月から9月にかけて、投稿の下のコメントスレッドが作業の大半を担った。Norbert Biermann、Armin、Thomas、Max Baertl、そして Lasry 自身が次々とメッセージを復号した。Schmeh はまとめの記事を予告したが書かなかったので、それらの復号は散在するコメントとしてしか存在せず、結果の表は印刷物にもオンラインにも見つからなかった。このレポートがまず行うのは、その表の公表である。

02 機械可読にした鍵

Lasry のリストは各鍵を、転置の置換と36文字の換字方陣（A D F G V X の行順に並んだ升目）として示している。14個の方陣のうち3個には、復元されなかった升目を示すハイフンの連なりが含まれており、PDF のテキスト層ではその連なりが en ダッシュや em ダッシュに潰れて、34文字や35文字の方陣になっている。各ダッシュを36文字になる長さの連なりに戻すと、3個とも修復できる。14個すべては次にある： keys.json.

鍵の番号には二通りの解釈がありうる。 perm[i] が i 番目に出力される列なのか、それとも列 i が出力される位置なのか。どちらも往復で自己整合的なので、暗号化と復号の往復テストでは区別できない。実際のメッセージを復号すれば区別できる。後者である。

リストにない鍵

2017年5月3日、Lasry はスレッドで、2部からなるメッセージ、すなわち11月13日の FFVXV 暗号文とその続きの AFAFF 断片が、14の期間のどれにもない鍵で一緒に復号できたと報告した。転置語 CMBLAKOHIDENFJGP、長さ16である。彼は173文字の結合された平文を示し、自分のプログラムが長さ16の鍵を復元するのに356文字の暗号文すべてを必要としたと記した。換字方陣は公表されなかった。ここでは、Norbert の修正を適用したうえで、2つの暗号文の転置を戻した二文字組を彼の平文と対応付けて再構築した。36升目中24升目で、数字と文字 M、Q、Y は、メッセージで一度も使われないため復元されていない。これは次のファイルの15番目の項目である： keys.json リポジトリのノートでは、それが暗号化したメッセージの見出しにちなんで CHI 鍵と呼んでいる。

03 2017年の結果を一つの表に

スレッドの70件のコメントすべてに目を通した。ページ番号は Schmeh が印刷した Childs の写しのページである。2通のメッセージはリスト上でページ番号を持たない。文字数は受信された暗号文のもので、印刷された転写で示された欠落は別に数えている。各復号は最初に投稿した人の功績としている。

9通が復号され、3通が部分的に復号され、10通はどこにも復号が見当たらない。もう1ページ、印刷上の187ページ（SELLV…、「Stellv. Gen. Kom. 9 AK Breslau」）は、カッセルのチームがすでに解読していたメッセージであり、リストに属さない。Lasry がスレッドでそう述べている。2通の CHI メッセージは公表された鍵では復号できないとして掲載されていたが、それは事実である。それらは Lasry が公表されていない鍵を復元した後に復号された。

04 Norbert の手法の再実装

Norbert は自分の手法を一文で述べた。2つの異なる位置で最大5文字を追加または削除し、総当たりで探索し、n-gram の評価関数で結果を順位付けする、というものである。 blocks.py はまさにそれを行う。15個の鍵それぞれについて、また転写の5文字群の境界に挿入または削除する1〜5文字のブロック編集を最大2つ選ぶ各組み合わせについて、復号し、その結果を Gutenberg のドイツ語360万文字から作ったドイツ語の四文字組モデル（lm_de.py）で採点する。数字や未復元の升目を含む窓には最低点が課され、区切りの X をまたぐ窓には、ゴミよりは小さく本文よりは大きい減点が課される。このモデルでドイツ語の散文は1窓あたり約 −3.3 nats、ランダムな文字は約 −7 になる。

平文のヒントを与えなくても、探索は105、109、146、171ページ、176ページの「missing 10 letters」のメッセージ、そして2通の CHI メッセージを再導出する。146ページでは、Norbert が第10群の前に挿入した5文字ブロックが次のように出てくる： (45, 5)。176ページのメッセージでは、2つの5文字ブロックが次のように出てくる： (10, 5), (130, 5)。100ページは、2文字の挿入1つで同じ探索により解ける。探索は番号のない VGADA メッセージの11月22–24日の部分解読も見つける。印刷された転写が欠落を示している箇所では、 gaps.py がそれらを各群に戻し、残った1文字の欠落を焼きなまし法で処理する。132ページでは、指示なしに Norbert のテキストに行き着く。

再導出されたページのスコア（実行ログより）と、未解決のメッセージのいずれかが達成した最良のスコアとの比較：

解読済みのページは、ブロック編集が完全に正しくない場合でも、一目でそれとわかるドイツ語になっており、残った崩れは2回目のパスで修復される1文字の欠落である。105ページと109ページの行が他より低いスコアなのは、2ブロック探索がそれらの損傷を近似しかできないためである。それでも両方のテキストは生の出力で判読でき、どちらも Norbert の2017年の復号と一致する。

05 未解決の10通の検定

2つのブロック編集、15個の鍵

10通すべてを、最大2つのブロック編集を伴って15個の鍵すべてに対して実行した。それぞれの最良の結果は次のとおり。出典： blocks_out.txt:

−6.7 を超えるものは一つもない。同じ実行で解読済みのメッセージは −4.4 から −6.0 の間、ランダムな文字は約 −7.3 になる。したがって10通のどれも、15個の鍵のいずれかで2つ以下のブロック損傷を受けたものではない。これはまさに2017年の読み手たちが到達し、立ち止まった境界である。数字の多い出力は誤った鍵の通常の兆候である。ここでの実際の通信は大部分が文字であり、誤った方陣は二文字組を数字の升目に散らしてしまう。

153ページの2通に対する CHI 鍵

2017年9月、Norbert は検証はせずに、153ページの2通のメッセージは同じ期間のものなので CHI 鍵に属するかもしれないと示唆した。パリティ修復を伴う直接の復号でも、ブロック探索でも、両メッセージとも雑音しか返さない。原因は、さらに別の未掲載の鍵か、2ブロックより重い欠損である。

鍵なしの攻撃と、それが失敗する理由

未解決のメッセージのいくつかがコーパスにない鍵で暗号化されていたとすれば、その鍵は暗号文のみから復元しなければならない。 keyless.py は次を試みる。候補となる各長さで、転置を戻して得られる文字対の一致指数に基づいて列の順序を焼きなまし法で最適化する（正しく転置を戻せば単一アルファベット換字の二文字組が対になるからである）。その後、36記号の換字をドイツ語モデルで解く。未解決のメッセージに適用する前に、仕込んだ対照実験で実行した。同じ設計の長さ19の鍵で暗号化したドイツ語224文字である。

正しい長さは目立たない。19のピークは21、22、23に負け、換字の段階はどの長さでも収束しない。対照実験は復元されない。この目的のために作られた Lasry 自身のプログラムでさえ、長さ16の鍵を復元するのに356文字を必要とした。未解決の10通は84〜240文字の長さである。したがって、この長さでは鍵なしの復元は手が届かない。例外が一つある。未知の鍵を共有する2通以上の未解決メッセージは、2通の CHI メッセージがそうであったように、一緒に解ける可能性がある。暗号文にはそれがどれなのかを示すものは何もなく、当然の候補である153ページの2通は、一緒に試しても何も得られない。

06 現状と、それを変えうるもの

9通が復号され、3通が部分的、10通が未解決である。10通は2026年9月に検定され、最大2つのブロック編集では既知のどの鍵でも失敗する。それを変えうるものが3つある。

そのいずれかが届くまでの有用な成果物は、上の表、損傷した3つの方陣を修復し CHI 方陣を再構築した機械可読な15個の鍵、そして平文を与えられずに2017年の復号を再現する復号器である。

07 ファイル