Turingery - Turingery

Turingery oder Turings Methode (spielerisch genannt Turingismus von Peter Ericsson, Peter Hilton und Donald Michie ) war eine manuelle Codebrecher - Methode entwickelt im Juli 1942 von dem Mathematiker und Kryptoanalytiker Alan Turing an der britischen Regierung Kodex und Cypher Schule in Bletchley Park während des Zweiten Weltkriegs . Es war für den Einsatz in Kryptanalyse des Chiffre Lorenz durch das erzeugte SZ40 und SZ42 Fernschreib- Rotorstromchiffre Maschinen, eine der Deutschen ' Geheimschreiber (secret writer) Maschinen. Der britische Codename Nicht- Morse- Verkehr "Fisch" und der von dieser Maschine " Thunfisch " (ein anderes Wort für den Thunfisch ).

Das Lesen einer Tunny-Nachricht erforderte zum einen, dass die logische Struktur des Systems bekannt war, zum anderen, dass das periodisch geänderte Muster der aktiven Nocken auf den Rädern abgeleitet wurde, und zum anderen, dass die Startpositionen der Scrambler-Räder für diese Nachricht - der Nachrichtenschlüssel - waren etabliert. Die logische Struktur von Tunny wurde von William Tutte und Kollegen über mehrere Monate bis Januar 1942 ausgearbeitet. Das Ableiten des Nachrichtenschlüssels wurde im Bletchley Park als "Einstellung" bezeichnet, aber es war die Ableitung der Nockenmuster - was als "bekannt" bezeichnet wurde. Radbruch "- das war das Ziel von Turingery.

Deutsche Bedienerfehler bei der Übertragung von mehr als einer Nachricht mit demselben Schlüssel, die eine "Tiefe" erzeugten , ermöglichten die Ableitung dieses Schlüssels. Turingery wurde auf einen solchen Schlüsselstrom angewendet, um die Nockeneinstellungen abzuleiten.

Die SZ40 und SZ42

Die logische Funktionsweise des Tunny-Systems wurde lange bevor die Kryptoanalytiker von Bletchley Park eine der Maschinen sahen - was erst 1945 geschah, kurz vor dem Sieg der Alliierten in Europa.

Die Lorenz SZ-Maschinen hatten 12 Räder mit jeweils unterschiedlicher Anzahl von Nocken (oder "Stiften").

Radnummer	1	2	3	4	5	6	7	8	9	10	11	12
BP Radname	${\ displaystyle \ psi}$ ₁	${\ displaystyle \ psi}$ ₂	${\ displaystyle \ psi}$ ₃	${\ displaystyle \ psi}$ ₄	${\ displaystyle \ psi}$ ₅	${\ displaystyle \ mu}$ ₃₇	${\ displaystyle \ mu}$ ₆₁	${\ displaystyle \ chi}$ ₁	${\ displaystyle \ chi}$ ₂	${\ displaystyle \ chi}$ ₃	${\ displaystyle \ chi}$ ₄	${\ displaystyle \ chi}$ ₅
Anzahl der Nocken (Stifte)	43	47	51	53	59	37	61	41	31	29	26	23

Die SZ-Maschinen waren 12-Rad- Rotor- Verschlüsselungsmaschinen , die eine Vernam- Stromverschlüsselung implementierten . Sie wurden an Standard-Lorenz-Ferndrucker angeschlossen. Die Nachrichtenzeichen wurden in der codierten 5-Bit Internationalen Telegraphy Alphabet No. 2 (ITA2) . Die ausgegebenen Chiffretextzeichen wurden durch Kombinieren eines pseudozufälligen zeichenweisen Schlüsselstroms mit den eingegebenen Zeichen unter Verwendung der Funktion " Exklusiv oder " (XOR) erzeugt, die in mathematischer Notation als " " ${\ displaystyle \ oplus}$ symbolisiert ist . Die Beziehung zwischen Klartext , Chiffretext und kryptografischem Schlüssel ist dann:

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

In ähnlicher Weise wurde zum Entschlüsseln der Chiffretext mit demselben Schlüssel kombiniert, um den Klartext zu erhalten:

{\ displaystyle \ mathrm {Klartext} = \ mathrm {Chiffretext} \ oplus \ mathrm {Schlüssel}}

Dies erzeugt die wesentliche Reziprozität, damit dieselbe Maschine mit denselben Einstellungen sowohl für die Verschlüsselung als auch für die Entschlüsselung verwendet werden kann.

Jedes der fünf Bits des Schlüssels für jedes Zeichen wurde von den relevanten Rädern in zwei Teilen der Maschine erzeugt. Diese wurden als Chi ( ) - Räder und Psi ( ) - Räder bezeichnet. Die Chi- Räder bewegten sich alle für jeden Charakter auf einer Position. Die Psi- Räder bewegten sich ebenfalls alle zusammen, jedoch nicht nach jedem Zeichen. Ihre Bewegung wurde von den beiden mu ( ) - oder "Motor" -Rädern gesteuert . ${\ displaystyle \ chi}$ ${\ displaystyle \ psi}$ ${\ displaystyle \ mu}$

Der von den SZ-Maschinen erzeugte Schlüsselstrom hatte somit eine Chi- Komponente und eine Psi- Komponente, die zusammen mit der XOR-Funktion kombiniert wurden. Der Schlüssel, der mit dem Klartext zum Verschlüsseln oder mit dem Chiffretext zum Entschlüsseln kombiniert wurde, kann also wie folgt dargestellt werden.

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

Symbolisch:

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

Die zwölf Räder hatten jeweils eine Reihe von Nocken (oder "Stiften") um sich herum. Diese Nocken können angehoben oder abgesenkt werden. In der angehobenen Position erzeugten sie eine "Markierung" × "(" 1 "in binär), in der abgesenkten Position erzeugten sie ein" Leerzeichen " · " ("0" in binär). Die Anzahl der Nocken an jedem Rad entsprach der Anzahl der Impulse, die erforderlich waren, um eine vollständige Umdrehung durchzuführen. Diese Zahlen sind alle Co-Prime miteinander, die eine möglichst lange Zeit vor dem wiederholten Muster. Bei insgesamt 501 Nocken entspricht dies 2 ^501, was ungefähr 10 ^{151 entspricht} , eine astronomisch große Zahl. Wenn die fünf Impulse jedoch unabhängig voneinander betrachtet werden, sind die Zahlen viel besser zu handhaben. Das Produkt der Rotationsperiode eines Paares von Chi- Rädern ergibt Zahlen zwischen 41 × 31 = 1271 und 26 × 23 = 598.

Differenzierung

Bei der Kryptoanalyse werden häufig Muster gefunden, mit denen eine Reihe von Schlüsselmöglichkeiten beseitigt werden können. In Bletchley Park die XOR - Verknüpfung der Werte von zwei benachbarten Buchstaben in dem Schlüssel oder der verschlüsselte Text wurde die Differenz genannt (durch den griechischen Buchstaben symbolisiert Delta ) , weil XOR ist die gleiche wie Modulo 2 Subtraktion (ohne „borrow“) - und, nebenbei bemerkt , Modulo 2 Addition (ohne "Carry"). Für die Zeichen in der Taste (K) wurde der Unterschied wie folgt erhalten, wobei die Unterstreichung das nachfolgende Zeichen angibt: ${\ displaystyle \ Delta}$ ${\ displaystyle \ Delta K}$

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

(Ähnlich mit dem Klartext, dem Chiffretext und den beiden Komponenten des Schlüssels).

Die Beziehung zwischen ihnen gilt, wenn sie differenziert sind. Zum Beispiel sowie:

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

Es ist der Fall, dass:

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

Wenn der Klartext durch P und der Cipertext durch Z dargestellt wird, gilt auch Folgendes:

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

Und:

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

Der Grund, warum die Differenzierung einen Weg nach Tunny bot, war, dass die Häufigkeitsverteilung der Zeichen im Chiffretext zwar nicht von einem zufälligen Strom unterschieden werden konnte, dies jedoch nicht für eine Version des Chiffretextes galt, aus der das Chi- Element des Schlüssels stammte Wurde entfernt. Dies liegt daran, dass, wenn der Klartext ein wiederholtes Zeichen enthielt und sich die Psi- Räder nicht bewegten, das differenzierte Psi- Zeichen ( ) das Nullzeichen (" ····· " oder 00000) oder in der Bletchley Park-Terminologie das Nullzeichen wäre. " / ". Wenn XOR-ed mit einem beliebigen Zeichen ausgeführt wird, hat dieses Nullzeichen keine Auswirkung . Wiederholte Zeichen im Klartext waren häufiger, sowohl aufgrund der Merkmale des Deutschen (EE, TT, LL und SS sind relativ häufig) als auch, weil Telegraphen häufig die Zeichen der Zahlenverschiebung und der Buchstabenverschiebung als ihren Verlust in einem gewöhnlichen Telegraphen wiederholten Nachricht könnte zu Kauderwelsch führen . ${\ displaystyle \ Delta \ psi}$ ${\ displaystyle \ Delta \ chi = \ Delta K}$

Um den allgemeinen Bericht über Thunfisch zu zitieren:

Turingery führte das Prinzip ein, dass der bei einem differenzierte Schlüssel, der jetzt genannt wird , Informationen liefern kann, die von einem normalen Schlüssel nicht zu erhalten sind. Dieses Prinzip sollte die Grundlage für nahezu alle statistischen Methoden zum Brechen und Setzen von Rädern sein. ${\ displaystyle \ Delta K}$ ${\ displaystyle \ Delta}$

Differenzierung auf Bitebene

Die Differenzierung wurde nicht nur auf die vollständigen 5-Bit-Zeichen des ITA2- Codes angewendet, sondern auch auf die einzelnen Impulse (Bits). Also, für den ersten Impuls, der von Rädern verschlüsselt und bei einem unterschieden wurde: ${\ displaystyle \ chi _ {1}}$ ${\ displaystyle \ psi _ {1}}$

{\ displaystyle \ Delta K_ {1} = K_ {1} \ oplus {\ underline {K_ {1}}}}

Und für den zweiten Impuls:

{\ displaystyle \ Delta K_ {2} = K_ {2} \ oplus {\ underline {K_ {2}}}

Und so weiter.

Es ist auch erwähnenswert, dass sich die Periodizität der Chi und Psi Räder für jeden Impuls (41 bzw. 43 für den ersten) in seinem Muster von widerspiegelt . Da jedoch die Psi- Räder nicht für jedes Eingabezeichen vorrückten, wie auch die Chi- Räder, war es nicht einfach eine Wiederholung des Musters alle 41 × 43 = 1763 Zeichen für , sondern eine komplexere Sequenz. ${\ displaystyle \ Delta K}$ ${\ displaystyle \ Delta K_ {1}}$

Turings Methode

Im Juli 1942 verbrachte Turing einige Wochen in der Forschungsabteilung. Er hatte sich für das Problem interessiert, Thunfisch aus den Schlüsseln zu brechen, die er aus der Tiefe erhalten hatte . Im Juli entwickelte er die Methode zum Ableiten der Nockeneinstellungen aus einer Schlüssellänge. Es handelte sich um einen iterativen , fast aus Versuch und Irrtum bestehenden Prozess. Es beruhte auf der Tatsache, dass, wenn das differenzierte psi- Zeichen das Nullzeichen ist (" ····· " oder 00000), / , dies durch XOR-Verknüpfung mit einem anderen Zeichen nicht geändert wird. Somit gibt das Delta-Schlüsselzeichen den Charakter der fünf Chi- Räder (dh ) an. ${\ displaystyle \ Delta \ chi = \ Delta K}$

Angesichts der Tatsache, dass das Delta- Psi- Zeichen im Durchschnitt die Hälfte der Zeit das Nullzeichen war, eine Annahme, die eine 50% ige Chance hatte, korrekt zu sein. Der Prozess begann damit, dass ein bestimmtes Zeichen als Δ für diese Position behandelt wurde. Das resultierende mutmaßliche Bitmuster von × und · für jedes Chi- Rad wurde auf einem Blatt Papier aufgezeichnet, das so viele Spalten enthielt, wie Zeichen im Schlüssel vorhanden waren, und fünf Zeilen, die die fünf Impulse des Schlüssels darstellten . Angesichts des Wissens aus Tuttes Arbeit über die Periodizität jedes der Räder ermöglichte dies die Ausbreitung dieser Werte an den entsprechenden Positionen im Rest des Schlüssels. ${\ displaystyle \ Delta K = \ Delta \ chi}$ ${\ displaystyle \ Delta K}$ ${\ displaystyle \ chi}$ ${\ displaystyle \ Delta \ chi}$

Ein Satz von fünf Blättern, eines für jedes der Chi- Räder, wurde ebenfalls vorbereitet. Diese enthielten eine Reihe von Säulen, deren Anzahl den Nocken für das entsprechende Chi- Rad entsprach, und wurden als "Käfig" bezeichnet. Der Käfig hatte also 29 solcher Säulen. Aufeinanderfolgende 'Vermutungen' von Werten erzeugten dann weitere mutmaßliche Nockenzustandswerte. Diese können früheren Annahmen entweder zustimmen oder nicht zustimmen, und auf diesen Blättern wurde eine Reihe von Vereinbarungen und Meinungsverschiedenheiten getroffen. Wenn Meinungsverschiedenheiten die Vereinbarungen erheblich überwogen, wurde die Annahme getroffen, dass das Zeichen nicht das Nullzeichen " / " ist, sodass die entsprechende Annahme abgezinst wurde. Nach und nach wurden alle Nockeneinstellungen der Chi- Räder und daraus die Nenneinstellungen für Psi und Motorrad abgeleitet. ${\ displaystyle \ chi _ {3}}$ ${\ displaystyle \ Delta \ chi}$ ${\ displaystyle \ Delta \ psi}$

Als die Erfahrung mit der Methode entwickelt wurde, wurden Verbesserungen vorgenommen, die es ermöglichten, sie mit viel kürzeren Schlüssellängen als die ursprünglichen 500 Zeichen zu verwenden.

Siehe auch

Referenzen und Notizen

Literaturverzeichnis

Carter, Frank, Bletchley Park Technical Papers: Koloss und das Brechen der Lorenz-Chiffre (PDF) , abgerufen am 28. Januar 2011 CS1-Wartung: entmutigter Parameter ( Link )
Churchhouse, Robert (2002), Codes und Chiffren: Julius Caesar, das Rätsel und das Internet , Cambridge: Cambridge University Press, ISBN 978-0-521-00890-7
Copeland, Jack (2006), "Turingery", in Copeland, B. Jack (Hrsg.), Koloss: Die Geheimnisse der Codebreaking-Computer von Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-284055-4
Good, Jack (1993), "Enigma and Fish", in Hinsley, FH ; Stripp, Alan (Hrsg.), Codebreakers: Die Insidergeschichte von Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
Gut, Jack ; Michie, Donald ; Timms, Geoffrey (1945), Allgemeiner Bericht über Thunfisch: Mit Schwerpunkt auf statistischen Methoden , UK Public Record Office HW 25/4 und HW 25/5 , abgerufen am 15. September 2010 CS1-Wartung: entmutigter Parameter ( Link ) Diese Version ist eine Faksimile-Kopie, aber es gibt eine Abschrift eines Großteils dieses Dokuments im PDF-Format unter: Sale, Tony (2001), Teil des von Tony Sale formatierten "General Report on Tunny", der Newmanry History (PDF) , abgerufen am 20. September 2010 CS1-Wartung: entmutigter Parameter ( Link ) und ein Web-Transkript von Teil 1 unter: Ellsbury, Graham, Allgemeiner Bericht über Thunfisch mit Schwerpunkt auf statistischen Methoden , abgerufen am 3. November 2010 CS1-Wartung: entmutigter Parameter ( Link )
Government Code and Cypher School (1944), The Bletchley Park 1944 Kryptografisches Wörterbuch, formatiert von Tony Sale (PDF) , abgerufen am 7. Oktober 2010 CS1-Wartung: entmutigter Parameter ( Link )
Hodges, Andrew (1992), Alan Turing: Das Rätsel , London: Vintage , ISBN 978-0-09-911641-7
Newman, Max (um 1944), "Anhang 7: Δ- Methode", in Copeland, B. Jack (Hrsg.), Koloss: Die Geheimnisse der Codebreaking-Computer von Bletchley Park , Oxford: Oxford University Press, ISBN ${\ displaystyle \ chi}$ 978-0-19-284055-4
Tutte, William T. (2006), "Meine Arbeit im Bletchley Park", in Copeland, B Jack (Hrsg.), Koloss: Die Geheimnisse der Codebreaking-Computer im Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-284055-4 CS1-Wartung: entmutigter Parameter ( Link )
Tutte, WT (19. Juni 1998), Fish and I (PDF) , archiviert vom Original (PDF) am 10. Juli 2007 , abgerufen am 7. Oktober 2010 CS1-Wartung: entmutigter Parameter ( Link ) Abschrift eines Vortrags von Prof. Tutte an der University of Waterloo

Languages

In other projects