Kryptoanalyse der Lorenz-Chiffre - Cryptanalysis of the Lorenz cipher
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-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.
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.
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
.
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.
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:
und
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 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
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
-
Za ⊕ Pa = K oder
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 1 ⊕ K 1
Und zum zweiten Impuls:
- & Dgr; K 2 = K 2 ⊕ K 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
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
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.
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.
χ 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.
χ 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.
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
- BBC Timewatch (2011), Code Breakers: Bletchley Parks verlorene Helden (Video)
- Budiansky, Stephen (2006), Colossus, Codebreaking und das digitale Zeitalterin Copeland 2006 , S. 52–63
- Carter, Frank (2008), Codebreaking with the Colossus Computer , Bletchley Park Reports, 1 (Neue Hrsg.), Bletchley Park Trust, ISBN 978-1-906723-00-2
- Churchhouse, Robert (2002), Codes and Ciphers: Julius Caesar, the Enigma and the Internet , Cambridge: Cambridge University Press, ISBN 978-0-521-00890-7
- Copeland, B. Jack , Hrsg. (2006), Colossus: The Secrets of Bletchley Park's Codebreaking Computers , Oxford: Oxford University Press, ISBN 978-0-19-284055-4
- Copeland, B. Jack (2010), "Colossus: Breaking the German 'Tunny' Code at Bletchley Park. An Illustrated History", The Rutherford Journal , 3
- Copeland, B. Jack (2012), Turing: Pionier des Informationszeitalters , Oxford: Oxford University Press, ISBN 978-0-19-963979-3
- Currie, Helen (2006), Ein ATS-Mädchen im Testeryin Copeland 2006 , S. 264–268
- Edgerley, Peter (2006), The Testery and the Breaking of Fishin Copeland 2006 , S. 269–277
- Erskine, Ralph; Smith, Michael , Hrsg. (2011) [2001], Die Bletchley Park Codebreakers , Biteback Publishing Ltd, ISBN 978-1-84954-078-0Aktualisierte und erweiterte Version von Action This Day: From Breaking of the Enigma Code to the Birth of the Modern Computer Bantam Press 2001
- Fensom, Harry (2006), Wie Colossus gebaut und betrieben wurdein Copeland 2006 , S. 297–304
- Flowers, Thomas H. (1983), "The Design of Colossus" , Annals of the History of Computing , 5 (3): 239–252, doi : 10.1109/MAHC.1983.10079 , S2CID 39816473
- Blumen, Thomas H. (2006), D-Day in Bletchley and Colossusin Copeland 2006 , S. 78–83, 91–100
- Gannon, Paul (2007) [2006], Colossus: Bletchley Parks größtes Geheimnis , Atlantic Books, ISBN 978-1-84354-331-2
- Gut, Jack ; Michie, Donald ; Timms, Geoffrey (1945), General Report on Tunny: With Emphasis on Statistical Methods , UK Public Record Office HW 25/4 und HW 25/5, archiviert vom Original am 17. September 2010 , abgerufen am 15. September 2010Diese Version ist eine Faksimile-Kopie, aber es gibt eine Abschrift eines Großteils dieses Dokuments im '.pdf'-Format unter: Sale, Tony (2001), Teil des "General Report on Tunny", the Newmanry History, formatiert von Tony Sale (PDF) , abgerufen am 20. September 2010, und ein Web-Transkript von Teil 1 unter: Ellsbury, Graham, General Report on Tunny With Emphasis on Statistical Methods , abgerufen am 3. November 2010
- Gut, Jack ; Michie, Donald (1992), IJ Good und Donald Michie im Gespräch mit David Kahn und Karen Frrankel , Computer History Museum (veröffentlicht am 22. Juni 2012) , abgerufen am 19. April 2013
- Gut, Jack (1993), Enigma und Fischin Hinsley & Stripp 1993 , S. 149–166
- Gut, Jack (2006), From Hut 8 to the Newmanryin Copeland 2006 , S. 204–222
- Government Code and Cypher School (1944), The Bletchley Park 1944 Cryptographic Dictionary, formatiert von Tony Sale (PDF) , abgerufen am 7. Oktober 2010
- Hayward, Gil (1993), Operation Tunnyin Hinsley & Stripp 1993 , S. 175–192
- Hayward, Gil (2006), Die britische Tunny-Maschinein Copeland 2006 , S. 291–296
- Hinsley, FH ; Stripp, Alan, Hrsg. (1993) [1992], Codebreakers: The Inside Story of Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
- Hinsley, FH (1993), Einführung: Der Einfluss von Ultra im Zweiten Weltkriegin Hinsley & Stripp 1993 , S. 1–13
- McKay, Sinclair (2010), The Secret Life of Bletchley Park: Das WWII Codebreaking Center und die Männer und Frauen, die dort arbeiteten , London: Aurum Press, ISBN 978-1-84513-539-3
- Michie, Donald (2006), Codebreaking and Colossusin Copeland 2006 , S. 223–246
- Newman, Max (ca. 1944), Anhang 7: Delta-Chi-Methodein Copeland 2006 , S. 386–390
- Roberts, Jerry (2006), "Major Tester's Section", Colossus: The Secrets of Bletchley Park's Codebreaking Computersin Copeland 2006 , S. 249–259
- Roberts, Jerry (2009), My Top-Secret Codebreaking during World War II: The Last British Survivor of Bletchley Park's Testery (iTunes U) (Video), University College London
- Small, Albert W. (Dezember 1944), The Special Fish Report , The American National Archive (NARA) College Campus Washington , abgerufen am 7. März 2013
- Tutte, William T. (2006), Anhang 4: Meine Arbeit im Bletchley Parkin Copeland 2006 , S. 352–369
- Tutte, WT (19. Juni 1998), Fish and I (PDF) , abgerufen am 7. April 2012Abschrift einer Vorlesung von Prof. Tutte an der University of Waterloo
- Weierud, Frode (2006), Bletchley Parks Stör – Der Fisch, der keine Eier legtein Copeland 2006 , S. 307–327
- Wylie, Shaun (2001), Breaking Tunny und die Geburt von Colossusin Erskine & Smith 2011 , S. 283–304