Kryptoanaliza szyfru Lorenza - Cryptanalysis of the Lorenz cipher
Czas | Wydarzenie |
---|---|
wrzesień 1939 | W Europie wybucha wojna . |
Druga połowa 1940 | Przechwycono pierwsze transmisje inne niż Morse'a . |
czerwiec 1941 | Pierwszy eksperymentalny link SZ40 Tunny rozpoczął się od wskaźnika alfabetycznego . |
sierpień 1941 | Dwie długie wiadomości dogłębne dały 3700 znaków klucza . |
styczeń 1942 | |
lipiec 1942 | |
Październik 1942 | |
Listopad 1942 | „Włamanie 1+2” wymyślone przez Billa Tutte . |
luty 1943 | Wprowadzono bardziej złożony SZ42A. |
maj 1943 | Heath Robinson dostarczył. |
Czerwiec 1943 | Powstanie Newmanry . |
grudzień 1943 | Colossus I pracuje w Dollis Hill przed dostawą do Bletchley Park. |
luty 1944 | Pierwsze użycie Colossus I do prawdziwej pracy. |
Marzec 1944 | Zamówiono cztery Kolosy (Mark 2). |
kwiecień 1944 | Rozkaz na kolejne Kolosy zwiększono do 12. |
Czerwiec 1944 | |
sierpień 1944 | Ustawienia krzywek na wszystkich kołach Lorenz zmieniały się codziennie. |
maj 1945 |
Kryptoanaliza szyfru Lorenza była procesem, który umożliwił Brytyjczykom odczytywanie wiadomości armii niemieckiej wysokiego szczebla podczas II wojny światowej . Brytyjski rząd Code and Cypher School (GC&CS) w Bletchley Park odszyfrował wiele komunikatów między Oberkommando der Wehrmacht (OKW, niemieckie naczelne dowództwo) w Berlinie a ich dowództwami armii w okupowanej Europie, z których niektóre były podpisane „Adolf Hitler, Führer”. Były to przechwycone transmisje radiowe inne niż Morse'a , które zostały zaszyfrowane przez załączniki szyfrujące strumienia wirnika teledrukarki Lorenz SZ . Odszyfrowanie tego ruchu stało się ważnym źródłem informacji wywiadowczych „ Ultra ”, które znacząco przyczyniły się do zwycięstwa aliantów.
W przypadku tajnych wiadomości wysokiego poziomu niemieckie służby zbrojne zaszyfrowały każdy znak przy użyciu różnych maszyn szyfrujących strumieniowo Geheimschreiber (sekretarz) na obu końcach łącza telegraficznego przy użyciu 5-bitowego międzynarodowego alfabetu telegraficznego nr 2 (ITA2). Następnie odkryto, że maszyny te to Lorenz SZ (SZ od Schlüssel-Zusatz , co oznacza „zaszyfrowany załącznik”) dla wojska, Siemens i Halske T52 dla sił powietrznych oraz Siemens T43, który był mało używany i nigdy nie został złamany przez Sojusznicy.
Bletchley Park odszyfrowuje wiadomości zaszyfrowane za pomocą maszyn Enigma ujawniło, że Niemcy nazwali jeden ze swoich bezprzewodowych systemów transmisji teledrukarek „Sägefisch” (sawfish), co skłoniło brytyjskich kryptografów do określenia zaszyfrowanego niemieckiego ruchu radiotelegraficznego jako „ Ryby ”. „ Tunny ” (tunafish) to nazwa nadana pierwszemu łączu bez alfabetu Morse'a, która została następnie użyta dla maszyn szyfrujących i ich ruchu.
Podobnie jak w przypadku całkowicie oddzielnej kryptoanalizy Enigmy , to niemieckie niedociągnięcia operacyjne umożliwiły wstępną diagnozę systemu i sposób na odszyfrowanie. W przeciwieństwie do Enigmy żadna maszyna fizyczna nie dotarła do rąk sojuszników aż do samego końca wojny w Europie, długo po tym, jak ustanowiono masowe odszyfrowywanie. Problemy z odszyfrowywaniem wiadomości Tunny doprowadziły do opracowania „ Colossus ”, pierwszego na świecie elektronicznego, programowalnego komputera cyfrowego, z których dziesięć było używanych do końca wojny, w którym to czasie odszyfrowano około 90% wybranych wiadomości Tunny w parku Bletchley.
Albert W. Small, kryptoanalityk z US Army Signal Corps, który został oddelegowany do Bletchley Park i pracował nad Tunny, powiedział w swoim raporcie z grudnia 1944 r. w Arlington Hall, że:
Codzienne rozwiązania komunikatów Fisha w GC&CS odzwierciedlają tło brytyjskiego geniuszu matematycznego, doskonałych umiejętności inżynierskich i solidnego zdrowego rozsądku. Każdy z nich był niezbędnym czynnikiem. Każdy mógł być przeceniony lub niedoceniony ze szkodą dla rozwiązań; niezwykłym faktem jest to, że połączenie elementów było najwyraźniej w idealnej proporcji. Rezultatem jest wybitny wkład w naukę kryptoanalityczną.
Niemieckie maszyny Tunny
Załączniki szyfru Lorenz SZ zaimplementowały szyfr strumieniowy Vernama , używając złożonej tablicy dwunastu kół, które dostarczały jako strumienia klucza coś, co powinno być kryptograficznie bezpieczną liczbą pseudolosową . Strumień klucza został połączony z tekstem jawnym, aby utworzyć tekst zaszyfrowany na końcu transmisji za pomocą funkcji wyłącznej lub (XOR) . Po stronie odbiorczej identycznie skonfigurowana maszyna wyprodukowała ten sam strumień kluczy, który został połączony z tekstem zaszyfrowanym w celu wytworzenia tekstu jawnego, tj. system zaimplementował algorytm klucza symetrycznego .
Kluczowy strumień został wygenerowany przez dziesięć z dwunastu kół. Był to produkt XOR-ingu 5-bitowego znaku generowanego przez pięć kół prawej ręki, koła chi ( ) i pięć kół lewej ręki, psi ( ). W chi koła zawsze przeniósł się na jednej pozycji dla każdej przychodzącej charakteru tekst zaszyfrowany, ale psi koła nie.
Centralne dwa koła mu ( ) lub „silnikowe” określały, czy koła psi obracały się z nowym znakiem. Po zaszyfrowaniu każdej litery albo wszystkie pięć kół psi przesunęło się dalej, albo pozostały nieruchome i ponownie użyto tej samej litery klucza psi. Podobnie jak koła chi , koło 61 poruszało się po każdym znaku. Gdy 61 miał krzywkę w aktywnej pozycji i w ten sposób wygenerował x (przed ruchem) 37 przesunął się jeden raz: kiedy krzywka była w nieaktywnej pozycji (przed ruchem) 37 i koła psi pozostały nieruchome. We wszystkich, z wyjątkiem najwcześniejszych maszyn, istniał dodatkowy czynnik, który wpływał na poruszanie się po kołach psi . Były to cztery różne typy i nazywano je „Ograniczeniami” w Bletchley Park. Wszystkie dotyczyły pewnego aspektu poprzednich pozycji kół maszyny.
Liczby krzywek na zestaw dwunastu kołami SZ42 maszyn wyniosła 501 i była współ-prime ze sobą, dając niezwykle długi okres przed kluczowej sekwencji powtarzających się. Każda krzywka mogła znajdować się albo w położeniu podniesionym, w którym to przypadku wnosiła x do logiki systemu, odwracając wartość bitu, albo w położeniu opuszczonym, w którym to przypadku generowała • . Całkowita możliwa liczba wzorów podniesionych krzywek wynosiła 2 501 co jest astronomicznie dużą liczbą. W praktyce jednak około połowa krzywek na każdym kole była w pozycji podniesionej. Później Niemcy zdali sobie sprawę, że jeśli liczba podniesionych krzywek nie byłaby bardzo zbliżona do 50%, wystąpiłyby przebiegi x s i • s, słabość kryptograficzna.
Proces sprawdzania, która z 501 krzywek znajduje się w pozycji podniesionej, nazwano „łamaniem kół” w Bletchley Park. Ustalenie pozycji początkowych kół dla konkretnej przekładni nazwano „ustawieniem koła” lub po prostu „ustawieniem”. Fakt, że wszystkie koła psi poruszały się razem, ale nie przy każdym wprowadzanym znaku, był główną słabością maszyn, które przyczyniły się do brytyjskiego sukcesu kryptoanalitycznego.
Bezpieczna telegrafia
Telegrafia elektromechaniczna została opracowana w latach 30. i 40. XIX wieku, na długo przed telefonią , i działała na całym świecie do czasów II wojny światowej . Rozbudowany system kabli połączonych witryn w obrębie krajów i między nimi, ze standardowym napięciem -80 V wskazującym „znak” i +80 V wskazującym „przestrzeń”. Tam, gdzie transmisja kablowa stała się niepraktyczna lub niewygodna, na przykład w przypadku mobilnych jednostek armii niemieckiej, stosowano transmisję radiową.
Teledrukarki na każdym końcu obwodu składały się z klawiatury i mechanizmu drukującego oraz bardzo często pięciootworowego mechanizmu odczytu i dziurkowania taśmy papierowej z perforacją . W trybie online naciśnięcie klawisza alfabetu po stronie nadawczej powodowało wydrukowanie odpowiedniego znaku po stronie odbierającej. Powszechnie jednak system łączności polegał na tym, że operator nadawczy przygotowywał zestaw wiadomości offline, wybijając je na taśmę papierową, a następnie przechodził w tryb online tylko w celu transmisji wiadomości zapisanych na taśmie. System zazwyczaj wysyła około dziesięciu znaków na sekundę, a więc zajmuje linię lub kanał radiowy krócej niż w przypadku pisania online.
Znaki wiadomości były reprezentowane przez kody Międzynarodowego Alfabetu Telegraficznego nr 2 ( ITA2 ). Medium transmisyjne, przewodowe lub radiowe, wykorzystywało asynchroniczną komunikację szeregową, przy czym każdy znak był sygnalizowany impulsem startu (spacji), 5 impulsami danych i 1½ impulsami stopu (znaku). W Bletchley Park impulsy znakowe były oznaczane przez x
(„krzyżyk”), a impulsy kosmiczne •
(„kropka”). Na przykład litera „H” zostałaby zakodowana jako ••x•x
.
Wzór impulsów Znak = x , Spacja = • | Dwójkowy | Przesunięcie litery | Przesunięcie figury | Interpretacja „bez zmiany” BP |
---|---|---|---|---|
••.••• | 00000 | zero | zero | / |
••.x•• | 00100 | przestrzeń | przestrzeń | 9 |
••.x•x | 00101 | h | # | h |
••.••x | 00001 | T | 5 | T |
••.•xx | 00011 | O | 9 | O |
••.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 | i | 8 | i |
•x.••• | 01000 | LF | LF | 4 |
xx.••• | 11000 | A | - | A |
xx.x•• | 11100 | U | 7 | U |
xx.x•x | 11101 | Q | 1 | Q |
xx.••x | 11001 | W | 2 | W |
xx.•xx | 11011 | FIGI | + lub 5 | |
xx.xxx | 11111 | LTRS | - lub 8 | |
xx.xx• | 11110 | K | ( | K |
xx.•x• | 11010 | J | dzwon | 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 | Tak | 6 | Tak |
x•.x•• | 10100 | S | ' | S |
x•.••• | 10000 | mi | 3 | mi |
Znaki przesunięcia cyfry (RYS.) i przesunięcia litery (LETRS) określały, w jaki sposób strona odbierająca interpretowała ciąg znaków do następnego znaku przesunięcia. Ze względu na niebezpieczeństwo uszkodzenia znaku przesunięcia, niektórzy operatorzy wpisali parę znaków przesunięcia podczas zmiany z liter na cyfry lub odwrotnie . Wpisali więc 55M88, aby reprezentować kropkę. Takie podwojenie znaków było bardzo pomocne w statystycznej analizie kryptograficznej stosowanej w Bletchley Park. Po zaszyfrowaniu znaki przesunięcia nie miały specjalnego znaczenia.
Szybkość transmisji wiadomości radiotelegraficznej była trzy lub cztery razy większa od szybkości transmisji alfabetu Morse'a i ludzki słuchacz nie mógł jej zinterpretować. Jednak standardowy dalekopis wyprodukowałby tekst wiadomości. Załącznik szyfrujący Lorenza zmienił tekst jawny wiadomości na tekst zaszyfrowany, który był niemożliwy do zinterpretowania przez osoby bez identycznej maszyny skonfigurowanej w identyczny sposób. To było wyzwanie, przed którym stanęli łamacze kodów z Bletchley Park.
Przechwycenie
Przechwytywanie transmisji Tunny nastręczało poważnych problemów. Ponieważ nadajniki były kierunkowe, większość sygnałów w odbiornikach w Wielkiej Brytanii była dość słaba. Co więcej, do transmisji tych używano około 25 różnych częstotliwości , które czasami ulegały zmianie. Po początkowym odkryciu sygnałów nie-Morse'a w 1940 r. na wzgórzu w Ivy Farm w Knockholt w hrabstwie Kent utworzono radiową stację przechwytującą o nazwie Foreign Office Research and Development Establishment , specjalnie w celu przechwytywania tego ruchu. Ośrodek był kierowany przez Harolda Kenworthy'ego, posiadał 30 odbiorników i zatrudniał około 600 pracowników. W pełni funkcjonował na początku 1943 roku.
Ponieważ jedna pominięta lub uszkodzona postać może uniemożliwić odszyfrowanie, wymagana była największa dokładność. Technologia undulatora wykorzystywana do rejestrowania impulsów została pierwotnie opracowana dla szybkiego Morse'a. Dało to widoczny zapis impulsów na wąskiej taśmie papierowej. To było następnie czytane przez ludzi zatrudnionych jako „czytelnicy poślizgu”, którzy interpretowali szczyty i doliny jako znaki i odstępy znaków ITA2. Następnie wyprodukowano perforowaną taśmę papierową do transmisji telegraficznej do Bletchley Park, gdzie została wykrojona.
Szyfr Vernama
Szyfr Vernama zaimplementowany przez maszyny Lorenz SZ wykorzystuje funkcję Boole'a „exclusive or” (XOR) , symbolizowana przez ⊕ i zwerbalizowana jako „A lub B, ale nie oba”. Przedstawia to poniższa tabela prawdy , gdzie x oznacza „prawdę”, a • oznacza „fałsz”.
WEJŚCIE | WYJŚCIE | |
A | b | A ⊕ B |
• | • | • |
• | x | x |
x | • | x |
x | x | • |
Inne nazwy tej funkcji to: wykluczenie wyłączne, nierówne (NEQ) oraz dodawanie modulo 2 (bez „carry”) i odejmowanie (bez „pożyczania”). Dodawanie i odejmowanie Modulo 2 są identyczne. Niektóre opisy deszyfrowania Tunny odnoszą się do dodawania, a inne do różnicowania, czyli odejmowania, ale oznaczają to samo. Operator XOR jest zarówno asocjacyjny, jak i przemienny .
Wzajemność jest pożądaną cechą szyfru maszynowego, dzięki której ta sama maszyna z tymi samymi ustawieniami może być używana do szyfrowania lub deszyfrowania. Osiąga to szyfr Vernama, ponieważ połączenie strumienia znaków tekstu jawnego ze strumieniem klucza tworzy tekst zaszyfrowany, a połączenie tego samego klucza z tekstem zaszyfrowanym regeneruje tekst jawny.
Symbolicznie:
oraz
- Szyfrogram ⊕ Key = Plaintext
Pierwotnym pomysłem Vernama było zastosowanie konwencjonalnej praktyki telegraficznej, z papierową taśmą tekstu jawnego połączoną z papierową taśmą z kluczem po stronie nadawczej i identyczną taśmą z kluczem połączoną z sygnałem tekstu zaszyfrowanego po stronie odbiorczej. Każda para taśm z kluczami byłaby unikalna ( taśma jednorazowa ), ale generowanie i dystrybucja takich taśm nastręczało znacznych trudności praktycznych. W latach dwudziestych czterej mężczyźni z różnych krajów wynaleźli wirnikowe maszyny szyfrujące Vernama do wytwarzania strumienia kluczy zamiast taśmy. Jednym z nich był Lorenz SZ40/42.
Funkcjonalność związana z bezpieczeństwem
Monoalphabetic podstawienie szyfrowania , takie jak szyfru Caesar łatwo uszkodzony, ponieważ rozsądny tekst zaszyfrowany. Osiąga się to poprzez analizę częstotliwości różnych liter tekstu zaszyfrowanego i porównanie wyniku ze znanym rozkładem częstotliwości liter tekstu jawnego.
W przypadku szyfru polialfabetycznego każdy kolejny znak ma inny alfabet zastępczy. Tak więc analiza częstotliwości pokazuje w przybliżeniu jednorodny rozkład , taki jak uzyskany z (pseudo) generatora liczb losowych . Jednak ponieważ jeden zestaw kół Lorenza obracał się z każdym znakiem, podczas gdy drugi nie, maszyna nie ukrywała wzoru za pomocą sąsiednich znaków w niemieckim tekście jawnym. Alan Turing odkrył tę słabość i wynalazł technikę różnicowania opisaną poniżej, aby ją wykorzystać.
Na kołach silnikowych ( 37 i 61) codziennie zmieniano wzór, które z krzywek znajdowały się w położeniu podniesionym, a które w położeniu opuszczonym . W chi koła wzory cam początkowo były zmieniane co miesiąc. W psi wzory kół były zmieniane co kwartał do października 1942 roku, kiedy częstotliwość wzrosła do co miesiąc, a potem codziennie w dniu 1 sierpnia 1944 roku, kiedy częstotliwość zmieniania chi wzory kół została również zmieniona na dobę.
Liczba pozycji startowych kół wynosiła 43×47×51×53×59×37×61×41×31×29×26×23, czyli około 1,6×10 19 (16 miliardów), zdecydowanie za duża liczba dla kryptoanalityków, aby spróbowali wyczerpującego „ ataku brute-force ”. Czasami operatorzy Lorenza nie posłuchali instrukcji i nadawane były dwie wiadomości z tymi samymi pozycjami początkowymi, zjawisko to określano jako „głębokość” . Sposób, w jaki operator przekazujący informował operatora odbierającego o ustawieniach koła, które wybrał dla wiadomości, którą miał nadać, został nazwany „wskaźnikiem” w Bletchley Park.
W sierpniu 1942 r. schematyczne początki wiadomości, które były przydatne dla kryptoanalityków, zostały zastąpione jakimś nieistotnym tekstem, co nieco utrudniło identyfikację prawdziwej wiadomości. Ten nowy materiał został nazwany quatsch (po niemiecku „nonsens”) w Bletchley Park.
W fazie transmisji eksperymentalnych wskaźnik składał się z dwunastu niemieckich imion, których początkowe litery wskazywały pozycję, w którą operatorzy skręcali dwunastoma kołami. Oprócz pokazania, kiedy dwie transmisje były w pełni głębokie, umożliwiło to również identyfikację głębokości częściowych, w których dwa wskaźniki różniły się tylko jednym lub dwoma położeniami kół. Od października 1942 roku system wskaźników zmienił się na operatora nadającego, który nadaje niezaszyfrowane litery QEP, po których następuje dwucyfrowa liczba. Numer ten został wzięty seryjnie z książki kodów, która została wydana obu operatorom i dla każdego numeru QEP podano ustawienia dwunastu kół. Książki zostały zastąpione, gdy zostały zużyte, ale między wymianami można było zidentyfikować pełne głębokości poprzez ponowne użycie numeru QEP na konkretnym łączu Tunny.
Diagnoza
P | zwykły tekst |
K | klucz – ciąg znaków XOR 'ed (dodany) do tekstu jawnego, aby dać tekst zaszyfrowany |
χ | składnik chi klucza |
ψ | składnik psi klucza |
” | rozszerzone psi – rzeczywista sekwencja znaków dodawana przez koła psi , w tym te , które się nie przesuwają |
Z | szyfrogram |
D | de- chi - szyfrogram z chi składnik klucza usunięte |
Δ | dowolny z powyższych XOR-ów z jego następcą znaku lub bitu |
⊕ | operacja XOR |
Pierwszym krokiem do złamania nowego szyfru jest zdiagnozowanie logiki procesów szyfrowania i deszyfrowania. W przypadku szyfru maszynowego, takiego jak Tunny, wiązało się to z ustaleniem struktury logicznej, a tym samym funkcjonowaniem maszyny. Osiągnięto to bez korzyści w postaci zobaczenia maszyny – co zdarzyło się dopiero w 1945 roku, na krótko przed zwycięstwem aliantów w Europie. System szyfrowania był bardzo dobry w zapewnianiu, że zaszyfrowany tekst Z nie zawiera żadnych statystycznych, okresowych lub językowych cech odróżniających go od losowych. Jednak nie dotyczyło to K , χ , ψ' i D , co było słabością, która oznaczała, że klucze Tunny'ego można było rozwiązać.
Podczas eksperymentalnego okresu transmisji Tunny'ego, kiedy używany był dwunastoznakowy system wskaźników, John Tiltman , weteran Bletchley Park i niezwykle utalentowany kryptoanalityk, przestudiował szyfrogramy Tunny'ego i stwierdził, że używają oni szyfru Vernama.
Gdy dwie skrzynie biegów ( A i B ) używają tego samego klucza, to znaczy, że są w głębi, łącząc je eliminuje efekt klucza. Nazwijmy dwa teksty zaszyfrowane Za i Zb , klucz K oraz dwa teksty jawne Pa i Pb . Mamy wtedy:
- Za Zb = Pa Pb
Jeśli oba teksty jawne mogą zostać opracowane, klucz można odzyskać z dowolnej pary tekst zaszyfrowany-tekst jawny, np.:
-
Za ⊕ Pa = K lub
Zb ⊕ Pb = K
-
Za ⊕ Pa = K lub
31 sierpnia 1941 r. otrzymano dwie długie wiadomości z tym samym wskaźnikiem HQIBPEXEZMUG. Pierwsze siedem znaków tych dwóch szyfrogramów było takich samych, ale druga wiadomość była krótsza. Pierwszych 15 znaków z dwóch wiadomości wyglądało następująco (w interpretacji Bletchley Park):
Za |
JSH4N ZYZY4 GLFRG
|
Zb |
JSH4N ZYMFS /884I
|
Za ⊕ Zb |
///// //FOU GFL3M
|
John Tiltman próbował różnych prawdopodobnych fragmentów tekstu jawnego, tj. „cribs” , z ciągiem Za ⊕ Zb i odkrył, że pierwsza wiadomość w postaci zwykłego tekstu zaczynała się od niemieckiego słowa SPRUCHNUMMER (numer wiadomości). W drugim tekście jawnym operator użył wspólnego skrótu NR dla NUMMER . W drugiej wiadomości było więcej skrótów, a interpunkcja czasami się różniła. Umożliwiło to Tiltmanowi opracowanie w ciągu dziesięciu dni tekstu jawnego obu wiadomości, jako sekwencji znaków tekstu jawnego odkrytego w Pa , który można następnie wypróbować przeciwko Pb i vice versa . To z kolei dało prawie 4000 znaków klucza.
Członkowie Sekcji Badawczej pracowali nad tym kluczem, próbując uzyskać matematyczny opis procesu generowania klucza, ale bez powodzenia. Bill Tutte dołączył do sekcji w październiku 1941 roku i otrzymał zadanie. Przed rekrutacją do Bletchley Park czytał chemię i matematykę w Trinity College w Cambridge . Na szkoleniu uczył się techniki egzaminacyjnej Kasiskiego polegającej na wypisaniu klucza na kwadratowym papierze nowym wierszem po określonej liczbie znaków, co do której podejrzewano, że jest to częstotliwość powtarzania klucza. Gdyby ta liczba była prawidłowa, kolumny macierzy pokazywałyby więcej powtórzeń sekwencji znaków niż sam przypadek.
Tutte pomyślała, że możliwe jest, że zamiast używać tej techniki na całych literach klucza, które prawdopodobnie miały dużą częstotliwość powtórzeń, warto spróbować jej na sekwencji utworzonej przez wzięcie tylko jednego impulsu (bitu). z każdej litery, na tej podstawie, że „ część może być kryptograficznie prostsza niż całość ”. Biorąc pod uwagę, że wskaźniki Tunny wykorzystywały 25 liter (bez J) dla 11 pozycji, ale tylko 23 litery dla dwunastej, wypróbował technikę Kasiskiego na pierwszym impulsie kluczowych znaków, stosując powtórzenie 25 × 23 = 575. nie produkowały dużej liczby powtórzeń w kolumnach, ale Tutte zaobserwowała to zjawisko po przekątnej. Dlatego spróbował ponownie z 574, które pojawiły się w kolumnach. Uznając, że czynnikami pierwszymi tej liczby są 2, 7 i 41, spróbował ponownie z kropką 41 i „ uzyskał prostokąt z kropek i krzyżyków, który był pełen powtórzeń ”.
Było jednak jasne, że sekwencja pierwszych impulsów była bardziej skomplikowana niż ta wytwarzana przez pojedyncze koło o 41 pozycjach. Tutte nazwała ten składnik klucza χ 1 ( chi ). Doszedł do wniosku, że istnieje jeszcze jeden składnik, który był oparty na XOR, który nie zawsze zmieniał się z każdą nową postacią, i że był to produkt koła, które nazwał ψ 1 ( psi ). To samo dotyczyło każdego z pięciu impulsów – oznaczonych tutaj indeksami dolnymi. Tak więc dla pojedynczego znaku klucz K składał się z dwóch elementów:
- K = Ď ⊕ * F .
Rzeczywista sekwencja znaków dodanych przez koła psi , w tym te, które nie rozwijają się, była określana jako rozszerzone psi i symbolizowana przez ψ′
- K = Ď ⊕ * F ' .
Wyprowadzenie składowej ψ przez Tutte było możliwe dzięki temu, że po kropkach częściej niż po nie występują kropki, a po krzyżykach częściej niż po krzyżykach. Było to wynikiem słabości w niemieckim ustawieniu kluczy, którą później zaprzestali. Gdy Tutte dokonał tego przełomu, reszta Sekcji Badawczej przyłączyła się, aby zbadać inne impulsy i ustalono, że wszystkie pięć ψ kół poruszało się razem pod kontrolą dwóch kół μ ( mu lub „silnik”).
Zdiagnozowanie funkcjonowania maszyny Tunny w ten sposób było naprawdę niezwykłym osiągnięciem kryptoanalitycznym i zostało opisane, gdy Tutte został mianowany Oficerem Zakonu Kanady w październiku 2001 roku, jako „ jeden z największych wyczynów intelektualnych II wojny światowej ”.
Turingery
W lipcu 1942 r. Alan Turing spędził kilka tygodni w Sekcji Naukowej. Zainteresował się problemem wyłamywania Tunny'ego z kluczy, które zostały wydobyte z głębin. W lipcu opracował metodę wyprowadzania ustawień krzywki ("łamania koła") z długości klucza. Stało się znane jako „Turingery” (nazywane żartobliwie „Turingismus” przez Petera Ericssona, Petera Hiltona i Donalda Michie ) i wprowadziło ważną metodę „różnicowania”, na której opierała się większość pozostałych rozwiązywania kluczy Tunny w przypadku braku głębi .
Różnice
Poszukiwano procesu, który manipulowałby zaszyfrowanym tekstem lub kluczem, aby uzyskać rozkład częstotliwości znaków, który odbiegał od jednolitości, do której dążył proces szyfrowania. Turing stwierdził, że kombinacja XOR wartości kolejnych (sąsiadujących) znaków w strumieniu zaszyfrowanego tekstu lub klucza uwydatnia wszelkie odstępstwa od jednolitego rozkładu. Wynikowy strumień nazwano różnicą (symbolizowanym przez grecką literę „delta” Δ ), ponieważ XOR jest tym samym co odejmowanie modulo 2. Tak więc dla ciągu znaków S różnicę ΔS otrzymano w następujący sposób, gdzie podkreślenie wskazuje kolejny znak:
- ΔS = S ⊕ S
Strumień S może być tekstem zaszyfrowanym Z , tekstem jawnym P , kluczem K lub jednym z jego dwóch składników χ i ψ . Relacja między tymi elementami nadal obowiązuje, gdy się różnią. Na przykład, a także:
- K = χ ⊕ ψ
Jest tak, że:
- ΔK = Δ χ ⊕ Δ ψ
Podobnie dla tekstu zaszyfrowanego, tekstu jawnego i kluczowych komponentów:
- ΔZ = ΔP ⊕ Δ χ ⊕ Δ ψ
Więc:
- ΔP = ΔZ ⊕ Δ χ ⊕ Δ ψ
Powodem, dla którego różnicowanie umożliwiło przejście do Tunny'ego, było to, że chociaż rozkład częstotliwości znaków w zaszyfrowanym tekście nie mógł zostać odróżniony od strumienia losowego, to samo nie dotyczyło wersji zaszyfrowanego tekstu, z którego element chi klucza miał został usunięty. Dzieje się tak, ponieważ tam, gdzie tekst jawny zawierał powtarzający się znak, a koła psi nie poruszały się dalej, odmienny znak psi ( Δ ψ ) byłby znakiem zerowym (' / ' w Bletchley Park). Kiedy XOR-ed z jakimkolwiek znakiem, ten znak nie ma żadnego efektu, więc w tych okolicznościach ΔK = Δ χ . Tekst zaszyfrowany zmodyfikowany przez usunięcie składnika chi z klucza nazwano dechi D w Bletchley Park, a proces usuwania jako „ dechi- ing”. Podobnie dla usunięcia psi składnika, który był znany jako „de- psi -nia” (lub „głębokości Westchnąwszy”, kiedy to szczególnie trudne).
Więc delta de- chi Ad było:
- ΔD = ΔZ ⊕ Δ χ
Powtarzające się znaki w tekście jawnym były częstsze zarówno ze względu na cechy języka niemieckiego (EE, TT, LL i SS są stosunkowo powszechne), jak i dlatego, że telegrafiści często powtarzali znaki przesunięcia cyfr i liter jako ich utratę w zwykłym przekazie telegraficznym może prowadzić do bełkotu.
Cytując raport ogólny w sprawie Tunny:
Turingery wprowadził zasadę, że klucz różniący się jednym kluczem, teraz nazywany ΔΚ , może dostarczyć informacji niemożliwych do uzyskania ze zwykłego klucza. Ta zasada Δ miała być fundamentalną podstawą niemal wszystkich statystycznych metod łamania i ustawiania kół.
Różnicowanie zastosowano do każdego z impulsów zakodowanych znaków ITA2. Tak więc dla pierwszego impulsu, który został zaszyfrowany przez koła χ 1 i ψ 1 , różniły się o jeden:
- ΔK 1 = k 1 ⊕ K 1
A na drugi impuls:
- ΔK 2 = k 2 ⊕ K 2
I tak dalej.
Okresowość kół chi i psi dla każdego impulsu (odpowiednio 41 i 43 dla pierwszego impulsu) jest również odzwierciedlona we wzorze ΔK . Jednakże, biorąc pod uwagę, że koła psi nie przesunęły się do przodu dla każdego znaku wejściowego, tak jak koła chi , nie było to po prostu powtórzenie wzorca co 41 × 43 = 1763 znaków dla ΔK 1 , ale bardziej złożona sekwencja.
Metoda Turinga
Metoda Turinga wyprowadzania ustawień krzywek kół z długości klucza uzyskanego z głębokości obejmowała proces iteracyjny . Biorąc pod uwagę, że znak delta psi był znakiem zerowym ' / ' średnio przez połowę czasu, założenie, że ΔK = Δ χ miało 50% szansy na poprawność. Proces rozpoczął się od traktowania określonego znaku ΔK jako będącego Δ χ dla tej pozycji. Powstały domniemany wzór bitowy x i • dla każdego koła chi , został zapisany na kartce papieru, która zawierała tyle kolumn, ile było znaków w kluczu, oraz pięć wierszy reprezentujących pięć impulsów Δ χ . Biorąc pod uwagę wiedzę z pracy Tutte o okresowości każdego z kół, umożliwiło to propagację tych wartości na odpowiednich pozycjach w pozostałej części klucza.
Przygotowano również zestaw pięciu arkuszy, po jednym dla każdego z kół chi . Zawierały one zestaw kolumn odpowiadających liczbą krzywek dla odpowiedniego koła chi i były określane jako „klatka”. Więc χ 3 klatka miała 29 takich kolumn. Kolejne „odgadnięcia” wartości Δ χ dały następnie dalsze domniemane wartości stanu krzywki. Mogą one albo zgadzać się, albo nie zgadzać z wcześniejszymi założeniami, a na tych arkuszach podano liczbę uzgodnień i nieporozumień. Tam, gdzie różnice zdań przeważały nad umowami, przyjęto założenie, że znak Δ ψ nie jest znakiem zerowym ' / ', więc odpowiednie założenie zostało zdyskontowane. Stopniowo wydedukowano wszystkie ustawienia krzywek kół chi , a na ich podstawie ustawienia krzywek psi i kół silnikowych.
Wraz z rozwojem metody, wprowadzono ulepszenia, które pozwoliły na użycie jej ze znacznie krótszymi kluczami niż oryginalnych 500 znaków”.
Testery
Testery to sekcja w Bletchley Park, która wykonała większość prac związanych z odszyfrowywaniem wiadomości Tunny. Do lipca 1942 r. natężenie ruchu znacznie się zwiększyło. W związku z tym powstała nowa sekcja, kierowana przez Ralpha Testera – stąd nazwa. Personel składał się głównie z byłych członków Sekcji Badań, w tym Petera Ericssona, Petera Hiltona , Denisa Oswalda i Jerry'ego Robertsa . Metody Testery były prawie w całości ręczne, zarówno przed, jak i po wprowadzeniu w Newmanry metod automatycznych w celu uzupełnienia i przyspieszenia ich pracy.
Pierwsza faza prac Testera trwała od lipca do października, przy czym dominowała metoda deszyfrowania oparta na głębokościach i głębokościach cząstkowych. Jednak po dziesięciu dniach schematyczny początek wiadomości został zastąpiony przez bezsensowny quatsch , co utrudniło odszyfrowanie. Okres ten był jednak produktywny, mimo że każde odszyfrowanie zajmowało dużo czasu. Ostatecznie we wrześniu otrzymano głębokość, która pozwoliła na zastosowanie metody Turinga łamania kół „ Turingery ”, co pozwoliło na rozpoczęcie odczytu aktualnego ruchu. Zebrano obszerne dane na temat statystycznej charakterystyki języka komunikatów i rozszerzono zbiór szopek.
Pod koniec października 1942 r. zamknięto oryginalne, eksperymentalne łącze Tunny i otwarto dwa nowe łącza (Dorsz i Ośmiornica). Wraz z tymi i kolejnymi linkami, 12-literowy system wskaźników określający klucz wiadomości został zastąpiony przez system QEP. Oznaczało to, że można było rozpoznać tylko pełne głębokości — na podstawie identycznych numerów QEP — co doprowadziło do znacznego zmniejszenia deszyfrowanego ruchu.
Po rozpoczęciu działalności Newmanry w czerwcu 1943 r. zmienił się charakter prac wykonywanych w Testerach – odszyfrowywanie i łamanie kół nie było już uzależnione od głębokości.
Brytyjski Tuńczyk
Tak zwana „British Tunny Machine” była urządzeniem, które dokładnie odwzorowywało funkcje maszyn SZ40/42. Wykorzystano go do utworzenia niemieckiego czystego tekstu z taśmy zaszyfrowanego tekstu, po ustaleniu ustawień krzywki. Funkcjonalny projekt powstał w Bletchley Park, gdzie do końca wojny używano dziesięciu Testery Tunnies. Został zaprojektowany i zbudowany w laboratorium Tommy Flowers w Stacji Badawczej General Post Office w Dollis Hill przez Gila Haywarda , „Doca” Coombsa , Billa Chandlera i Sida Broadhursta. Został zbudowany głównie ze standardowego brytyjskiego wyposażenia elektromechanicznego centrali telefonicznej, takiego jak przekaźniki i uniselektory . Wejście i wyjście odbywało się za pomocą teledrukarki z odczytem i dziurkowaniem taśmy papierowej. Maszyny te były używane zarówno w Testery, jak i później w Newmanry . Dorothy Du Boisson, która była operatorką maszyn i członkinią Królewskiej Służby Marynarki Wojennej Kobiet (Wren), opisała podłączenie ustawień jako działanie staroświeckiej centrali telefonicznej i że w trakcie tego została porażona prądem.
Kiedy Flowers został zaproszony przez Haywarda do wypróbowania pierwszej maszyny British Tunny w Dollis Hill, wpisując standardowe zdanie testowe: „Nadszedł czas, aby wszyscy dobrzy ludzie przyszli z pomocą imprezie”, bardzo docenił to, że wirnik działa został utworzony, aby zapewnić następujące wyniki Wordsworthian :
Wejście |
NOW IS THE TIME FOR ALL GOOD MEN TO COME TO THE AID OF THE PARTY
|
Wyjście |
I WANDERED LONELY AS A CLOUD THAT FLOATS ON HIGH OER VALES AND H
|
Do brytyjskich tuńczyków dodano dodatkowe funkcje, aby uprościć ich działanie. Dalsze udoskonalenia zostały wykonane dla wersji stosowanych w Newmanry, trzeci Tuńczyk jest wyposażony produkować de- chi taśm.
Newmanry
Newmanry była sekcja powołana na mocy Max Newman w grudniu 1942 roku do zbadania możliwości wspomagania prac Testery poprzez automatyzację części procesów odszyfrowania wiadomości tuńczyk. Newman pracował z Gerrym Morganem, szefem Sekcji Badań nad sposobami złamania Tunny'ego, kiedy Bill Tutte zwrócił się do nich w listopadzie 1942 z pomysłem czegoś, co stało się znane jako „włamanie 1+2”. Uznano to za wykonalne, ale tylko wtedy, gdy jest to zautomatyzowane.
Newman stworzył funkcjonalną specyfikację tego, co miało stać się maszyną „ Heath Robinson ”. Zatrudnił Stację Badawczą Poczty w Dollis Hill oraz dr CE Wynn-Williams z Telekomunikacji Research Establishment (TRE) w Malvern, aby zrealizować swój pomysł. Prace nad projektem technicznym rozpoczęły się w styczniu 1943 roku, a pierwsza maszyna została dostarczona w czerwcu. Załoga w tym czasie składała się z Newmana, Donalda Michie , Jacka Gooda , dwóch inżynierów i 16 Wrenów. Pod koniec wojny w Newmanry znajdowały się trzy maszyny Robinson, dziesięć komputerów Colossus i kilka tuńczyków brytyjskich. Personel składał się z 26 kryptografów, 28 inżynierów i 275 Wrenów.
Automatyzacja tych procesów wymagała przetwarzania dużych ilości dziurkowanej taśmy papierowej, takiej jak ta, na której odebrano zaszyfrowane wiadomości. Absolutna dokładność tych taśm i ich transkrypcja była niezbędna, ponieważ pojedyncza pomyłka może unieważnić lub zepsuć ogromną ilość pracy. Jack Good przedstawił maksymę „Jeśli nie jest sprawdzone, to źle”.
„Włamanie 1+2”
WT Tutte opracował sposób wykorzystania niejednorodności bigramów (sąsiadujących liter) w niemieckim tekście jawnym przy użyciu zróżnicowanego zaszyfrowanego tekstu i kluczowych komponentów. Jego metoda została nazwana „włamaniem 1+2” lub „atakem podwójnej delty”. Istotą tej metody było znalezienie początkowych ustawień składnika chi klucza poprzez wyczerpujące wypróbowanie wszystkich pozycji jego kombinacji z tekstem zaszyfrowanym i poszukiwanie dowodów na niejednorodność, która odzwierciedla cechy oryginalnego tekstu jawnego. Proces łamania koła musiał z powodzeniem wygenerować bieżące ustawienia krzywki, aby umożliwić wygenerowanie odpowiedniej sekwencji znaków kół chi . Wygenerowanie 22 milionów znaków ze wszystkich pięciu kół chi było całkowicie niewykonalne , więc początkowo było to ograniczone do 41 × 31 = 1271 z pierwszych dwóch.
Biorąc pod uwagę, że dla każdego z pięciu impulsów i :
- Z i = χ i ⊕ ψ i ⊕ P i
i stąd
- P i = Z i ⊕ χ i ⊕ ψ i
dla pierwszych dwóch impulsów:
- (P 1 ⊕ P 2 ) = (Z 1 ⊕ Z 2 ) ⊕ ( χ 1 ⊕ χ 2 ) ⊕ ( ψ 1 ⊕ ψ 2 )
Obliczenie domniemanego P 1 ⊕ P 2 w ten sposób dla każdego punktu początkowego sekwencji χ 1 ⊕ χ 2 dałoby x s i • s z, na dłuższą metę, większą proporcją • s, gdy poprawny punkt początkowy był używany. Tutte wiedziała jednak, że użycie różnych wartości (∆) wzmocniło ten efekt, ponieważ wszelkie powtarzające się znaki w tekście jawnym zawsze generowałyby • , i podobnie ∆ ψ 1 ⊕ ∆ ψ 2 generowałyby • zawsze, gdy koła psi nie poruszały się, i mniej więcej w połowie przypadków, kiedy to robili – w sumie około 70%.
Tutte przeanalizowała odszyfrowany zaszyfrowany tekst z odmienną wersją powyższej funkcji:
- (ΔZ 1 ⊕ ΔZ 2 ) ⊕ (Æ Ď 1 ⊕ Æ Ď 2 ) ⊕ (Æ * F 1 ⊕ Æ * F 2 )
i stwierdzili, że generowała • około 55% czasu. Biorąc pod uwagę naturę udziału kół psi , wyrównanie strumienia chi z tekstem zaszyfrowanym dało największą liczbę • s z (∆Z 1 ⊕ ∆Z 2 ⊕ ∆ χ 1 ⊕ ∆ χ 2 ) było tym, które najprawdopodobniej była poprawna. Technikę tę można było zastosować do dowolnej pary impulsów, zapewniając w ten sposób podstawę zautomatyzowanego podejścia do uzyskania dechi (D) zaszyfrowanego tekstu, z którego można było usunąć składnik psi metodami ręcznymi.
Robinsonowie
Heath Robinson był pierwszą maszyną wyprodukowaną w celu zautomatyzowania metody 1+2 Tutte. Nazwa została nadana przez Wrenów, którzy go obsługiwali, po rysowniku Williamie Heathu Robinsonie , który rysował niezmiernie skomplikowane urządzenia mechaniczne do prostych zadań, podobne do amerykańskiego rysownika Rube Goldberga .
Specyfikację funkcjonalną maszyny opracował Max Newman. Główny projekt inżynierski był dziełem Franka Morrella w Stacji Badawczej Poczty w Dollis Hill w północnym Londynie, wraz z kolegą Tommym Flowers, który zaprojektował „jednostkę łączącą”. Dr CE Wynn-Williams z Telekomunikacyjnego Zakładu Badawczego w Malvern wyprodukował szybkie elektroniczne liczniki zaworów i przekaźników. Budowa rozpoczęła się w styczniu 1943, prototypowa maszyna była używana w Bletchley Park w czerwcu.
Głównymi częściami maszyny były:
- mechanizm transportu i odczytu taśmy (nazywany „stelażem łóżka” ze względu na podobieństwo do odwróconej metalowej ramy łóżka), który uruchamiał zapętlone taśmy z kluczami i wiadomościami z prędkością od 1000 do 2000 znaków na sekundę;
- jednostka łącząca, która realizowała logikę metody Tutte;
- jednostka zliczająca, która zliczyła liczbę • s, a jeśli przekroczyła zadaną sumę, wyświetlała ją lub drukowała.
Prototypowa maszyna była skuteczna pomimo szeregu poważnych niedociągnięć. Większość z nich została stopniowo pokonana w rozwoju tego, co stało się znane jako „Stary Robinson”.
Kolos
Doświadczenie Tommy'ego Flowersa z Heathem Robinsonem i jego poprzednie, unikalne doświadczenie z lampami termionowymi (rurki próżniowe) doprowadziły go do zdania sobie sprawy, że lepszą maszynę można wyprodukować przy użyciu elektroniki. Zamiast odczytywania strumienia klucza z dziurkowanej taśmy papierowej, generowany elektronicznie strumień klucza może umożliwić znacznie szybsze i bardziej elastyczne przetwarzanie. Sugestia Flowersa, że można to osiągnąć za pomocą maszyny, która byłaby całkowicie elektroniczna i zawierałaby od jednego do dwóch tysięcy zaworów, została potraktowana z niedowierzaniem zarówno w Instytucie Badań Telekomunikacyjnych, jak i w Bletchley Park, ponieważ sądzono, że będzie to „zbyt nierzetelny do wykonania użytecznej pracy”. Miał jednak wsparcie Kontrolera Badań w Dollis Hill, W. Gordona Radleya, i wdrożył te idee, tworząc Colossus , pierwszą na świecie elektroniczną, cyfrową, komputerową maszynę obliczeniową, która była w ogóle programowalna, w niezwykle krótkim czasie dziesięć miesięcy. Pomagali mu w tym jego koledzy ze Stacji Badawczej Poczty Dollis Hill : Sidney Broadhurst, William Chandler, Allen Coombs i Harry Fensom .
Prototyp Mark 1 Colossus (Colossus I) z 1500 zaworami zaczął działać w Dollis Hill w grudniu 1943 roku i był używany w Bletchley Park do lutego 1944 roku. Przetwarzało to wiadomość z szybkością 5000 znaków na sekundę, wykorzystując impuls odczytany z taśmy. otwory na koło zębate, które działają jako sygnał zegarowy . Szybko okazało się, że był to ogromny krok naprzód w kryptoanalizie Tunny'ego. Zamówiono kolejne maszyny Colossus i anulowano zamówienia na więcej Robinsonów. Ulepszony Mark 2 Colossus (Colossus II) zawierał 2400 zaworów i po raz pierwszy pracował w Bletchley Park 1 czerwca 1944 r., w sam raz na lądowanie w Normandii w D-day .
Głównymi częściami tej maszyny były:
- mechanizm transportu i odczytu taśmy ("stelaż"), który uruchamiał taśmę wiadomości w pętli z prędkością 5000 znaków na sekundę;
- jednostka, która elektronicznie wygenerowała strumień klucza;
- pięć jednostek przetwarzania równoległego, które można zaprogramować do wykonywania szerokiego zakresu operacji logicznych;
- pięć jednostek liczących, z których każda liczyła • liczbę s lub x s, a jeśli przekroczyła zadaną sumę, wydrukowała ją.
Pięć równoległych jednostek przetwarzania pozwoliło na uruchomienie „1+2 break in” Tutte i innych funkcji z efektywną szybkością 25 000 znaków na sekundę dzięki zastosowaniu obwodów wynalezionych przez Flowersa, które teraz nazwano by rejestrem przesuwnym . Donald Michie opracował metodę wykorzystania Kolosa do wspomagania łamania kół oraz ustawiania kół. Zostało to następnie zaimplementowane w specjalnym sprzęcie w późniejszych Kolosach.
Łącznie w użyciu było dziesięć komputerów Colossus, a jedenasty został uruchomiony pod koniec wojny w Europie ( VE-Day ).
Maszyny specjalne
Oprócz komercyjnie produkowanych teledrukarek i reperforatorów zbudowano szereg innych maszyn, które miały pomóc w przygotowaniu i kontroli taśm w Newmanry i Testery. Przybliżony stan na maj 1945 r. przedstawiał się następująco.
Nazwa | Funkcjonować | Testery | Newmanry |
---|---|---|---|
Super Robinson | Używany do wybiegów łóżeczek, w których porównywano dwie taśmy we wszystkich pozycjach. Zawierał kilka zaworów. | 2 | |
Kolos Mk.2 | Policzył stan obejmujący taśmę z wiadomością i elektronicznie wygenerowany strumień kluczowych znaków imitujący różne koła Tunny w różnych względnych pozycjach („kroczenie”). Zawierał około 2400 zaworów. | 10 | |
Smoki | Używany do ustawiania krótkich łóżeczek metodą „crib-przeciągania” (stąd nazwa). | 2 | |
Wodnik | Maszyna opracowywana pod koniec wojny dla „powrotów” SZ42B, która przechowywała zawartość taśmy wiadomości w dużym banku kondensatorów, który działał jako pamięć elektroniczna. | 1 | |
odmieniec | Maszyna do wykorzystywania głębin, która była w budowie pod koniec wojny, ale nie została ukończona. | ||
Maszyny dekodujące | Przetłumaczone z wpisanego zaszyfrowanego tekstu na wydrukowany tekst jawny. Niektóre z późniejszych przyspieszono za pomocą kilku zaworów. Wiele zmodyfikowanych maszyn zostało wyprodukowanych dla Newmanry | 13 | |
Tunele | Zobacz brytyjskiego tuńczyka powyżej | 3 | |
Miles | Zestaw coraz bardziej skomplikowanych maszyn (A, B, C, D), które odczytują dwie lub więcej taśm i łączą je na różne sposoby w celu uzyskania taśmy wyjściowej. | 3 | |
Garbo | Podobny do Juniora, ale z funkcją Delta'ing – używany do prostokąta. | 3 | |
Juniorzy | Do drukowania taśm za pomocą panelu wtykowego, aby zmienić znaki w razie potrzeby, służy do drukowania de-chis. | 4 | |
Wstaw maszyny | Podobny do Angela, ale z urządzeniem do ręcznego wprowadzania poprawek. | 2 | |
Anioły | Skopiowane taśmy. | 4 | |
Perforatory ręczne | Wygenerowana taśma z klawiatury. | 2 | |
Liczniki ręczne | Zmierzona długość tekstu. | 6 | |
Naklejki (gorące) | Do przyklejania taśm do wykonania pętli użyto Bostika i benzenu . Taśmę do przyklejenia wsunięto między dwie elektrycznie podgrzewane płyty i odparowano benzen. | 3 | |
Naklejki (zimne) | Przyklejone taśmy bez podgrzewania. | 6 |
Kroki w ustawieniu kół
Ustalenie pozycji początkowej kół chi ( χ ) wymagało najpierw, aby ich ustawienia krzywek zostały określone przez „łamanie koła”. Początkowo ten został osiągnięty przez dwóch komunikatów został wysłany w głębi .
Liczba miejsc startowych dla pierwszych dwóch kołach, × 1 i χ 2 wynosiła 41 x 31 = 1271. Pierwszym krokiem było spróbować wszystkich tych pozycjach startowych przed taśmą wiadomości. To było „włamanie 1+2” Tutte, które obejmowało obliczenie (∆Z 1 ⊕ ∆Z 2 ⊕ ∆ χ 1 ⊕ ∆ χ 2 ) — co daje domniemane ( ∆D 1 ⊕ ∆D 2 ) — i zliczenie liczby razy to dało • . Nieprawidłowe pozycje początkowe dałyby średnio 50% długości wiadomości. Średnio liczba punktów dla prawidłowego punktu początkowego wynosiłaby 54%, ale nieuchronnie występował znaczny rozrzut wartości wokół tych średnich.
Zarówno Heath Robinson, który został rozwinięty w coś, co stało się znane jako „Stary Robinson”, jak i Colossus zostały zaprojektowane w celu zautomatyzowania tego procesu. Teoria statystyczna pozwoliła na wyprowadzenie miar tego, jak daleko dowolna liczba była oczekiwana od 50% oczekiwanych z nieprawidłowym punktem początkowym dla kół chi . Ta miara odchylenia od losowości została nazwana sigma. Punkty początkowe, które dały liczbę mniejszą niż 2,5 × sigma, nazwane „set total”, nie zostały wydrukowane. Idealne dla biegu do zestawu × 1 i χ 2 było to, że jedna para wartości doświadczalnej wytwarzanej jedno zaległe wartości sigma sposób identyfikacji pozycji początkowej pierwszego dwóch chi koła. Poniżej podano przykład wyniku takiego przebiegu na kolosie Mark 2 z jego pięcioma licznikami: a, b, c, d i e.
χ 1 | χ 2 | Lada | Liczyć | Notatki operatora na wyjściu |
---|---|---|---|---|
06 | 11 | a | 4921 | |
06 | 13 | a | 4948 | |
02 | 16 | mi | 4977 | |
05 | 18 | b | 4926 | |
02 | 20 | mi | 4954 | |
05 | 22 | b | 4914 | |
03 | 25 | D | 4925 | |
02 | 26 | mi | 5015 | 4,6 |
19 | 26 | C | 4928 | |
25 | 19 | b | 4930 | |
25 | 21 | b | 5038 | 5,1 σ |
29 | 18 | C | 4946 | |
36 | 13 | a | 4955 | |
35 | 18 | b | 4926 | |
36 | 21 | a | 5384 | ← 12.2 σ ch χ 1 χ 2 ! ! |
36 | 25 | a | 4965 | |
36 | 29 | a | 5013 | |
38 | 08 | D | 4933 |
W przypadku wiadomości średniej wielkości zajęłoby to około ośmiu minut. Jednak dzięki wykorzystaniu równoległości kolosa Mark 2, liczbę odczytów wiadomości można było zmniejszyć pięciokrotnie, z 1271 do 255. Po zidentyfikowaniu możliwych pozycji początkowych χ 1 , χ 2 , kolejny krok była próba znalezienia pozycji startowych dla innych kół chi . W powyższym przykładzie jest pojedyncze ustawienie χ 1 = 36 i χ 2 = 21, którego wartość sigma wyróżnia się spośród pozostałych. Nie zawsze tak było, a Small wymienia 36 różnych dalszych przebiegów, które można wypróbować zgodnie z wynikiem przebiegu χ 1 , χ 2 . Na początku wyborów w tym iteracyjnym procesie dokonywał kryptoanalityk siedzący przy wyjściu maszyny do pisania i wywołujący instrukcje operatorom Wrena. Max Newman opracował drzewo decyzyjne, a następnie wyznaczył Jackowi Goodowi i Donaldowi Michie zadanie opracowania innych. Zostały one wykorzystane przez Wrens bez uciekania się do kryptoanalityków, jeśli spełniono określone kryteria.
W powyższym jednym z przykładów Smalla, następny bieg był z dwoma pierwszymi kołami chi ustawionymi na znalezionych pozycjach początkowych i trzema oddzielnymi równoległymi eksploracjami pozostałych trzech kół chi . Taki bieg został nazwany „krótkim biegiem” i trwał około dwóch minut.
χ 1 | χ 2 | χ 3 | χ 4 | χ 5 | Lada | Liczyć | Notatki operatora na wyjściu |
---|---|---|---|---|---|---|---|
36 | 21 | 01 | a | 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 | a | 2740 | |||
36 | 21 | 07 | C | 2750 | |||
36 | 21 | 09 | b | 2811 | |||
36 | 21 | 11 | a | 2751 | |||
36 | 21 | 12 | C | 2759 | |||
36 | 21 | 14 | C | 2733 | |||
36 | 21 | 16 | a | 2743 | |||
36 | 21 | 19 | b | 3093 | ← 11,1 ρ ! χ 4 ! | ||
36 | 21 | 20 | a | 2785 | |||
36 | 21 | 22 | b | 2823 | |||
36 | 21 | 24 | a | 2740 | |||
36 | 21 | 25 | b | 2796 | |||
36 | 21 | 01 | b | 2763 | |||
36 | 21 | 07 | C | 2750 |
Tak więc prawdopodobne położeń początkowych dla chi kół są następujące: χ 1 = 36, χ 2 = 21 χ 3 = 01 × 4 = 19 χ 5 = 04. te musiały być zweryfikowane przed wycofaniem chi ( D wiadomości) został przekazany do Testery. Wiązało się to z tym, że Colossus zliczał częstotliwość 32 znaków w ΔD . Small opisuje sprawdzenie liczby częstotliwości znaków ΔD jako „test na kwas” i że praktycznie każdy kryptoanalityk i Wren w Newmanry and Testery znali na pamięć zawartość poniższej tabeli.
Zwęglać. | Liczyć | Zwęglać. | Liczyć | Zwęglać. | Liczyć | Zwęglać. | Liczyć | |||
---|---|---|---|---|---|---|---|---|---|---|
/ | 1,28 | r | 0,92 | A | 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 | |||
O | 1,04 | L | 0,92 | 5 | 1,43 | Z | 0,89 | |||
m | 1,00 | P | 0,96 | 8 | 1.12 | Tak | 0,97 | |||
n | 1,00 | i | 0,96 | K | 0,89 | S | 1,04 | |||
3 | 1.13 | 4 | 0,90 | J | 1,03 | mi | 0,89 |
Jeżeli uzyskane punkty początku chi kół przeszedł tego testu de- chi -ed wiadomość została przekazana do Testery gdzie metody ręczne były używane do uzyskiwania psi ustawienia i motorycznych. Jak zauważył Small, praca w Newmanry wymagała dużej ilości nauk statystycznych, podczas gdy w Testery wymagała dużej znajomości języka i była bardzo interesująca jako sztuka. Kryptoanalityk Jerry Roberts zauważył, że ta praca testowa była większym obciążeniem dla personelu niż zautomatyzowane procesy w Newmanry.
Zobacz też
Uwagi i referencje
Bibliografia
- BBC Timewatch (2011), Code Breakers: Zagubieni bohaterowie Bletchley Park (wideo)
- Budiansky, Stephen (2006), Colossus, Codebreaking and the Digital Agew Copeland 2006 , s. 52–63
- Carter, Frank (2008), Codebreaking with the Colossus Computer , Bletchley Park Reports, 1 (New ed.), Bletchley Park Trust, ISBN 978-1-906723-00-2
- Churchhouse, Robert (2002), Kody i szyfry: Juliusz Cezar, Enigma i Internet , Cambridge: Cambridge University Press, ISBN 978-0-521-00890-7
- Copeland, B. Jack , wyd. (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. Historia ilustrowana", The Rutherford Journal , 3
- Copeland, B. Jack (2012), Turing: Pionier Wieku Informacji , Oxford: Oxford University Press, ISBN 978-0-19-963979-3
- Currie, Helen (2006), Dziewczyna ATS w Testeryw Copeland 2006 , s. 264–268
- Edgerley, Peter (2006), Testery i łamanie rybw Copeland 2006 , s. 269-277
- Erskine, Ralph; Smith, Michael , wyd. (2011) [2001], The Bletchley Park Codebreakers , Biteback Publishing Ltd, ISBN 978-1-84954-078-0Zaktualizowana i rozszerzona wersja Action This Day: Od złamania kodu Enigmy do narodzin nowoczesnego Computer Bantam Press 2001
- Fensom, Harry (2006), Jak zbudowano i eksploatowano Colossusw Copeland 2006 , s. 297-304
- Kwiaty, 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
- Kwiaty, Thomas H. (2006), D-Day w Bletchley i Colossusw Copeland 2006 , s. 78–83, 91–100
- Gannon, Paul (2007) [2006], Colossus: Greatest Secret Bletchley Park , Atlantic Books, ISBN 978-1-84354-331-2
- Dobrze, Jacku ; Michie, Donaldzie ; Timms, Geoffrey (1945), General Report on Tunny: With Emphasis on Statistical Methods , UK Public Record Office HW 25/4 i HW 25/5, zarchiwizowane od oryginału w dniu 17 września 2010 r. , pobrane 15 września 2010 r.Ta wersja jest kopią faksymiliową, ale istnieje transkrypcja większości tego dokumentu w formacie „.pdf” pod adresem: Sale, Tony (2001), część „General Report on Tunny”, The Newmanry History, sformatowanej przez Tony Sale (PDF) , pobrano 20 września 2010oraz internetowy zapis części 1 pod adresem: Ellsbury, Graham, General Report on Tunny With Emphasis on Statistical Methods , pobrane 3 listopada 2010 r.
- Dobrze, Jacku ; Michie, Donald (1992), IJ Good i Donald Michie w rozmowie z Davidem Kahnem i Karen Frrankel , Computer History Museum (opublikowane 22 czerwca 2012) , pobrane 19 kwietnia 2013
- Dobry, Jack (1993), Zagadka i rybaw Hinsley i Stripp 1993 , s. 149-166
- Dobrze, Jack (2006), Od chaty 8 do Newmanryw Copeland 2006 , s. 204–222
- Government Code and Cypher School (1944), The Bletchley Park 1944 Cryptographic Dictionary sformatowany przez Tony'ego Sale (PDF) , pobrane 7 października 2010
- Hayward, Gil (1993), Operacja Tunnyw Hinsley i Stripp 1993 , s. 175–192
- Hayward, Gil (2006), Brytyjska maszyna do tuńczykaw Copeland 2006 , s. 291–296
- Hinsley, FH ; Stripp, Alan, wyd. (1993) [1992], Codebreakers: Wewnętrzna historia Bletchley Park , Oxford: Oxford University Press, ISBN 978-0-19-280132-6
- Hinsley, FH (1993), Wprowadzenie: Wpływ Ultra w II wojnie światowejw Hinsley i Stripp 1993 , s. 1–13
- McKay, Sinclair (2010), The Secret Life of Bletchley Park: The WWII Codebreaking Center oraz mężczyźni i kobiety, którzy tam pracowali , Londyn: Aurum Press, ISBN 978-1-84513-539-3
- Michie, Donald (2006), Codebreaking and Colossusw Copeland 2006 , s. 223–246
- Newman, Max (ok. 1944), Dodatek 7: Metoda Delta-chiw Copeland 2006 , s. 386–390
- Roberts, Jerry (2006), "Major Tester's Section", Colossus: The Secrets of Codebreaking Computers Bletchley Parkw Copeland 2006 , s. 249–259
- Roberts, Jerry (2009), Moje ściśle tajne łamanie kodów podczas II wojny światowej: Ostatni brytyjski ocalały z testu Bletchley Park (iTunes U) (wideo), University College London
- Small, Albert W. (grudzień 1944), The Special Fish Report , The American National Archive (NARA) College Campus Washington , pobrane 7 marca 2013
- Tutte, William T. (2006), Dodatek 4: Moja praca w Bletchley Parkw Copeland 2006 , s. 352–369
- Tutte, WT (19 czerwca 1998), Fish and I (PDF) , pobrane 7 kwietnia 2012Zapis wykładu prof. Tutte na Uniwersytecie Waterloo
- Weierud, Frode (2006), Jesiotr Bletchley Park — ryba, która nie składała jajw Copeland 2006 , s. 307–327
- Wylie, Shaun (2001), Breaking Tunny i narodziny Kolosaw Erskine & Smith 2011 , s. 283-304