チューリンガリー

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

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

ドイツのオペレーターが同じキーで複数のメッセージを送信した際に「深さ」を生成し、そのキーの導出を可能にした。チューリング法がそのようなキーストリームに適用され、カメラの設定が導出された。^{[ 10 ]}

タニーシステムの論理的な動作原理は、ブレッチリー・パークの暗号解読者たちがその機械を目にするずっと前に解明されていた。実際に機械が目にされたのは1945年、ヨーロッパにおける連合国の勝利の直前のことだった。^{[ 11 ]}

SZ マシンは、 Vernamストリーム暗号を実装した12 ホイールローター暗号機でした。これらは標準的な Lorenz テレプリンターにインラインで接続されていました。メッセージ文字は5 ビットの国際電信アルファベット No. 2 (ITA2)でエンコードされました。出力暗号文文字は、擬似乱数文字ごとのキー ストリームと入力文字を「排他的論理和(XOR)」関数を使用して組み合わせることによって生成されました。${\displaystyle \oplus }$数学的表記では、平文、暗号文、暗号鍵の関係は次のようになります。

${\displaystyle \mathrm {ciphertext} =\mathrm {plaintext} \oplus \mathrm {key} }$

同様に、復号化においては、暗号文を同じ鍵と組み合わせることで平文が得られました。

${\displaystyle \mathrm {plaintext} =\mathrm {ciphertext} \oplus \mathrm {key} }$

これにより、暗号化と復号化の両方に同じ設定の同じマシンを使用できるようにする、本質的な相互性が実現される。

各文字のキーの 5 ビットはそれぞれ、機械の 2 つの部分にある関連するホイールによって生成されました。これらはカイ(${\displaystyle \chi }$）ホイール、そしてpsi（${\displaystyle \psi }$）ホイール。カイホイールはすべて、各文字ごとに 1 つの位置で動きました。プサイホイールもすべて一緒に動きましたが、各文字の後ではありませんでした。それらの動きは 2 つのミューホイールによって制御されました。${\displaystyle \mu }$）または「モーター」ホイール。^{[ 12 ]}

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

${\displaystyle \mathrm {key} ={\textit {chi}}\mathrm {{\mbox{-}}key} \oplus {\textit {psi}}\mathrm {{\mbox{-}}key} }$

象徴的に：

${\displaystyle K=\chi \oplus \psi }$

12 個の車輪にはそれぞれ、周囲に一連のカム (または「ピン」) がありました。これらのカムは、上げたり下げたりした位置に設定できました。上げられた位置では、「マーク」が生成され、これはブレッチリー パークでは「×」と表記され、2 進数の 1 に相当します。下げられた位置では、「スペース」が生成され、「・」と表記され、2 進数の 0 に相当します。各車輪のカムの数は、車輪が 1 回転するのに必要なインパルスの数に等しくなります。これらの数はすべて互いに素であるため、パターンが繰り返されるまでに可能な限り長い時間が得られます。合計 501 個のカムで、これは 2 ^{501に等しく、約 10 151}で、天文学的に大きな数です。^{[ 13 ]}ただし、5 つのインパルスを個別に考えると、数ははるかに扱いやすくなります。任意の2つのカイホイールの回転周期の積は、41×31=1271から26×23=598までの間の数値になります。

暗号解読では、鍵の可能性の範囲を絞り込む方法となる何らかのパターンを見つけることがしばしば必要となる。ブレッチリー・パークでは、鍵または暗号文中の隣接する 2 つの文字の値の XOR 組み合わせは、差分 (ギリシャ文字デルタで表される) と呼ばれていた。${\displaystyle \Delta }$なぜなら、XOR はモジュロ2 減算 (「借り」なし)と同じであり、また、偶然にもモジュロ 2 加算 (「繰り上がり」なし) と同じだからです。したがって、キー (K) の文字の場合、差は${\displaystyle \Delta K}$以下のようにして得られた。下線は後続の文字を示す。

${\displaystyle \Delta K=K\oplus {\underline {K}}}$

（平文、暗号文、および鍵の2つの構成要素についても同様です。）

それらの間の関係は、それらが差異を持つ場合にも適用されます。例えば、以下のような場合です。

${\displaystyle K=\chi \oplus \psi }$

事実は以下のとおりです。

${\displaystyle \Delta K=\Delta \chi \oplus \Delta \psi }$

平文をP、暗号文をZで表す場合、以下のことも成り立つ。

${\displaystyle \Delta Z=\Delta P\oplus \Delta \chi \oplus \Delta \psi }$

そして：

${\displaystyle \Delta P=\Delta Z\oplus \Delta \chi \oplus \Delta \psi }$

差分法がタニー暗号への突破口となった理由は、暗号文中の文字の頻度分布はランダムな流れと区別できなかったが、鍵のカイ要素が削除されたバージョンの暗号文ではそうではなかったからである。これは、平文に繰り返し文字が含まれており、プサイホイールが進まなかった場合、差分されたプサイ文字（${\displaystyle \Delta \psi }$) はヌル文字 (" ····· " または 00000) または、ブレッチリー・パークの用語では " / " になります。このヌル文字は任意の文字と XOR 演算しても効果はありません。したがって、このような状況では、${\displaystyle \Delta \chi =\Delta K}$平文中の文字の繰り返し頻度が高かったのは、ドイツ語の特徴（EE、TT、LL、SSが比較的よく使われる）^{[ 15 ]}と、電信技師が数字シフト文字と文字シフト文字を頻繁に繰り返していたためである^{[ 16 ]。}これらの文字が通常の電信メッセージで失われると意味不明なメッセージになる可能性があるからである^{[ 17 ]}。

タニーに関する総括報告書からの引用：

チューリングは、鍵の差が1である原理を導入した。 ${\displaystyle \Delta K}$通常の鍵では得られない情報が得られる可能性がある。${\displaystyle \Delta }$この原理は、車輪のブレーキングとセッティングに関するほぼすべての統計的方法の基本的な基礎となるものであった。^{[ 1 ]}

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

デルタプサイ文字が平均して半分の時間ヌル文字であったことを考えると（プサイホイールが動いたのは時間の 50% だけであったため）、${\displaystyle \Delta K=\Delta \chi }$正解する確率は50％だった。プロセスは特定の${\displaystyle \Delta K}$Δ としての特性${\displaystyle \chi }$その位置に対して。結果と​​して得られた各カイホイールのビットの推定ビットパターンは、鍵の文字数と同じ数の列と、5ビットを表す5行を含む紙に記録された。${\displaystyle \Delta \chi }$タッテの研究から各歯車の周期性が分かっていたため、これらの値を鍵盤の残りの部分の適切な位置に伝播させることができた。

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

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

• バンブリズム
• 差分暗号解読

• カーター、フランク、「ブレッチリー・パーク技術論文：コロッサスとローレンツ暗号の解読（PDF）」 、 2012年5月8日にオリジナル（PDF）からアーカイブ、 2011年1月28日に取得
• チャーチハウス、ロバート（2002）、『暗号と暗号：ユリウス・カエサル、エニグマ、そしてインターネット』、ケンブリッジ：ケンブリッジ大学出版局、ISBN 978-0-521-00890-7
• コープランド、ジャック（2006）、「チューリングリー」、コープランド、B.ジャック（編）、『コロッサス：ブレッチリー・パークの暗号解読コンピュータの秘密』、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-284055-4
• Good, Jack (1993)、「Enigma and Fish」、Hinsley, FH ; Stripp, Alan (編)『Codebreakers: The inside story of Bletchley Park』、Oxford: Oxford University Press、ISBN 978-0-19-280132-6
• Good, Jack ; Michie, Donald ; Timms, Geoffrey (1945)、「マグロに関する総合報告書：統計的手法に重点を置いて」、英国国立公文書館 HW 25/4 および HW 25/5 、 2010年9月15日取得このバージョンはファクシミリ版ですが、この文書の大部分の転写が「.pdf」形式で以下のURLにあります：Sale, Tony (2001), Part of the "General Report on Tunny", the Newmanry History, formatted by Tony Sale (PDF) , retrieved 20 September 2010パート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：Δ${\displaystyle \chi }$-Method」、B.ジャック・コープランド編『コロッサス：ブレッチリー・パークの暗号解読コンピュータの秘密』、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-284055-4{{citation}}ISBN /日付の不一致（ヘルプ）
• Sale, Tony (日付不明)、「ローレンツ暗号とブレッチリー・パークがそれを解読した方法」、odesandciphers.org.uk 、 2010年10月21日取得
• タット、ウィリアム・T. (2006)、「ブレッチリー・パークでの私の仕事」、コープランド、B・ジャック(編)、『コロッサス：ブレッチリー・パークの暗号解読コンピュータの秘密』、オックスフォード：オックスフォード大学出版局、ISBN 978-0-19-284055-4
• Tutte, WT (1998年6月19日)、「魚と私」（PDF） 、 2007年7月10日にオリジナル（PDF）からアーカイブ、2010年10月7日に取得ウォータールー大学で行われたタッテ教授の講演の記録