チューリンゲリー
手動暗号解読法

チューリンゲリー[1]またはチューリング法[2]（ピーター・エリクソン、ピーター・ヒルトン、ドナルド・ミチー[3]によって揶揄されてチューリング主義と呼ばれた）は、第二次世界大戦中の1942年7月[4]に、数学者で暗号解読者のアラン・チューリングがブレッチリー・パークの英国政府暗号学校で考案した手動の暗号解読法である。[5] [6]これは、ドイツの秘密書記（ Geheimschreiber ）機械の1つであるSZ40およびSZ42テレタイプローターストリーム暗号機によって生成されたローレンツ暗号の解読に使用された。イギリス軍はモールス信号以外の通信を「フィッシュ」 、この機械から発信される通信を「タニー」（マグロの別名）とコードネームで呼んだ。

タニーのメッセージを読むには、まずシステムの論理構造を知ること、次にホイール上のアクティブカムの周期的に変化するパターンを導き出すこと、そして最後にこのメッセージのためのスクランブラーホイールの開始位置（メッセージキー）を確立することが必要だった。[7]タニーの論理構造は、ウィリアム・タットと同僚[8]によって1942年1月までの数ヶ月をかけて解明された。[9]メッセージキーを導き出すことはブレッチリー・パークでは「セッティング」と呼ばれていたが、チューリンガリーの目標はカムパターンの導き出し（これは「ホイールブレーキング」として知られていた）であった。

ドイツの通信士は、同じキーで複数のメッセージを送信する際にミスを犯し、「深度」と呼ばれる現象が発生し、そのキーの導出を可能にしました。チューリンガリー法は、このようなキーストリームに適用され、カムの設定を導出しました。[10]

SZ40とSZ42

タニーシステムの論理的機能は、ブレッチリーパークの暗号解読者がマシンの1つを見るずっと前から解明されていました。それが起こったのは1945年、ヨーロッパでの連合軍の勝利の直前でした。[11]

ロレンツSZマシンには、それぞれ異なる数のカム（または「ピン」）を備えた12個のホイールがありました。

SZマシンは、バーナムストリーム暗号を実装した12輪ローター 暗号機でした。これらは標準的なローレンツ式テレタイププリンタにインライン接続されていました。メッセージ文字は5ビットの国際電信アルファベット第2号（ITA2）で符号化されていました。出力暗号文文字は、数学表記では「」で表される「排他的論理和」（XOR）関数を用いて、擬似乱数による文字単位の鍵ストリームと入力文字を組み合わせることで生成されました。平文、暗号文、暗号鍵の関係は次のようになります。 ⊕ {\displaystyle \oplus}

c 私 p h e r t e × t ＝ p l 1つの 私 n t e × t ⊕ け e y {\displaystyle \mathrm {暗号文} =\mathrm {平文} \oplus \mathrm {鍵} }

同様に、解読では、暗号文を同じキーと組み合わせて平文を生成します。

p l 1つの 私 n t e × t ＝ c 私 p h e r t e × t ⊕ け e y {\displaystyle \mathrm {平文} =\mathrm {暗号文} \oplus \mathrm {鍵} }

これにより、同じ設定を持つ同じマシンを暗号化と解読の両方に使用できるようになるという本質的な相互性が生まれます。

各文字の鍵の5ビットは、機械の2つの部分にある対応するホイールによって生成されました。これらはカイ（）ホイールとプサイ（）ホイールと呼ばれていました。カイホイールは、各文字ごとに同じ位置で動きました。プサイホイールもすべて一緒に動きましたが、各文字の後には動きませんでした。これらの動きは、2つのミュー（）ホイール、つまり「モーター」ホイールによって制御されました。 [12] χ {\displaystyle \chi } ψ {\displaystyle \psi} μ {\displaystyle \mu}

SZマシンによって生成された鍵ストリームには、カイ成分とプサイ成分が含まれており、これらはXOR関数で結合されています。したがって、暗号化のために平文と結合された鍵、あるいは復号のために暗号文と結合された鍵は、次のように表すことができます。[12]

け e y ＝ カイ - け e y ⊕ サイ - け e y {\displaystyle \mathrm {key} ={\textit {chi}}\mathrm {{\mbox{-}}key} \oplus {\textit {psi}}\mathrm {{\mbox{-}}key} }

象徴的に：

K ＝ χ ⊕ ψ {\displaystyle K=\chi \oplus \psi }

12個の車輪にはそれぞれ、一連のカム（または「ピン」）が取り付けられていました。これらのカムは、上昇または下降の位置に調整できました。上昇位置では「マーク」（ブレッチリー・パークでは「×」と表記され、2進数の1に相当）を生成し、下降位置では「スペース」（「・」と表記され、2進数の0に相当）を生成します。各車輪のカムの数は、車輪を1回転させるために必要なインパルスの数に等しく、これらの数はすべて互いに素であるため、パターンが繰り返されるまでの時間が最も長くなります。合計501個のカムの場合、これは2の501乗、つまり約10の151乗となり、天文学的な数字となります。[13]しかし、5つのインパルスを個別に考えれば、これらの数字ははるかに扱いやすくなります。任意の一対の気の輪の回転周期の積は、41×31=1271 から 26×23=598 の間の数値になります。

ホイール番号 1 2 3 4 5 6 7 8 9 10 11 12
BPホイール名[14] ψ {\displaystyle \psi} 1 ψ {\displaystyle \psi} 2 ψ {\displaystyle \psi} 3 ψ {\displaystyle \psi} 4 ψ {\displaystyle \psi} 5 μ {\displaystyle \mu} 37 μ {\displaystyle \mu} 61 χ {\displaystyle \chi } 1 χ {\displaystyle \chi } 2 χ {\displaystyle \chi } 3 χ {\displaystyle \chi } 4 χ {\displaystyle \chi } 5
カムの数（ピン） 43 47 51 53 59 37 61 41 31 29 26 23

差分化

暗号解読には、鍵となる可能性のある様々な文字を排除する道筋となる、ある種のパターンを見つけることがしばしば含まれます。ブレッチリー・パークでは、鍵または暗号文に含まれる隣接する2つの文字の値のXOR（排他的論理和）の組み合わせは、差（ギリシャ文字のデルタで表されます）と呼ばれていました。これは、XORが 法2の減算（「借用」なし）と同じであり、さらに法2の加算（「繰り上がり」なし）と同じであるためです。したがって、鍵（K）に含まれる文字の差は次のように求められます。下線は後続の文字を示します。 Δ {\displaystyle \Delta } Δ K {\displaystyle \Delta K}

Δ K ＝ K ⊕ K _ {\displaystyle \Delta K=K\oplus {\underline {K}}}

(平文、暗号文、およびキーの 2 つのコンポーネントについても同様です)。

それらの関係は、それらが区別される場合にも適用されます。例えば、以下の例も同様です。

K ＝ χ ⊕ ψ {\displaystyle K=\chi \oplus \psi }

事実は次の通りです:

Δ K ＝ Δ χ ⊕ Δ ψ {\displaystyle \Delta K=\Delta \chi \oplus \Delta \psi }

平文を P、暗号文を Z で表すと、次のことも成り立ちます。

Δ Z ＝ Δ P ⊕ Δ χ ⊕ Δ ψ {\displaystyle \Delta Z=\Delta P\oplus \Delta \chi \oplus \Delta \psi }

そして：

Δ P ＝ Δ Z ⊕ Δ χ ⊕ Δ ψ {\displaystyle \Delta P=\Delta Z\oplus \Delta \chi \oplus \Delta \psi }

差分化によってタニー暗号への道が開かれた理由は、暗号文中の文字の頻度分布はランダムストリームと区別できないものの、鍵のカイ要素を取り除いた暗号文では同じことが当てはまらないためである。これは、平文に繰り返し文字が含まれており、サイホイールが動かない場合、差分化されたサイ文字（）はヌル文字（「·····」または00000）、あるいはブレッチリー・パークの用語で言えば「/」となるためである。このヌル文字は任意の文字とXOR演算しても効果を持たないため、このような状況では となる。平文中の繰り返し文字は、ドイツ語の特性（EE、TT、LL、SSは比較的一般的）[15]と、電信士が数字シフト文字と文字シフト文字を頻繁に繰り返した[16 ]ことの両方により、より頻繁に見られた。これは、通常の電信メッセージでこれらの文字が失われると意味不明な内容になる可能性があるためである。[17] Δ ψ {\displaystyle \Delta \psi } Δ χ ＝ Δ K {\displaystyle \Delta \chi =\Delta K}

タニーに関する一般報告書を引用すると：

チューリンゲリーは、現在では「1」と呼ばれる1音階の鍵差 から、通常の鍵では得られない情報が得られるという原理を提唱しました。この原理は、車輪の調律と調整におけるほぼすべての統計的手法の基礎となりました。[1] Δ K {\displaystyle \Delta K} Δ {\displaystyle \Delta }

ビットレベルの差分

ITA2コードの5ビット文字全体に差分を適用するだけでなく、個々のインパルス（ビット）にも差分を適用しました。つまり、最初のインパルスはwheelsとで暗号化され、1で差分が取られました。 χ 1 {\displaystyle \chi _{1}} ψ 1 {\displaystyle \psi_{1}}

Δ K 1 ＝ K 1 ⊕ K 1 _ {\displaystyle \Delta K_{1}=K_{1}\oplus {\underline {K_{1}}}}

そして2番目の衝動は:

Δ K 2 ＝ K 2 ⊕ K 2 _ {\displaystyle \Delta K_{2}=K_{2}\oplus {\underline {K_{2}}}}

等々。

また、各インパルスにおけるカイホイールとプサイホイールの周期性（最初のインパルスではそれぞれ 41 と 43）が のパターンに反映されていることも注目に値します。しかし、プサイホイールはカイホイールのように入力文字ごとに進むわけではないため、 では 41 × 43 = 1763 文字ごとにパターンが単純に繰り返されるのではなく、より複雑なシーケンスになっています。 Δ K {\displaystyle \Delta K} Δ K 1 {\displaystyle \Delta K_{1}}

チューリング法

1942年7月、チューリングは研究部門で数週間を過ごした。[18]彼は深海から得られた鍵からタニーを解読する問題に興味を持つようになった。[3] 7月に、彼は鍵の長さからカムの設定を導き出す方法を開発した。[1]それは反復的な、ほとんど試行錯誤のプロセスを含んでいた。それは、差分されたサイ文字がヌル文字(" ····· " または 00000)、  /の場合、これを他の文字と排他的論理和しても変化しないという事実に依存していた。したがって、デルタキー文字は5つのカイホイールの文字 (つまり)と同じである。 Δ χ ＝ Δ K {\displaystyle \Delta \chi =\Delta K}

デルタサイ文字は平均して半分の時間、ヌル文字であった（サイホイールが50%の時間しか動かなかったため）ことから、50%の確率で正しい仮定であった。このプロセスは、特定の文字をその位置のΔ文字として扱うことから始まった。結果として得られた各カイホイールの推定ビットパターンは、キーの文字数と同じ数の列と、5つのビットを表す5つの行を含む1枚の紙に記録された。タットの研究から得られた各ホイールの周期性に関する知識を前提とすると、これによりこれらの値がキーの残りの適切な位置に伝播することができた。 Δ K ＝ Δ χ {\displaystyle \Delta K=\Delta \chi } Δ K {\displaystyle \Delta K} χ {\displaystyle \chi } Δ χ {\displaystyle \Delta \chi }

また、各カイホイールに1枚ずつ、計5枚のシートのセットも用意されました。これらには、該当するカイホイールのカムの数に対応する列のセットが含まれており、「ケージ」と呼ばれていました。したがって、ケージには29の列がありました。[19]値の連続的な「推測」により、さらに推定カムの状態の値が生成されました。これらは、以前の仮定と一致する場合もあれば、一致しない場合もあります。これらのシートで一致と不一致の数をカウントしました。不一致が一致を大幅に上回った場合、文字はヌル文字「 / 」ではないと仮定したため、関連する仮定は無視されました。段階的に、カイホイールのすべてのカム設定が推定され、そこからpsiとモーターホイールのカム設定が推定されました。 χ 3 {\displaystyle \chi _{3}} Δ χ {\displaystyle \Delta \chi } Δ ψ {\displaystyle \Delta \psi }

この方法の経験が蓄積されるにつれて、改良が加えられ、元の約500文字よりもはるかに短いキーの長さでも使用できるようになりました。[1]

参照

参考文献と注釈

  1. ^ abcd Good、Michie、Timms 1945、p. 313、Testery Methods 1942–1944
  2. ^ 政府暗号学校 1944年、89ページ
  3. ^ コープランド 2006、380ページ
  4. ^ Good, Michie & Timms 1945, p. 309 in Early Hand Methods
  5. ^ ホッジス 1992、230–231ページ
  6. ^ コープランド 2006, 380–382ページ
  7. ^ チャーチハウス 2002、4ページ
  8. ^ トゥッテ 1998、5ページ
  9. ^ グッド 1993、161ページ
  10. ^ コープランド 2006, p. 381
  11. ^ セールnd
  12. ^ ab Good, Michie & Timms 1945, p. 7 in German Tunny
  13. ^ チャーチハウス 2002、158ページ
  14. ^ Good, Michie & Timms 1945, p. 6 in German Tunny
  15. ^ Singh, Simon , The Black Chamber 、 2012年4月28日閲覧。
  16. ^ ニューマン1944 年頃p. 387
  17. ^ カーター、3ページ
  18. ^ トゥッテ 2006、359、360ページ
  19. ^ Copeland 2006, p. 385マグロに関する一般報告書のケージを再現 χ 3 {\displaystyle \chi _{3}}

参考文献

  • Carter, Frank, Bletchley Park Technical Papers: Colossus and the Breaking of the Lorenz Cipher (PDF) 、 2012年5月8日時点のオリジナル(PDF)からアーカイブ、 2011年1月28日閲覧。
  • チャーチハウス、ロバート（2002）、コードと暗号：ジュリアス・シーザー、エニグマ、そしてインターネット、ケンブリッジ：ケンブリッジ大学出版局、ISBN 978-0-521-00890-7
  • コープランド、ジャック（2006年）「チューリンガル」、コープランド、B.ジャック（編）、コロッサス：ブレッチリー・パークの暗号解読コンピュータの秘密、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-284055-4
  • グッド、ジャック（1993）、「エニグマと魚」、ヒンズリー、FH、ストリップ、アラン（編）、コードブレーカー：ブレッチリーパークの内幕、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-280132-6
  • グッド、ジャック、ミチー、ドナルド、ティムズ、ジェフリー（1945年）、マグロに関する一般報告書：統計手法に重点を置いた、英国公文書館HW 25/4およびHW 25/5 、 2010年9月15日閲覧。このバージョンはファクシミリコピーですが、この文書の大部分の転写が「.pdf」形式で以下にあります。Sale , Tony (2001)、「General Report on Tunny」、Newmanry History、Tony Saleによってフォーマットされた(PDF) 、2010年9月20日取得。、およびパート1のウェブトランスクリプト：Ellsbury, Graham, General Report on Tunny With Emphasis on Statistical Methods 、 2010年11月3日取得
  • 政府暗号学校（1944年）、ブレッチリーパーク1944年暗号辞典、トニー・セールによるフォーマット（PDF）、2010年10月7日取得
  • ホッジス、アンドリュー（1992）、アラン・チューリング：エニグマ、ロンドン：ヴィンテージ、ISBN 978-0-09-911641-7
  • ニューマン、マックス（1944年頃）、「付録7：Δ法」、コープランド、B・ジャック（編）『コロッサス：ブレッチリー・パークの暗号解読コンピュータの秘密』、オックスフォード：オックスフォード大学出版局、ISBN χ {\displaystyle \chi }  978-0-19-284055-4 {{citation}}:ISBN / 日付の非互換性（ヘルプ）
  • セール、トニー（nd）、「ロレンツ暗号とブレッチリー・パークの解読法」odesandciphers.org.uk 、 2010年10月21日閲覧。
  • Tutte, William T. (2006)、「My Work at Bletchley Park」、Copeland, B. Jack (ed.)、Colossus: The Secrets of Bletchley Park's Codebreaking Computers、オックスフォード: オックスフォード大学出版局、ISBN 978-0-19-284055-4
  • Tutte, WT (19 June 1998), Fish and I (PDF) 、 2007年7月10日時点のオリジナル(PDF)からアーカイブ、 2010年10月7日閲覧。ウォータールー大学におけるトゥット教授の講義の記録
「https://en.wikipedia.org/w/index.php?title=チューリンガル&oldid=1312263686」より取得