Kryptoanalyse der Lorenz-Chiffre - Cryptanalysis of the Lorenz cipher

Zeitleiste der wichtigsten Ereignisse
Zeit Veranstaltung
September 1939 In Europa bricht Krieg aus .
Zweite Hälfte 1940 Erste Nicht- Morse- Übertragungen abgefangen.
Juni 1941 Erste experimentelle SZ40 Tunny- Verbindung begann mit alphabetischer Anzeige .
August 1941 Zwei lange Nachrichten in der Tiefe ergaben 3700 Zeichen des Schlüssels .
Januar 1942
Juli 1942
Oktober 1942
November 1942 "1 + 2 Einbruch" erfunden von Bill Tutte .
Februar 1943 Komplexeres SZ42A eingeführt.
Mai 1943 Heath Robinson lieferte.
Juni 1943 Newmanry gegründet.
Dezember 1943 Colossus I , der in Dollis Hill arbeitet, bevor er an Bletchley Park geliefert wird.
Februar 1944 Erster Einsatz von Colossus I für einen echten Job.
März 1944 Vier Kolosse (Mark 2) bestellt.
April 1944 Bestellung für weitere Kolosse auf 12 gestiegen.
Juni 1944
August 1944 Nockeneinstellungen an allen Lorenz-Rädern wurden täglich geändert.
Mai 1945

Die Kryptoanalyse der Lorenz-Chiffre war der Prozess, der es den Briten ermöglichte, während des Zweiten Weltkriegs hochrangige Nachrichten der deutschen Armee zu lesen . Die British Government Code and Cypher School (GC&CS) in Bletchley Park entschlüsselte viele Kommunikationen zwischen dem Oberkommando der Wehrmacht (OKW) in Berlin und ihren Armeekommandos im gesamten besetzten Europa, von denen einige mit "Adolf Hitler, Führer" signiert waren. Dabei handelte es sich um abgefangene Nicht- Morse- Funksendungen, die von den Lorenz SZ- Fernschreiber- Rotorstromchiffrenaufsätzen verschlüsselt worden waren . Die Entschlüsselung dieses Datenverkehrs wurde zu einer wichtigen Quelle der „ Ultra “ -Intelligenz , die maßgeblich zum Sieg der Alliierten beitrug.

Für ihre hochrangigen Geheimbotschaften verschlüsselten die deutschen Streitkräfte jedes Zeichen mit verschiedenen Online- Geheimschreiber- Stromchiffriermaschinen an beiden Enden einer Telegrafenverbindung mit dem 5-Bit International Telegraphy Alphabet No. 2 (ITA2). Später entdeckte man bei diesen Maschinen die Lorenz SZ (SZ für Schlüssel-Zusatz ) für das Heer, die Siemens und Halske T52 für die Luftwaffe und die Siemens T43, die wenig benutzt wurde und nie von den Alliierte.

Bletchley Parks Entschlüsselung von mit den Enigma-Maschinen verschlüsselten Nachrichten ergab, dass die Deutschen eines ihrer drahtlosen Fernschreiber-Übertragungssysteme "Sägefisch" (Sägefisch) nannten, was dazu führte, dass britische Kryptographen den verschlüsselten deutschen Funktelegrafieverkehr als " Fisch " bezeichneten. " Tunny " (Thunfisch) war der Name des ersten Nicht-Morse-Links und wurde später für die Chiffriermaschinen und ihren Verkehr verwendet.

Wie bei der völlig separaten Kryptoanalyse des Enigma waren es deutsche Betriebsmängel, die die erste Diagnose des Systems und einen Weg zur Entschlüsselung ermöglichten. Im Gegensatz zu Enigma gelangte bis zum Ende des Krieges in Europa keine physische Maschine in die Hände der Alliierten , lange nachdem die umfassende Entschlüsselung etabliert war. Die Probleme bei der Entschlüsselung von Tunny-Nachrichten führten zur Entwicklung von " Colossus ", dem ersten elektronischen, programmierbaren Digitalcomputer der Welt, von dem bis Kriegsende zehn davon im Einsatz waren und bis zu diesem Zeitpunkt etwa 90% der ausgewählten Tunny-Nachrichten entschlüsselt waren im Bletchley-Park.

Albert W. Small, ein Kryptoanalytiker des US Army Signal Corps, der nach Bletchley Park abgeordnet wurde und an Tunny arbeitete, sagte in seinem Bericht vom Dezember 1944 an Arlington Hall :

Die täglichen Lösungen von Fischnachrichten bei GC&CS spiegeln den Hintergrund britischer mathematischer Genialität, hervorragender Ingenieurskunst und solidem gesunden Menschenverstand wider. Jeder dieser Faktoren war ein notwendiger Faktor. Jede hätte zum Nachteil der Lösungen über- oder unterbetont werden können; eine bemerkenswerte Tatsache ist, dass die Verschmelzung der Elemente anscheinend in perfektem Verhältnis erfolgt ist. Das Ergebnis ist ein herausragender Beitrag zur kryptanalytischen Wissenschaft.

Die deutschen Tunny-Maschinen

Die Lorenz SZ-Maschinen hatten jeweils 12 Räder mit einer unterschiedlichen Anzahl von Nocken (oder "Pins").
OKW/ Chi
Radname
EIN B C D E F g h ich J K L
BP Rad
Name
1 2 3 4 5 37 61 1 2 3 4 5
Anzahl
Nocken (Stifte)
43 47 51 53 59 37 61 41 31 29 26 23

Die Lorenz SZ-Chiffre-Anhänge implementierten eine Vernam- Stream-Chiffre , die eine komplexe Anordnung von zwölf Rädern verwendet, die eine kryptographisch sichere Pseudozufallszahl als Schlüsselstream liefern sollten . Der Schlüsselstrom wurde mit dem Klartext kombiniert , um auf der Sendeseite unter Verwendung der Exklusiv-Oder- Funktion (XOR) den Chiffretext zu erzeugen . Auf der Empfangsseite erzeugte eine identisch konfigurierte Maschine denselben Schlüsselstrom, der mit dem Chiffretext kombiniert wurde, um den Klartext zu erzeugen, dh das System implementierte einen symmetrischen Schlüsselalgorithmus .

Der Schlüsselstrom wurde von zehn der zwölf Räder erzeugt. Dies war ein Produkt der XOR-Verknüpfung des 5-Bit-Zeichens, das von den rechten fünf Rädern, den chi ( ) Rädern, und den linken fünf, den psi ( ) Rädern, erzeugt wurde. Die Chi- Räder bewegten sich für jedes eingehende Geheimtextzeichen immer auf eine Position, die Psi- Räder jedoch nicht.

Nocken auf den Rädern 9 und 10 zeigen ihre angehobene (aktiv) und abgesenkte (inaktive) Position. Ein aktiver Nocken hat den Wert eines Bits umgekehrt ( x und x ).

Die beiden mittleren mu ( ) oder "Motor"-Räder bestimmten, ob sich die Psi- Räder mit einem neuen Zeichen drehten oder nicht . Nachdem jeder Buchstabe verschlüsselt war, bewegten sich entweder alle fünf Psi-Räder weiter, oder sie blieben stehen und derselbe Buchstabe des Psi-Schlüssels wurde erneut verwendet. Wie die Chi- Räder bewegte sich das 61- Rad nach jedem Zeichen weiter. Als 61 die Nocke in der aktiven Position hatte und so x (vor der Bewegung) erzeugte, bewegte sich 37 einmal weiter: als die Nocke in der inaktiven Position war (vor der Bewegung) 37 und die Psi- Räder blieben still. Bei allen außer den frühesten Maschinen gab es einen zusätzlichen Faktor, der das Weiterbewegen der Psi- Räder beeinflusste oder nicht . Diese waren von vier verschiedenen Typen und wurden in Bletchley Park "Limitations" genannt. Alle betrafen einen Aspekt der vorherigen Positionen der Räder der Maschine.

Die Zahl der Nocken auf dem Satz von zwölf Rädern der SZ42 Maschinen betrugen 501 und waren Co-Prime miteinander, eine extrem lange Zeit vor der Tastenfolge geben wiederholt. Jeder Nocken konnte sich entweder in einer angehobenen Position befinden, in diesem Fall trug er x zur Logik des Systems bei, indem er den Wert eines Bits umkehrte, oder in der abgesenkten Position, in diesem Fall erzeugte er . Die insgesamt mögliche Anzahl von Mustern angehobener Nocken betrug 2 501, was eine astronomisch große Zahl ist. In der Praxis befand sich jedoch etwa die Hälfte der Nocken an jedem Rad in der angehobenen Position. Später erkannten die Deutschen, dass es zu x s und s, einer kryptografischen Schwäche, kommen würde, wenn die Anzahl der angehobenen Cams nicht sehr nahe bei 50% lag .

Der Prozess, um herauszufinden, welche der 501 Nocken in der angehobenen Position waren, wurde in Bletchley Park als "Radbrechen" bezeichnet. Das Ableiten der Startpositionen der Räder für ein bestimmtes Getriebe wurde als "Radeinstellung" oder einfach als "Einstellung" bezeichnet. Die Tatsache, dass sich die Psi- Räder alle zusammen bewegten, aber nicht bei jedem Eingabezeichen, war eine große Schwäche der Maschinen, die zum britischen kryptanalytischen Erfolg beigetragen haben.

Eine Lorenz SZ42 Chiffriermaschine mit entfernten Abdeckungen im National Museum of Computing im Bletchley Park

Sichere Telegrafie

Die elektromechanische Telegrafie wurde in den 1830er und 1840er Jahren, lange vor der Telefonie , entwickelt und zur Zeit des Zweiten Weltkriegs weltweit betrieben . Ein umfangreiches Kabelsystem verband Standorte innerhalb und zwischen Ländern mit einer Standardspannung von -80 V für ein "Zeichen" und +80 V für ein "Leerzeichen". Wo die Kabelübertragung unpraktisch oder unbequem wurde, wie zum Beispiel bei mobilen Bundesheerverbänden, kam die Funkübertragung zum Einsatz.

Fernschreiber an jedem Ende des Stromkreises bestanden aus einer Tastatur und einem Druckmechanismus und sehr oft einem perforierten Papierbandlese- und Stanzmechanismus mit fünf Löchern . Bei Online- Nutzung führte das Drücken einer Buchstabentaste auf der Sendeseite dazu, dass das entsprechende Zeichen auf der Empfangsseite gedruckt wurde. Üblicherweise beinhaltete das Kommunikationssystem jedoch den übertragenden Operator, der einen Satz von Nachrichten offline vorbereitete, indem er sie auf ein Papierband stanzte und dann nur für die Übertragung der auf dem Band aufgezeichneten Nachrichten online ging. Das System würde typischerweise etwa zehn Zeichen pro Sekunde senden und damit die Leitung oder den Funkkanal kürzer belegen als beim Online-Eingeben.

Die Zeichen der Nachricht wurden durch die Codes des International Telegraphy Alphabet No. 2 ( ITA2 ) repräsentiert . Das Übertragungsmedium, entweder Draht oder Funk, verwendet asynchrone serielle Kommunikation, wobei jedes Zeichen durch einen Startimpuls (Leerzeichen), 5 Datenimpulse und 1½ Stoppimpulse (Markierungsimpulse) signalisiert wird. In Bletchley Park wurden Markierungsimpulse durch x("Kreuz") und Raumimpulse durch ("Punkt") gekennzeichnet. Der Buchstabe "H" würde beispielsweise als codiert werden ••x•x.

Binärer Fernschreibercode ( ITA2 ), wie er in Bletchley Park verwendet wird, in Reflexionsreihenfolge angeordnet , wobei sich jede Reihe von ihren Nachbarn nur um ein Bit unterscheidet.
Impulsmuster Mark = x , Leerzeichen = Binär Buchstabenverschiebung Figurenverschiebung BP 'verschiebungslose' Interpretation
••.••• 00000 Null Null /
••.x•• 00100 Raum Raum 9
••.x•x 00101 h # h
••.••x 00001 T 5 T
••.•xx 00011 Ö 9 Ö
••.xxx 00111 m . m
••.xx• 00110 n , n
••.•x• 00010 CR CR 3
•x.•x• 01010 R 4 R
•x.xx• 01110 C : C
•x.xxx 01111 V ; V
•x.•xx 01011 g & g
•x.••x 01001 L ) L
•xx•x 01101 P 0 P
•xx•• 01100 ich 8 ich
•x.••• 01000 LF LF 4
xx.••• 11000 EIN - EIN
xx.x•• 11100 U 7 U
xx.x•x 11101 Q 1 Q
xx.••x 11001 W 2 W
xx.•xx 11011 BILDER + oder 5
xx.xxx 11111 LTRS - oder 8
xx.xx• 11110 K ( K
xx.•x• 11010 J Glocke J
x•.•x• 10010 D WRU D
x•.xx• 10110 F ! F
x•.xxx 10111 x / x
x•.•xx 10011 B ? B
x•.••x 10001 Z " Z
x•.x•x 10101 Ja 6 Ja
x•.x•• 10100 S ' S
x•.••• 10000 E 3 E

Die Zeichenverschiebungs- (FIGS) und Buchstabenverschiebungs-(LETRS)-Zeichen legten fest, wie das empfangende Ende die Zeichenfolge bis zum nächsten Verschiebungszeichen interpretierte. Wegen der Gefahr, dass ein Shift-Zeichen beschädigt wird, geben einige Operatoren ein Paar von Shift-Zeichen ein, wenn sie von Buchstaben zu Zahlen oder umgekehrt wechseln . Sie würden also 55M88 eingeben, um einen Punkt darzustellen. Eine solche Zeichenverdoppelung war für die statistische Kryptoanalyse von Bletchley Park sehr hilfreich. Nach der Verschlüsselung hatten Umschaltzeichen keine besondere Bedeutung.

Die Übertragungsgeschwindigkeit einer Funktelegraphennachricht war drei- oder viermal höher als die des Morsecodes, und ein menschlicher Zuhörer konnte sie nicht interpretieren. Ein normaler Fernschreiber würde jedoch den Text der Nachricht erzeugen. Der Lorenz-Chiffre-Anhang änderte den Klartext der Nachricht in einen Geheimtext , der für diejenigen ohne identische, identisch eingerichtete Maschine nicht interpretierbar war. Dies war die Herausforderung für die Codebrecher von Bletchley Park.

Abfangen

Das Abfangen von Tunny-Übertragungen bereitete erhebliche Probleme. Da die Sender direktional waren, waren die meisten Signale bei Empfängern in Großbritannien ziemlich schwach. Darüber hinaus wurden für diese Übertragungen etwa 25 verschiedene Frequenzen verwendet, und die Frequenz wurde manchmal zwischendurch geändert. Nach der ersten Entdeckung der Nicht-Morse-Signale im Jahr 1940 wurde auf einem Hügel der Ivy Farm in Knockholt in Kent eine Funkstation namens Foreign Office Research and Development Establishment eingerichtet , um diesen Verkehr abzufangen. Das Zentrum wurde von Harold Kenworthy geleitet, hatte 30 Empfangsgeräte und beschäftigte etwa 600 Mitarbeiter. Es wurde Anfang 1943 voll funktionsfähig.

Ein 12 Millimeter breites Band, hergestellt von einem Undulator, ähnlich denen, die während des Zweiten Weltkriegs für den abgefangenen drahtlosen „Tunny“-Telegrafenverkehr in Knockholt verwendet wurden, zur Übersetzung in ITA2-Zeichen, die an Bletchley Park gesendet werden

Da ein einzelnes vergessenes oder beschädigtes Zeichen eine Entschlüsselung unmöglich machen konnte, war höchste Genauigkeit erforderlich. Die Undulator-Technologie zur Aufzeichnung der Impulse wurde ursprünglich für Hochgeschwindigkeits-Morse entwickelt. Es erzeugte eine sichtbare Aufzeichnung der Impulse auf schmalem Papierband. Dies wurde dann von Leuten gelesen, die als "Slipreader" beschäftigt waren und die Höhen und Tiefen als Markierungen und Leerzeichen von ITA2-Zeichen interpretierten. Perforiertes Papierband wurde dann für die telegrafische Übertragung nach Bletchley Park hergestellt, wo es ausgestanzt wurde.

Die Vernam-Chiffre

Die von den Lorenz SZ-Maschinen implementierte Vernam-Chiffre verwendet die boolesche Funktion "exklusives Oder" (XOR) , die durch ⊕ symbolisiert und als "A oder B, aber nicht beides" verbalisiert wird. Dies wird durch die folgende Wahrheitstabelle dargestellt , wobei x für "wahr" steht und für "falsch" steht.

EINGANG AUSGANG
EIN B A ⊕ B
x x
x x
x x

Andere Bezeichnungen für diese Funktion sind: exklusive Disjunktion, ungleich (NEQ) und Modulo- 2-Addition (ohne "Carry") und Subtraktion (ohne "Borrow"). Modulo 2 Addition und Subtraktion sind identisch. Einige Beschreibungen der Tunny-Entschlüsselung beziehen sich auf Addition und andere auf Differenzierung, dh Subtraktion, aber sie bedeuten dasselbe. Der XOR-Operator ist sowohl assoziativ als auch kommutativ .

Reziprozität ist ein wünschenswertes Merkmal einer Maschinenverschlüsselung, so dass dieselbe Maschine mit denselben Einstellungen entweder zum Verschlüsseln oder zum Entschlüsseln verwendet werden kann. Die Vernam-Chiffre erreicht dies, da das Kombinieren des Stroms von Klartextzeichen mit dem Schlüsselstrom den Chiffretext erzeugt und das Kombinieren desselben Schlüssels mit dem Chiffretext den Klartext regeneriert.

Symbolisch:

KlartextSchlüssel = Geheimtext

und

GeheimtextSchlüssel = Klartext

Die ursprüngliche Idee von Vernam bestand darin, die herkömmliche Telegrafiepraxis zu verwenden, mit einem Papierband des Klartextes kombiniert mit einem Papierband des Schlüssels am sendenden Ende und einem identischen Schlüsselband kombiniert mit dem Geheimtextsignal am empfangenden Ende. Jedes Paar von Schlüsselbändern wäre einzigartig (ein einmaliges Band ), aber die Erzeugung und Verteilung solcher Bänder bereitete erhebliche praktische Schwierigkeiten. In den 1920er Jahren erfanden vier Männer in verschiedenen Ländern Rotor-Vernam-Chiffriermaschinen, um einen Schlüsselstrom anstelle eines Schlüsselbandes zu erzeugen. Der Lorenz SZ40/42 war einer davon.

Sicherheitsfunktionen

Eine typische Verteilung von Buchstaben in englischsprachigem Text. Eine unzureichende Verschlüsselung kann die uneinheitliche Natur der Verteilung möglicherweise nicht ausreichend maskieren. Diese Eigenschaft wurde bei der Kryptoanalyse der Lorenz-Chiffre ausgenutzt, indem ein Teil des Schlüssels geschwächt wurde.

Eine monoalphabetische Substitutions-Chiffre wie die Caesar-Chiffre kann bei einer angemessenen Menge an Geheimtext leicht gebrochen werden. Dies wird durch eine Häufigkeitsanalyse der verschiedenen Buchstaben des Geheimtextes und den Vergleich des Ergebnisses mit der bekannten Buchstabenhäufigkeitsverteilung des Klartextes erreicht.

Bei einer polyalphabetischen Chiffre gibt es für jedes nachfolgende Zeichen ein anderes Substitutionsalphabet. Eine Frequenzanalyse zeigt also eine annähernd gleichmäßige Verteilung , wie sie beispielsweise von einem (Pseudo-)Zufallszahlengenerator erhalten wird . Da sich jedoch ein Satz Lorenzräder mit jedem Zeichen drehte und der andere nicht, verschleierte die Maschine das Muster nicht durch die Verwendung benachbarter Zeichen im deutschen Klartext. Alan Turing entdeckte diese Schwäche und erfand die unten beschriebene Differenzierungstechnik, um sie auszunutzen.

Das Muster welcher der Nocken in der angehobenen Position und welche in der abgesenkten Position wurde täglich an den Motorrädern ( 37 und 61 ) geändert . Die Chi- Rad-Nockenmuster wurden zunächst monatlich geändert. Die Psi -Radmuster wurden bis Oktober 1942 vierteljährlich geändert, als die Häufigkeit auf monatlich und dann am 1. August 1944 auf täglich erhöht wurde, als die Häufigkeit des Wechsels der Chi -Radmuster ebenfalls auf täglich geändert wurde.

Die Anzahl der Startpositionen der Räder betrug 43 × 47 × 51 × 53 × 59 × 37 × 61 × 41 × 31 × 29 × 26 × 23, was ungefähr 1,6 × 10 19 (16 Milliarden Milliarden) entspricht, eine viel zu große Zahl für Kryptoanalytiker einen erschöpfenden „ Brute-Force-Angriff “ zu versuchen . Manchmal missachteten die Lorenz-Operatoren Anweisungen und es wurden zwei Nachrichten mit den gleichen Startpositionen gesendet, ein Phänomen, das als "Tiefe" bezeichnet wird . Die Methode, mit der der sendende Operator dem empfangenden Operator die Radeinstellungen mitteilte, die er für die Nachricht, die er senden wollte, gewählt hatte, wurde in Bletchley Park als "Indikator" bezeichnet .

Im August 1942 wurden die formelhaften Anfänge der Botschaften, die für Kryptoanalytiker nützlich waren, durch einen irrelevanten Text ersetzt, der es etwas schwieriger machte, die wahre Botschaft zu identifizieren. Dieses neue Material wurde genannt quatsch (deutsch für „Unsinn“) in Bletchley Park.

Während der Phase der Versuchsübertragungen bestand der Indikator aus zwölf deutschen Vornamen, deren Anfangsbuchstaben die Position anzeigten, in die die Bediener die zwölf Räder drehten. Es zeigte nicht nur an, wann zwei Getriebe vollständig in der Tiefe waren, sondern ermöglichte auch die Identifizierung von Teiltiefen, bei denen sich zwei Indikatoren nur in einer oder zwei Radpositionen unterschieden. Ab Oktober 1942 änderte sich das Anzeigesystem dahingehend, dass der sendende Operator die unverschlüsselten Buchstaben QEP gefolgt von einer zweistelligen Nummer übermittelte. Diese Nummer wurde seriell einem Codebuch entnommen, das an beide Betreiber ausgegeben worden war und gab für jede QEP-Nummer die Einstellungen der zwölf Räder an. Die Bücher wurden ersetzt, wenn sie aufgebraucht waren, aber zwischen den Ersetzungen konnten vollständige Tiefen durch die Wiederverwendung einer QEP-Nummer auf einem bestimmten Tunny-Link identifiziert werden.

Diagnose

Notation
Letters können Zeichenströme, einzelne 5-Bit-Zeichen oder, falls tiefgestellt, einzelne Zeichenbits darstellen
P Klartext
K Schlüssel – die Zeichenfolge XOR 'ed (hinzugefügt)
zum Klartext, um den Geheimtext zu erhalten
χ Chi- Komponente des Schlüssels
ψ Psi- Komponente des Schlüssels
' Extended psi – die tatsächliche Folge von Zeichen,
die von den Psi- Rädern hinzugefügt werden , einschließlich derer,
wenn sie nicht vorrücken
Z Geheimtext
D de- chi — der Chiffretext, bei dem die Chi-
Komponente des Schlüssels entfernt wurde
Δ jeder der oben genannten XOR'ed mit
seinem Nachfolger-Charakter oder Bit
die XOR-Operation

Der erste Schritt beim Entschlüsseln einer neuen Chiffre besteht darin, die Logik der Prozesse der Verschlüsselung und Entschlüsselung zu diagnostizieren. Bei einer Maschinenchiffre wie Tunny ging es darum, den logischen Aufbau und damit die Funktionsweise der Maschine zu ermitteln. Dies gelang ohne den Vorteil, eine Maschine zu sehen – was erst 1945 geschah, kurz vor dem Sieg der Alliierten in Europa. Das Chiffriersystem war sehr gut darin sicherzustellen, dass der Geheimtext Z keine statistischen, periodischen oder linguistischen Merkmale enthielt, um ihn von zufällig zu unterscheiden. Dies galt jedoch nicht für K , χ , ψ' und D , was die Schwäche war, die dazu führte, dass Tunny-Schlüssel gelöst werden konnten.

Während der Versuchsperiode der Tunny-Übertragungen, als das Zwölf-Buchstaben-Indikatorsystem verwendet wurde, studierte John Tiltman , Bletchley Parks Veteran und bemerkenswert begabter Kryptoanalytiker, die Tunny-Chiffretexte und stellte fest, dass sie eine Vernam-Chiffre verwendeten.

Wenn zwei Übertragungen ( a und b ) denselben Schlüssel verwenden, dh sie sind in der Tiefe, wird durch ihre Kombination der Effekt des Schlüssels eliminiert. Nennen wir die beiden Geheimtexte Za und Zb , den Schlüssel K und die beiden Klartexte Pa und Pb . Wir haben dann:

Za ⊕ Zb = Pa ⊕ Pb

Wenn die beiden Klartexte ausgearbeitet werden können, kann der Schlüssel aus einem der beiden Geheimtext-Klartext-Paare wiederhergestellt werden, zB:

Za ⊕ Pa = K oder
Zb ⊕ Pb = K

Am 31. August 1941 gingen zwei lange Nachrichten mit dem gleichen Kennzeichen HQIBPEXEZMUG ein. Die ersten sieben Zeichen dieser beiden Geheimtexte waren gleich, aber die zweite Nachricht war kürzer. Die ersten 15 Zeichen der beiden Nachrichten lauteten wie folgt (in Bletchley Park-Interpretation):

Za JSH4N ZYZY4 GLFRG
Zum Beispiel JSH4N ZYMFS /884I
Za ⊕ Zb ///// //FOU GFL3M

John Tiltman versuchte verschiedene wahrscheinliche Klartextstücke, zB ein "cribs" , gegen die Za ⊕ Zb- Zeichenfolge und stellte fest, dass die erste Klartextnachricht mit dem deutschen Wort SPRUCHNUMMER (Nachrichtennummer) begann. Im zweiten Klartext hatte der Betreiber die gebräuchliche Abkürzung NR für NUMMER verwendet . Die zweite Nachricht enthielt mehr Abkürzungen, und die Interpunktion war manchmal anders. Dies ermöglichte Tiltman, über einen Zeitraum von zehn Tagen den Klartext beider Nachrichten als eine Folge von Klartextzeichen, die in Pa entdeckt wurden, auszuarbeiten , die dann gegen Pb und umgekehrt versucht werden konnten . Dies wiederum ergab fast 4000 Schlüsselzeichen.

Mitglieder der Forschungsabteilung arbeiteten an diesem Schlüssel, um eine mathematische Beschreibung des Schlüsselgenerierungsprozesses abzuleiten, jedoch ohne Erfolg. Bill Tutte trat der Sektion im Oktober 1941 bei und erhielt die Aufgabe. Er hatte Chemie und Mathematik am Trinity College in Cambridge studiert, bevor er nach Bletchley Park rekrutiert wurde. In seiner Ausbildung war ihm die Kasiski-Prüfungstechnik beigebracht worden, einen Schlüssel auf kariertem Papier mit einer neuen Reihe nach einer definierten Anzahl von Zeichen zu schreiben, die im Verdacht stand, die Wiederholungshäufigkeit des Schlüssels zu sein. Wenn diese Zahl richtig wäre, würden die Spalten der Matrix mehr Wiederholungen von Zeichenfolgen aufweisen als der Zufall allein.

Tutte hielt es für möglich, dass es sich lohnen könnte, diese Technik nicht auf die gesamten Buchstaben des Schlüssels anzuwenden, die wahrscheinlich eine lange Wiederholungshäufigkeit haben, sondern auf die Sequenz, die aus nur einem Impuls (Bit) gebildet wurde. aus jedem Buchstaben, mit der Begründung, dass " der Teil kryptographisch einfacher sein könnte als das Ganze ". Da die Tunny-Indikatoren 25 Buchstaben (ohne J) für 11 der Positionen, aber nur 23 Buchstaben für die zwölfte verwendeten, probierte er Kasiskis Technik beim ersten Impuls der Schlüsselzeichen mit einer Wiederholung von 25 × 23 = 575 aus nicht viele Wiederholungen in den Spalten, aber Tutte beobachtete das Phänomen auf einer Diagonale. Er versuchte es daher erneut mit 574, was sich in den Spalten wiederholte. Als er erkannte, dass die Primfaktoren dieser Zahl 2, 7 und 41 sind, versuchte er es erneut mit einer Periode von 41 und " erhielt ein Rechteck aus Punkten und Kreuzen, das voller Wiederholungen war ".

Es war jedoch klar, dass die Abfolge der ersten Impulse komplizierter war als bei einem einzelnen Rad mit 41 Positionen. Tutte nannte diese Komponente des Schlüssels χ 1 ( chi ). Er stellte sich vor, dass es eine weitere Komponente gab, die damit XOR-verknüpft war, die sich nicht immer mit jedem neuen Zeichen änderte, und dass dies das Produkt eines Rades war, das er ψ 1 ( psi ) nannte. Dasselbe galt für jeden der fünf Impulse – hier durch Indizes gekennzeichnet. Für ein einzelnes Zeichen bestand der Schlüssel K also aus zwei Komponenten:

K = χψ .

Die tatsächliche Folge von Zeichen, die von den Psi- Rädern hinzugefügt wurden , einschließlich derer, wenn sie nicht vorrücken, wurde als erweitertes Psi bezeichnet und durch ψ′ symbolisiert.

K = χψ′ .

Tuttes Ableitung der ψ- Komponente wurde durch die Tatsache ermöglicht, dass auf Punkte eher Punkte folgten als nicht und auf Kreuze eher Kreuze folgten als nicht. Dies war das Produkt einer Schwäche in der deutschen Tasteneinstellung, die sie später beendeten. Nachdem Tutte diesen Durchbruch geschafft hatte, schloss sich der Rest der Forschungsabteilung an, um die anderen Impulse zu studieren, und es wurde festgestellt, dass sich die fünf ψ- Räder alle unter der Kontrolle von zwei μ- Rädern ( mu oder "Motor") zusammen bewegten .

Die Funktionsfähigkeit der Tunny-Maschine auf diese Weise zu diagnostizieren, war eine wahrhaft bemerkenswerte kryptanalytische Leistung und wurde, als Tutte im Oktober 2001 zum Offizier des Order of Canada ernannt wurde, als „ eine der größten intellektuellen Leistungen des Zweiten Weltkriegs “ bezeichnet.

Turingerie

Im Juli 1942 verbrachte Alan Turing einige Wochen in der Forschungsabteilung. Er hatte sich für das Problem interessiert, Tunny aus den Schlüsseln zu brechen, die er aus der Tiefe geholt hatte. Im Juli entwickelte er eine Methode, um die Nockeneinstellungen ("Radbruch") aus einer Schlüssellänge abzuleiten. Es wurde als "Turingery" bekannt (von Peter Ericsson, Peter Hilton und Donald Michie spielerisch "Turingismus" genannt ) und führte die wichtige Methode des "Differencing" ein, auf der ein Großteil des Rests der Lösung von Tunny-Schlüsseln ohne Tiefen basierte .

Differenzierung

Es wurde nach einem Verfahren gesucht, das den Chiffretext oder Schlüssel manipulieren würde, um eine Häufigkeitsverteilung von Zeichen zu erzeugen, die von der Einheitlichkeit abwich, die der Verschlüsselungsprozess erreichen wollte. Turing stellte fest, dass die XOR-Kombination der Werte aufeinanderfolgender (benachbarter) Zeichen in einem Chiffretext- oder Schlüsselstrom alle Abweichungen von einer gleichmäßigen Verteilung hervorhebt. Der resultierende Strom wurde Differenz genannt (symbolisiert durch den griechischen Buchstaben "Delta" Δ ), weil XOR dasselbe ist wie die Modulo-2-Subtraktion. Für einen Zeichenstrom S wurde die Differenz ΔS wie folgt erhalten, wobei die Unterstreichung das folgende Zeichen angibt:

ΔS = S ⊕ S

Der Strom S kann Chiffretext sein Z , Klartext P , Schlüssel K oder einer seiner beiden Komponenten & khgr; und ψ . Die Beziehung zwischen diesen Elementen gilt auch dann, wenn sie unterschieden werden. Zum Beispiel sowie:

K = χψ

Es ist so:

ΔK = Δ χ ⊕ Δ ψ

Ähnlich für den Geheimtext, den Klartext und die Schlüsselkomponenten:

ΔZ = ΔP ⊕ Δ χ ⊕ Δ ψ

So:

ΔP = ΔZ ⊕ Δ χ ⊕ Δ ψ

Der Grund dafür, dass die Differenzierung einen Weg in Tunny eröffnete, war, dass die Häufigkeitsverteilung von Zeichen im Geheimtext zwar nicht von einem zufälligen Strom unterschieden werden konnte, dies jedoch nicht für eine Version des Geheimtexts galt, aus der das chi- Element des Schlüssels stammte Wurde entfernt. Dies liegt daran, wo der Klartext ein sich wiederholendes Charakter und die darin enthaltenen psi Räder bewegte sich nicht auf die differenced psi - Zeichen ( & Dgr; & psgr; ) würde die Nullzeichen sein ( ‚ / ‘ in Bletchley Park). Wenn mit einem beliebigen Zeichen XOR- verknüpft wird , hat dieses Zeichen keine Auswirkung, daher gilt unter diesen Umständen ΔK = Δ χ . Der Chiffretext, der durch das Entfernen der Chi- Komponente des Schlüssels modifiziert wurde, wurde in Bletchley Park als De- Chi D bezeichnet , und der Vorgang des Entfernens als "De- Chi- ing". Ähnliches gilt für das Entfernen der Psi- Komponente, die als "de- psi- ing" (oder "tiefes Seufzen", wenn es besonders schwierig war) bekannt war.

So das De- Delta Chi & Delta; D waren:

ΔD = ΔZ ⊕ Δ χ

Wiederholte Zeichen im Klartext waren sowohl wegen der Besonderheiten des Deutschen (EE, TT, LL und SS sind relativ häufig) häufiger, als auch weil Telegrafisten häufig die Ziffern- und Buchstabenverschiebung als Verlust in einer gewöhnlichen Telegrafenübertragung wiederholten könnte zu Kauderwelsch führen.

Um den Gesamtbericht über Tunny zu zitieren:

Turingery führte das Prinzip ein, dass der um eins differenzierte Schlüssel, der jetzt als bezeichnet wird , Informationen liefern kann, die mit einem gewöhnlichen Schlüssel nicht erhältlich sind. Dieses Δ- Prinzip sollte die grundlegende Grundlage für fast alle statistischen Methoden des Radbruchs und der Einstellung sein.

Auf jeden der Impulse der ITA2-codierten Zeichen wurde eine Differenzierung angewendet. Also für den ersten Impuls, der von den Rädern χ 1 und ψ 1 chiffriert wurde , unterschieden um eins:

& Dgr; K 1 = K 1K 1

Und zum zweiten Impuls:

& Dgr; K 2 = K 2K 2

Usw.

Die Periodizität der Chi- und Psi- Räder für jeden Impuls (41 bzw. 43 für den ersten Impuls) spiegelt sich auch im Muster von ΔK wider . Da die Psi- Räder jedoch nicht wie die Chi- Räder für jedes eingegebene Zeichen vorrückten , handelte es sich nicht einfach um eine Wiederholung des Musters alle 41 × 43 = 1763 Zeichen für ΔK 1 , sondern um eine komplexere Sequenz.

Turings Methode

Turings Methode, die Nockeneinstellungen der Räder aus einer aus einer Tiefe erhaltenen Schlüssellänge abzuleiten, beinhaltete einen iterativen Prozess. Angesichts der Tatsache, dass das Delta- psi- Zeichen im Durchschnitt die Hälfte der Zeit das Nullzeichen ' / ' war, hatte eine Annahme, dass ΔK  =  Δ χ eine Chance von 50 % war, richtig zu sein. Der Prozess begann damit, dass ein bestimmtes ΔK- Zeichen als das Δ χ für diese Position behandelt wurde. Das resultierende mutmaßliche Bitmuster von x und für jedes Chi- Rad wurde auf einem Blatt Papier aufgezeichnet, das so viele Spalten enthielt, wie der Schlüssel Zeichen enthielt, und fünf Reihen, die die fünf Impulse des Δ χ darstellten . Angesichts der Kenntnisse 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.

Ein Satz von fünf Blättern, eines für jedes der Chi- Räder, wurde ebenfalls vorbereitet. Diese enthielten eine Reihe von Spalten, die der Anzahl der Nocken für das entsprechende Chi- Rad entsprachen und wurden als "Käfig" bezeichnet. Der χ 3- Käfig hatte also 29 solcher Säulen. Aufeinanderfolgende 'Schätzungen' von Δ χ Werten erzeugten dann weitere mutmaßliche Nockenzustandswerte. Diese können früheren Annahmen entweder zustimmen oder nicht, und auf diesen Blättern wurde eine Zählung der Übereinstimmungen und Meinungsverschiedenheiten vorgenommen. Wo Meinungsverschiedenheiten die Vereinbarungen im Wesentlichen überwogen, wurde die Annahme getroffen, dass das Zeichen Δ ψ nicht das Nullzeichen ' / ' war, so dass die relevante Annahme verworfen wurde. Nach und nach wurden alle Nockeneinstellungen der Chi- Räder abgeleitet und daraus die psi- und Motorrad-Nockeneinstellungen.

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

Testbericht

Die Testery war die Abteilung in Bletchley Park, die den Großteil der Arbeit bei der Entschlüsselung von Tunny-Nachrichten ausführte. Bis Juli 1942 baute sich das Verkehrsaufkommen erheblich auf. Aus diesem Grund wurde eine neue Sektion eingerichtet, die von Ralph Tester geleitet wurde – daher der Name. Das Personal bestand hauptsächlich aus ehemaligen Mitgliedern der Forschungsabteilung, darunter Peter Ericsson, Peter Hilton , Denis Oswald und Jerry Roberts . Die Methoden des Testery waren fast ausschließlich manuell, sowohl vor als auch nach der Einführung automatisierter Methoden im Newmanry , um ihre Arbeit zu ergänzen und zu beschleunigen.

Die erste Phase der Arbeit des Testery lief von Juli bis Oktober, wobei die vorherrschende Methode der Entschlüsselung auf Tiefen und Teiltiefen basiert. Nach zehn Tagen wurde jedoch der formelhafte Beginn der Nachrichten durch unsinniges Quatsch ersetzt , was die Entschlüsselung erschwerte. Dieser Zeitraum war dennoch produktiv, auch wenn jede Entschlüsselung einige Zeit in Anspruch nahm. Im September schließlich wurde eine Tiefe erhalten, die es ermöglichte, Turings Methode des Radbrechens " Turingery " anzuwenden , was zur Möglichkeit führte, den aktuellen Verkehr zu lesen. Umfangreiche Daten über die statistischen Merkmale der Sprache der Botschaften wurden zusammengetragen und die Krippensammlung erweitert.

Ende Oktober 1942 wurde die ursprüngliche, experimentelle Tunny-Verbindung geschlossen und zwei neue Verbindungen (Kabeljau und Oktopus) eröffnet. Mit diesen und nachfolgenden Links wurde das 12-Buchstaben-Kennzeichensystem zur Angabe des Nachrichtenschlüssels durch das QEP-System ersetzt. Dies bedeutete, dass nur volle Tiefen erkannt werden konnten – von identischen QEP-Nummern – was zu einer erheblichen Reduzierung des entschlüsselten Datenverkehrs führte.

Als die Newmanry im Juni 1943 in Betrieb ging, änderte sich die Art der in der Testery durchgeführten Arbeit, da Entschlüsselungen und Radbrüche nicht mehr auf Tiefen angewiesen waren.

Britischer Thunfisch

Ein wiederaufgebauter britischer Tunny im National Museum of Computing , Bletchley Park . Es emulierte die Funktionen des Lorenz SZ40/42 und erzeugte gedruckten Klartext aus Geheimtexteingaben.

Die sogenannte "British Tunny Machine" war ein Gerät, das die Funktionen der SZ40/42-Maschinen exakt nachbildete. Es wurde verwendet, um den deutschen Klartext von einem Geheimtextband zu erzeugen, nachdem die Nockeneinstellungen bestimmt worden waren. Das funktionale Design wurde in Bletchley Park produziert, wo bis Kriegsende zehn Testery Tunnies im Einsatz waren. Es wurde im Labor von Tommy Flowers an der General Post Office Research Station in Dollis Hill von Gil Hayward , "Doc" Coombs , Bill Chandler und Sid Broadhurst entworfen und gebaut . Es wurde hauptsächlich aus elektromechanischen Standardgeräten der britischen Telefonzentrale wie Relais und Uniselektoren gebaut . Die Ein- und Ausgabe erfolgte mittels eines Fernschreibers mit Papierstreifenlesung und -lochung. Diese Maschinen wurden sowohl im Testery als auch später im Newmanry verwendet . Dorothy Du Boisson , Maschinenführerin und Mitglied des Women's Royal Naval Service (Wren), beschrieb das Abschließen der Einstellungen als das Betreiben einer altmodischen Telefonzentrale und dass sie dabei Stromschläge erhielt.

Als Flowers von Hayward eingeladen wurde, die erste britische Tunny-Maschine in Dollis Hill auszuprobieren, indem er den Standardtestsatz eintippte: "Jetzt ist es an der Zeit, dass alle guten Männer der Party zu Hilfe kommen", schätzte er die Funktion des Rotors sehr wurde eingerichtet, um die folgende Wordsworthian- Ausgabe bereitzustellen :

Eingang NOW IS THE TIME FOR ALL GOOD MEN TO COME TO THE AID OF THE PARTY
Ausgabe I WANDERED LONELY AS A CLOUD THAT FLOATS ON HIGH OER VALES AND H

Zu den britischen Tunnies wurden zusätzliche Funktionen hinzugefügt, um ihre Bedienung zu vereinfachen. Weitere Verbesserungen für die Versionen in der Newmanry verwendet gemacht wurden, die dritte Tunny de- herzustellen ist ausgestattet Chi - Bänder.

Newmanry

Die Newmanry war eine Sektion, die im Dezember 1942 unter Max Newman gegründet wurde, um die Möglichkeit zu untersuchen, die Arbeit der Testery durch die Automatisierung von Teilen des Prozesses der Entschlüsselung von Tunny-Nachrichten zu unterstützen. Newman hatte mit Gerry Morgan, dem Leiter der Forschungsabteilung, über Möglichkeiten zusammengearbeitet, Tunny zu brechen, als Bill Tutte im November 1942 mit der Idee des sogenannten "1+2-Einbruchs" an sie herantrat. Dies wurde als machbar erkannt, jedoch nur, wenn es automatisiert ist.

Newman erstellte eine funktionale Spezifikation dessen, was die " Heath Robinson "-Maschine werden sollte. Er rekrutierte die Post Office Research Station in Dollis Hill und Dr. CE Wynn-Williams vom Telecommunications Research Establishment (TRE) in Malvern, um seine Idee umzusetzen. Die Arbeiten an der Konstruktion begannen im Januar 1943 und die erste Maschine wurde im Juni ausgeliefert. Das Personal bestand zu dieser Zeit aus Newman, Donald Michie , Jack Good , zwei Ingenieuren und 16 Wrens. Am Ende des Krieges enthielt die Newmanry drei Robinson-Maschinen, zehn Colossus-Computer und eine Reihe britischer Tunnies. Das Personal bestand aus 26 Kryptografen, 28 Ingenieuren und 275 Wrens.

Die Automatisierung dieser Prozesse erforderte die Verarbeitung großer Mengen gestanzter Papierstreifen, auf denen die verschlüsselten Nachrichten empfangen wurden. Absolute Genauigkeit dieser Bänder und ihrer Transkription war von entscheidender Bedeutung, da ein einzelnes fehlerhaftes Zeichen eine große Menge an Arbeit ungültig machen oder verfälschen könnte. Jack Good führte die Maxime "Wenn es nicht überprüft wird, ist es falsch" ein.

Der "1+2 Einbruch"

WT Tutte entwickelte eine Möglichkeit, die Uneinheitlichkeit von Bigrammen (benachbarten Buchstaben) im deutschen Klartext unter Verwendung des differenzierten Geheimtextes und Schlüsselkomponenten auszunutzen. Seine Methode wurde "1+2-Einbruch" oder "Doppel-Delta-Angriff" genannt. Die Essenz dieser Methode bestand darin, die Anfangseinstellungen der Chi- Komponente des Schlüssels zu finden, indem alle Positionen seiner Kombination mit dem Geheimtext erschöpfend ausprobiert und nach Beweisen für die Uneinheitlichkeit gesucht wurden, die die Eigenschaften des ursprünglichen Klartexts widerspiegelte. Der Radbremsprozess musste die aktuellen Nockeneinstellungen erfolgreich erzeugt haben, damit die entsprechende Zeichenfolge der Chi- Räder erzeugt werden kann. Es war völlig undurchführbar, die 22 Millionen Zeichen aus allen fünf Chi- Rädern zu generieren , daher war es zunächst auf 41 × 31 = 1271 von den ersten beiden beschränkt.

Für jeden der fünf Impulse i gilt :

Z i = χ iψ i ⊕ P i

und daher

P i = Z iχ iψ i

für die ersten beiden Impulse:

(P 1 ⊕ P 2 ) = (Z 1 ⊕ Z 2 ) ⊕ ( χ 1χ 2 ) ⊕ ( ψ 1ψ 2 )

Die Berechnung eines putativen P 1 ⊕ P 2 auf diese Weise für jeden Startpunkt der Folge χ 1χ 2 würde x s und s mit langfristig einem größeren Anteil von s ergeben, wenn der richtige Startpunkt gewesen wäre Gebraucht. Tutte wusste jedoch, dass die Verwendung der differenzierten (∆)-Werte diesen Effekt verstärkte, da jedes wiederholte Zeichen im Klartext immer erzeugen würde , und in ähnlicher Weise würde ∆ ψ 1 ⊕ ∆ ψ 2 erzeugen, wenn sich die Psi- Räder nicht weiterbewegten, und ungefähr die Hälfte der Zeit, wenn sie es taten - insgesamt etwa 70 %.

Tutte analysierte einen entschlüsselten Geheimtext mit der differenzierten Version der obigen Funktion:

(∆Z 1 ⊕ ∆Z 2 ) ⊕ (∆ χ 1 ⊕ ∆ χ 2 ) ⊕ (∆ ψ 1 ⊕ ∆ ψ 2 )

und stellte fest, dass etwa 55 % der Zeit generiert wurden. Angesichts der Art des Beitrags der Psi- Räder war die Ausrichtung von Chi- Stream mit dem Geheimtext, der die höchste Anzahl von s von (∆Z 1 ⊕ ∆Z 2 ⊕ ∆ χ 1 ⊕ ∆ χ 2 ) ergab, diejenige, die war höchstwahrscheinlich richtig. Diese Technik könnte in jedem Paar von Impulsen angewendet werden und vorgesehen ist, um die Basis eines automatisierten Ansatz für die Gewinnung de- chi (D) eines chiffrierten Text, aus dem das psi - Komponente durch manuelle Methoden entfernt werden konnte.

Robinsons

Heath Robinson war die erste Maschine, die das 1+2-Verfahren von Tutte automatisierte. Den Namen erhielt es von den Wrens , die es betrieben, nach dem Karikaturisten William Heath Robinson , der immens komplizierte mechanische Geräte für einfache Aufgaben zeichnete, ähnlich dem amerikanischen Karikaturisten Rube Goldberg .

Die funktionale Spezifikation der Maschine wurde von Max Newman erstellt. Das wichtigste technische Design war die Arbeit von Frank Morrell an der Post Office Research Station in Dollis Hill im Norden Londons, während sein Kollege Tommy Flowers die "Combining Unit" entwarf. Dr. CE Wynn-Williams von der Telecommunications Research Establishment in Malvern produzierte die schnellen elektronischen Ventil- und Relaiszähler. Der Bau begann im Januar 1943, die Prototypmaschine war im Juni in Bletchley Park im Einsatz.

Die Hauptteile der Maschine waren:

  • ein Bandtransport- und Lesemechanismus (aufgrund seiner Ähnlichkeit mit einem umgedrehten Metallbettrahmen als "Bettgestell" bezeichnet), der die Schlüssel- und Nachrichtenbänder mit einer Geschwindigkeit von 1000 bis 2000 Zeichen pro Sekunde laufen ließ;
  • eine Kombinationseinheit, die die Logik des Tuttes-Verfahrens implementiert;
  • eine Zähleinheit, die die Anzahl der s gezählt und, wenn sie eine voreingestellte Summe überschreitet, angezeigt oder gedruckt hat.

Der Prototyp der Maschine war trotz einer Reihe schwerwiegender Mängel effektiv. Die meisten davon wurden bei der Entwicklung des sogenannten "Old Robinson" nach und nach überwunden.

Koloss

Ein Mark 2 Colossus-Computer. Die Wren-Operatoren sind (von links nach rechts) Dorothy Du Boisson und Elsie Booker. Das schräge Bedienfeld auf der linken Seite wurde verwendet, um die Nadelmuster auf der Lorenz einzustellen. Der Papierbandtransport "Bettgestell" befindet sich auf der rechten Seite.
1994 begann ein Team unter der Leitung von Tony Sale (rechts) mit der Rekonstruktion eines Mark 2-Koloss im Bletchley Park. Hier überwachen Sale und Phil Hayes 2006 die Lösung einer verschlüsselten Nachricht mit der fertigen Maschine.

Die Erfahrung von Tommy Flowers mit Heath Robinson und seine früheren, einzigartigen Erfahrungen mit thermionischen Ventilen (Vakuumröhren) führten ihn zu der Erkenntnis, dass eine bessere Maschine mit Elektronik hergestellt werden könnte. Anstatt den Schlüsselstrom von einem Lochstreifen zu lesen, könnte ein elektronisch erzeugter Schlüsselstrom eine viel schnellere und flexiblere Verarbeitung ermöglichen. Flowers' Vorschlag, dass dies mit einer vollständig elektronischen Maschine erreicht werden könnte, die zwischen ein und zweitausend Ventile enthalten würde, wurde sowohl im Telecommunications Research Establishment als auch in Bletchley Park mit Unglauben behandelt, da man dachte, dass es "zu unzuverlässig, nützliche Arbeit zu leisten". Er hatte jedoch die Unterstützung des Controllers of Research in Dollis Hill, W. Gordon Radley, und er setzte diese Ideen in der bemerkenswert kurzen Zeit von Colossus um , der weltweit ersten elektronischen, digitalen Rechenmaschine, die überhaupt programmierbar war zehn Monate. Dabei wurde er von seinen Kollegen der Post Research Station Dollis Hill unterstützt : Sidney Broadhurst, William Chandler, Allen Coombs und Harry Fensom .

Der Prototyp Mark 1 Colossus (Colossus I) mit seinen 1500 Ventilen wurde im Dezember 1943 in Dollis Hill in Betrieb genommen und war im Februar 1944 in Bletchley Park im Einsatz. Dieser verarbeitete die Nachricht mit 5000 Zeichen pro Sekunde unter Verwendung des Impulses aus dem Lesen des Bandes Ritzellöcher als Taktsignal fungieren . Es wurde schnell klar, dass dies ein großer Fortschritt in der Kryptoanalyse von Tunny war. Weitere Colossus-Maschinen wurden bestellt und die Bestellungen für weitere Robinsons storniert. Ein verbesserter Mark 2 Colossus (Colossus II) enthielt 2400 Ventile und arbeitete erstmals am 1. Juni 1944 in Bletchley Park, gerade rechtzeitig für die Landung am D-Day in der Normandie .

Die Hauptteile dieser Maschine waren:

  • ein Bandtransport- und Lesemechanismus (das "Bettgestell"), der das Nachrichtenband in einer Schleife mit 5000 Zeichen pro Sekunde laufen ließ;
  • eine Einheit, die den Schlüsselstrom elektronisch erzeugt hat;
  • fünf parallele Verarbeitungseinheiten, die so programmiert werden könnten, dass sie einen großen Bereich von Booleschen Operationen ausführen;
  • fünf Zähleinheiten, die jeweils die Anzahl von s oder x s gezählt und, wenn sie eine voreingestellte Summe überschritten, ausgedruckt haben.

Die fünf parallelen Verarbeitungseinheiten ermöglichten es, Tuttes "1+2-Einbruch" und andere Funktionen mit einer effektiven Geschwindigkeit von 25.000 Zeichen pro Sekunde auszuführen, indem eine von Flowers erfundene Schaltung verwendet wurde, die jetzt als Schieberegister bezeichnet wird . Donald Michie hat eine Methode entwickelt, um Colossus sowohl beim Radbruch als auch bei der Radeinstellung zu unterstützen. Dies wurde dann bei späteren Colossi in spezieller Hardware implementiert.

Insgesamt waren zehn Colossus-Rechner im Einsatz und ein elfter wurde bei Kriegsende in Europa ( VE-Day ) in Betrieb genommen.

Sondermaschinen

Neben den kommerziell hergestellten Fernschreibern und Reperforatoren wurden eine Reihe anderer Maschinen gebaut, die bei der Vorbereitung und Prüfung von Bändern in Newmanry und Testery helfen. Die ungefähre Ergänzung ab Mai 1945 war wie folgt.

Maschinen zur Entzifferung von Tunny ab Mai 1945
Name Funktion Testbericht Newmanry
Super-Robinson Wird für Krippenläufe verwendet, bei denen zwei Bänder in allen Positionen verglichen wurden. Enthält einige Ventile. 2
Koloss Mk.2 Gezählt wurde eine Bedingung mit einem Nachrichtenband und einem elektronisch erzeugten Schlüsselzeichenstrom, der die verschiedenen Tunny-Räder in unterschiedlichen relativen Positionen ("Schritte") imitiert. Enthält etwa 2.400 Ventile. 10
Drachen Wird zum Einstellen kurzer Krippen durch "Krippenziehen" verwendet (daher der Name). 2
Wassermann Eine bei Kriegsende in Entwicklung befindliche Maschine für die "Go-Backs" der SZ42B, die den Inhalt des Nachrichtenbandes in einer großen Kondensatorbank speicherte, die als elektronischer Speicher diente. 1
Proteus Eine Maschine zur Verwendung von Tiefen , die bei Kriegsende im Bau war , aber nicht abgeschlossen.
Entschlüsselungsmaschinen Übersetzt von eingegebenem Geheimtext in ausgedruckten Klartext. Einige der späteren wurden durch die Verwendung einiger Ventile beschleunigt. Für die Newmanry wurden eine Reihe von modifizierten Maschinen hergestellt 13
Thunfische Siehe Britischer Tunny oben 3
Meilen Eine Reihe von immer komplexer werdenden Maschinen (A, B, C, D), die zwei oder mehr Bänder lesen und diese auf verschiedene Weise zu einem Ausgabeband kombinieren. 3
Garbo Ähnlich wie Junior, aber mit einer Delta'ing- Einrichtung – wird zum Rechteckigen verwendet. 3
Junioren Zum Bedrucken von Bändern über ein Steckerfeld, um die Zeichen nach Bedarf zu ändern, zum Drucken von De-Chis. 4
Einlegemaschinen Ähnlich wie Angel, jedoch mit einer Vorrichtung zur manuellen Korrektur. 2
Engel Kopierte Bänder. 4
Handperforatoren Generiertes Band von einer Tastatur. 2
Handzähler Gemessene Textlänge. 6
Aufkleber (heiß) Bostik und Benzol wurden zum Kleben von Klebebändern verwendet, um eine Schlaufe zu machen. Das zu verklebende Band wurde zwischen zwei elektrisch beheizte Platten eingelegt und das Benzol verdampft. 3
Aufkleber (kalt) Klebebänder ohne Erhitzen. 6

Schritte in der Radeinstellung

Die Ermittlung der Startposition der Chi ( χ )-Räder erforderte zunächst, dass deren Nockeneinstellungen durch "Radbrechen" ermittelt wurden. Dies wurde zunächst durch zwei eingehende Nachrichten erreicht .

Die Anzahl von Startpositionen für die ersten zwei Räder, & khgr; 1 und χ 2 betrug 41 × 31 = 1271. Der erste Schritt all diese Startpositionen gegen die Nachrichtenband zu versuchen war. Dies war Tuttes "1+2-Einbruch", bei dem es darum ging, (∆Z 1 ⊕ ∆Z 2 ⊕ ∆ χ 1 ⊕ ∆ χ 2 ) zu berechnen – was eine putative ( D 1 ⊕ ∆D 2 ) ergibt – und die Anzahl der mal dies gab . Falsche Startpositionen würden im Durchschnitt eine Punktzahl von 50% der Nachrichtenlänge ergeben. Im Durchschnitt würde die Punktzahl für einen korrekten Startpunkt 54% betragen, aber es gab zwangsläufig eine beträchtliche Streuung der Werte um diese Mittelwerte.

Sowohl Heath Robinson, das als "Old Robinson" bekannt wurde, als auch Colossus wurden entwickelt, um diesen Prozess zu automatisieren. Die statistische Theorie ermöglichte die Ableitung von Maßen dafür, wie weit eine Zählung von den erwarteten 50% mit einem falschen Ausgangspunkt für die Chi- Räder entfernt war. Dieses Maß für die Abweichung von der Zufälligkeit wurde Sigma genannt. Startpunkte, die eine Zählung von weniger als 2,5 × Sigma ergaben, die als "Satzsumme" bezeichnet wurden, wurden nicht ausgedruckt. Das Ideal für einen Lauf zum Einstellen von χ 1 und χ 2 war, dass ein einziges Paar von Versuchswerten einen herausragenden Wert für Sigma erzeugte, wodurch die Startpositionen der ersten beiden Chi- Räder identifiziert wurden . Ein Beispiel für die Ausgabe eines solchen Laufs auf einem Mark 2 Colossus mit seinen fünf Zählern: a, b, c, d und e, ist unten angegeben.

Ausgabetabelle gekürzt aus Smalls "The Special Fish Report". Der eingestellte Gesamtschwellenwert war 4912.
χ 1 χ 2 Zähler Zählen Bedienerhinweise zum Ausgang
06 11 ein 4921
06 13 ein 4948
02 16 e 4977
05 18 B 4926
02 20 e 4954
05 22 B 4914
03 25 D 4925
02 26 e 5015 4.6
19 26 C 4928
25 19 B 4930
25 21 B 5038 5.1
29 18 C 4946
36 13 ein 4955
35 18 B 4926
36 21 ein 5384 ← 12.2 σ ch χ 1 χ 2  ! !
36 25 ein 4965
36 29 ein 5013
38 08 D 4933

Bei einer durchschnittlich großen Nachricht würde dies etwa acht Minuten dauern. Doch durch die Parallelität der Mark 2 Colossus verwendet wird , die Anzahl der Male hatte die Nachricht gelesen werden konnte um den Faktor fünf reduziert werden, von 1271 bis 255 identifiziert Nachdem möglich χ 1 , & khgr; 2 Startpositionen, ist der nächste Schritt war zu versuchen, die Startpositionen für die anderen Chi- Räder zu finden. Im obigen Beispiel gibt es eine einzige Einstellung von χ 1 = 36 und χ 2 = 21, deren Sigma-Wert sie von den anderen abhebt. Dies war nicht immer der Fall, und kleiner aufzählt 36 verschiedene weitere Durchläufe , die gemäß dem Ergebnis der versucht werden könnten , χ 1 , & khgr; 2 läuft. Zuerst wurden die Entscheidungen in diesem iterativen Prozess vom Kryptoanalytiker getroffen, der am Schreibmaschinenausgang saß und den Wren-Bedienern Anweisungen gab. Max Newman entwarf einen Entscheidungsbaum und übertrug dann Jack Good und Donald Michie die Aufgabe, andere zu entwickeln. Diese wurden von den Wrens ohne Rückgriff auf die Kryptoanalytiker verwendet, wenn bestimmte Kriterien erfüllt waren.

In dem obigen Beispiel von Small wurde der nächste Lauf mit den ersten beiden Chi- Rädern auf die gefundenen Startpositionen und drei separaten parallelen Erkundungen der verbleibenden drei Chi- Räder durchgeführt. Ein solcher Lauf wurde als "Kurzlauf" bezeichnet und dauerte etwa zwei Minuten.

Ausgabetabelle angepasst von Smalls "The Special Fish Report". Der eingestellte Gesamtschwellenwert war 2728.
χ 1 χ 2 χ 3 χ 4 χ 5 Zähler Zählen Bedienerhinweise zum Ausgang
36 21 01 ein 2938 6.8 ! χ 3  !
36 21 01 B 2763
36 21 01 C 2803
36 21 02 B 2733
36 21 04 C 3003 8.6 ! χ 5  !
36 21 06 ein 2740
36 21 07 C 2750
36 21 09 B 2811
36 21 11 ein 2751
36 21 12 C 2759
36 21 14 C 2733
36 21 16 ein 2743
36 21 19 B 3093 11.1 ! χ 4  !
36 21 20 ein 2785
36 21 22 B 2823
36 21 24 ein 2740
36 21 25 B 2796
36 21 01 B 2763
36 21 07 C 2750

So ist die wahrscheinlichen Startpositionen für die Chi - Räder sind: χ 1 = 36, χ 2 = 21, χ 3 = 01, & khgr; 4 = 19, χ 5 = 04. vor dem de- prüft werden , um diese hatten chi ( D ) -Nachricht wurde an die Prüfstelle übergeben. Dabei führte Colossus eine Zählung der Häufigkeit der 32 Zeichen in ΔD durch . Small beschreibt die Überprüfung der Häufigkeitszählung der ΔD- Zeichen als " Säuretest ", und dass praktisch jeder Kryptoanalytiker und Wren in Newmanry und Testery den Inhalt der folgenden Tabelle auswendig kannte.

Relative Häufigkeitszahl der Zeichen in ΔD.
Verkohlen. Zählen Verkohlen. Zählen Verkohlen. Zählen Verkohlen. Zählen
/ 1,28 R 0,92 EIN 0,96 D 0,89
9 1,10 C 0,90 U 1,24 F 1.00
h 1.02 V 0,94 Q 1,01 x 0,87
T 0,99 g 1.00 W 0,89 B 0,82
Ö 1,04 L 0,92 5 1.43 Z 0,89
m 1.00 P 0,96 8 1,12 Ja 0,97
n 1.00 ich 0,96 K 0,89 S 1,04
3 1,13 4 0,90 J 1,03 E 0,89

Wenn die abgeleiteten Startpunkte der Chi Räder diesen Test bestanden, die De- chi wurde -ed Nachricht an den Testery geleitet , wo manuelle Methoden verwendet wurden , um die herzuleiten psi und Motoreinstellungen. Wie Small bemerkte, erforderte die Arbeit in Newmanry viel statistische Wissenschaft, während die Arbeit in Testery viel Sprachkenntnisse erforderte und als Kunst von großem Interesse war. Der Kryptoanalytiker Jerry Roberts wies darauf hin, dass diese Testery-Arbeit eine größere Belastung für die Mitarbeiter darstelle als die automatisierten Prozesse in Newmanry.

Siehe auch

Hinweise und Referenzen

Literaturverzeichnis