Komputery Colossus

Alan Turing

Na uniwersytecie w Cambridge matematyk Alan Turing został wytypowany na kandydata do pracy przy łamaniu szyfrów. Na początku roku 1938 odwiedzał kilkakrotnie Rządową Szkołę Kodów i Szyfrów (ang. Government Codes & Ciphers School - GC&CS) położoną w Broadway w Londynie aby zapoznać się z dotychczasowymi osiągnięciami w tej dziedzinie. Pokazano mu podstawowe metody łamania szyfrów oraz kilka przechwyconych transmisji niemieckich zaszyfrowanych przy pomocy wojskowej Enigmy z łącznicą wtyczkową. Dilly Knox (angielski kryptolog o międzynarodowej sławie) już wtedy wiedział, iż bębny szyfrujące wojskowej wersji maszyny Enigma posiadały inne połączenia elektryczne niż w bębnach maszyn komercyjnych, nie znał natomiast połączeń w bębnie wejściowym oraz widocznie nie wiedział nic o podwójnym szyfrowaniu klucza wiadomości.

Przez pewien czas Alan Turing zastanawiał się nad sposobami podejścia do złamania szyfru Enigmy. Główne nadzieje pokładał w tzw. "znanym niezaszyfrowanym tekście" (ang. known plain text), co w ośrodku w Bletchley Park nosiło nazwę "crib" (ściąga).

Turing zdał sobie sprawę, iż jeśli analiza ruchu radiowego mogła być zastosowana do przewidzenia tekstu zawartego w pewnych partiach zaszyfrowanych wiadomości, to można użyć pewnej maszyny działającej z dużą prędkością do sprawdzenia, czy istniały jakiekolwiek możliwe ustawienia bębnów, które powodowały transformację zaszyfrowanych znaków w znaki przewidziane. Co ważniejsze, wykorzystując swoje zdolności matematyczne wykazał, iż dużo szybciej da się udowodnić, że transformacja z tekstu zaszyfrowanego do tekstu przewidywanego wyklucza olbrzymią ilość możliwych kombinacji bębnów oraz ich pozycji startowych.

Szkoła GC&CS posiadała już w swoich zasobach kilka przechwyconych szyfrogramów dla których znany był czysty tekst. Zostały one przeszmuglowane do Anglii przez polskiego urzędnika Biura Szyfrów.

Wśród wielu różnych cech znalezionych przez Turinga była jedna polegająca na nieregularnym występowaniu w wiadomości tej samej pary liter szyfru i czystego tekstu. Właściwość tę nazywano w Bletchley Park "clicks" (kliknięcia)

JYCQRPWYDEMCJMRSR
SPRUCHNUMMERXEINS
  ^ ^    ^^^ ^

Przypomnij sobie, iż z uwagi na odwracalność maszyny Enigma, transformacja R w C jest tym samym co C w R i transformacja M w E jest taka sama jak E w M.

Występowanie takich par liter uwarunkowane jest kolejnością bębnów szyfrujących oraz pozycją startową rdzeni bębnów. Turing wywnioskował, iż również odwrotnie można określić te parametry wypróbowując wszystkie konfiguracje, aż do uzyskania zgodności danych par liter. Podejście to dałoby wyniki tylko dla maszyny Enigma nie wykorzystującej łącznicy wtyczkowej lub wykorzystującej ją, jednakże bez wymiany liter C i R. W początkowym okresie używania maszyny Enigma zamieniano przy pomocy łącznicy tylko sześć liter, zatem mogłoby się to zdarzyć.

Oczywiście próba rozwiązania tego problemy przy pomocy maszyny Enigma i ręcznego wprowadzania danych trwałaby zbyt długi czas. W następnym kroku należało rozważyć sposób jednoczesnego przeprowadzenia tych testów dla określonej konfiguracji początkowej maszyny Enigma.

Test występowania par liter wymaga pewnej metody szybkiego sprawdzania, czy dana konfiguracja jest prawdziwa lub fałszywa. Doprowadziło to do koncepcji elektrycznego połączenia ze sobą zespołu maszyn Enigma. Zrealizowano to przy użyciu "rozwartej" Enigmy.

W rzeczywistej maszynie Enigma prąd elektryczny wchodzi i wychodzi z nieruchomego bębna wejściowego dzięki bębnowi odwracającemu (U - niem. Umkerwaltz), co uniemożliwiało łączenie ze sobą maszyn Enigma. W rozwartej Enigmie Turinga bęben odwracający posiada dwie strony, z której strona wyjściowa jest podłączona do trzech bębnów odpowiadających dokładnie trzem bębnom początkowym, lecz ułożonym w kolejności odwrotnej (rysunek na prawo). Bębny te odwzorowują drogę powrotną prądu w rzeczywistych bębnach szyfrujących maszyny Enigma. Takie rozwiązanie udostępnia osobne połączenia wejściowe oraz wyjściowe, dzięki czemu można połączyć ze sobą szeregowo kilka maszyn Enigma.

W implementacji z Letchworth (nazwanej tak ze względu na lokalizację w Letchworth fabryki produkcji maszyn rachunkowych - British Tabulating Machine) w inteligentny sposób umieszczono w jednym bębnie okablowanie Enigmy zarówno dla prądu płynącego do bębna odwracającego jak i dla prądu powracającego z tego bębna.

Połączenia z jednego bębna do następnych wykonano w formie czterech koncentrycznych zestawów 26 kontaktów i czterech koncentrycznych zestawów szczotek umieszczonych na każdym bębnie. Trzy zestawy nieruchomych styków były na stałe połączone przewodami między sobą oraz pomiędzy 26 zestykami wejściowymi i wyjściowymi. Trzy bębny, odpowiadające elektrycznie oryginalnym bębnom szyfrującym maszyny Enigma, mogły być teraz montowane ponad kontaktami, co w efekcie tworzyło rozwartą maszynę Enigma z osobnymi zestykami dla prądu wejściowego oraz wyjściowego.

Wracając do problemu sprawdzania, czy litera C szyfruje się w R (co zapisujemy jako C→R) najpierw potrzebne jest przesunięcie od pozycji startowej. Uzyskamy je zapisując nad tekstem alfabet za pomocą małych liter.

abcdefghijklmnopq
JYCQRPWYDEMCJMRSR
SPRUCHNUMMERXEINS
  ^ ^    ^^^ ^

Widzimy zatem, iż C→R na pozycji c, e i l w stosunku do pozycji startowej, a M→E na j, k i n. Rozwarta Enigma pozwala podłączyć napięcie elektryczne do styku wejściowego C, a zestaw 26 żarówek do styków wyjściowych. Jeśli zaświeci się żarówka R, to bębny znajdują się w kolejności i na pozycji takiej, iż C szyfruje się w R.

W pojedynczej maszynie Enigma zdarza się to przy olbrzymiej ilości ustawień bębnów szyfrujących. Jednakże ściąga (ang. crib) pozwala ustawić rozwarte Enigmy na każde wystąpienie podstawienia C→R i mogą one być testowane równolegle w tym samym czasie.

We wszystkich rozwartych Enigmach są montowane bębny szyfrujące w tej samej kolejności. Z kolei w każdej Enigmie lewy i środkowy bęben ustawiany jest na tę samą pozycję startową. Natomiast prawy bęben jest obracany na pozycję, która wg ściągi ma być przetestowana. Wszystkie wejścia połączone są równolegle ze sobą, a napięcie zostaje podane na styk C. Następnie zespół przekaźników połączonych z każdym stykiem wyjściowym R sprawdza w tym samym czasie, czy na wszystkich wyjściach R pojawiło się napięcie. Jeśli tak, to zostało znalezione ustawienie bębnów, które zgodnie ze ściągą dokonuje szyfrowania C→R na podanych pozycjach.

Jeśli tak się nie stanie, to prawe bębny są obracane o jedną pozycję i test jest wykonywany ponownie. Po 26 pozycjach prawego bębna obracany jest o jedną pozycję bęben środkowy i operacja kontynuuje się aż do przetestowania wszystkich pozycji bębnów. Wtedy bębny są wymieniane w celu przetestowania innej ich kolejności lub układu. Proces ten wykonywany ręcznie jest bardzo czasochłonny i aż prosi się o automatyzację.

Można tego dokonać za pomocą silnika elektrycznego, który napędza w sposób synchroniczny wszystkie górne bębny, a następnie obracając co 26 pozycji bębny środkowe i dalej po przejściu 26 pozycji bębnów środkowych obracając bębny dolne. W ten sposób bębny mogą przejść przez wszystkie możliwe 17576 pozycji i można sprawdzić wystąpienie poprawnej pozycji dla podstawienia C→R według ściągi.

Jednakże test podstawienia C→R wciąż spełnia duża liczba pozycji bębnów szyfrujących.

Potrzebna jest zatem lepsza metoda znajdowania kolejności bębnów szyfrujących oraz ich ustawień.

Rozszerzeniem koncepcji par liter są kaskadowe zastąpienia liter w różnych miejscach ściągi, które dają w wyniku pętle literowe.

abcdefghijklmnopq JYCQRPRYDEMCJMRSR SPRUCHNUMMERXEINS ^ ^^

Na przykład R→N na pozycji g, N→S na pozycji p i S→R na pozycji q tworząc pętlę. Schemat pokazujący taką pętlę znany był pod nazwą menu. Jednakże w przypadku stosowania łącznicy wtyczkowej zamieniającej pary liter podstawienia wyglądały następująco:

R zamienione na S1 szyfruje się w S2 zamienione na N na pozycji g, N zamienione na S2 szyfruje się w S3 zamienione na S na pozycji p, S zamienione na S3 szyfruje się w S1 zamienione na R na pozycji q.

Problemem staje się teraz znalezienie pozycji rdzeni bębnów szyfrujących S1, S2 i S3. Jeśli da się je znaleźć, to będą one odpowiadały połączeniom na łącznicy wtyczkowej dla danych liter menu.

Turing zdał sobie sprawę, iż istniał jeszcze inny sposób konfiguracji połączonych ze sobą rozwartych maszyn Enigma, który w rezultacie umożliwił mu odkrycie połączeń łącznicy wtyczkowej.

Weźmy na przykład podaną powyżej pętlę literową R→N→S→R. Trzy rozwarte maszyny Enigma są ze sobą nawzajem połączone szeregowo, a dolne bębny zostają ustawione na przesunięcia g, p oraz q.

Jeśli zastosuje się właściwą kolejność bębnów szyfrujących, to wystąpi pewna startowa pozycja górnych, środkowych oraz dolnych bębnów odpowiadająca rzeczywistej pozycji rdzeni bębnów prawdziwej maszyny Enigma z uwzględnieniem różnicy pomiędzy oryginalnym nastawieniem pierścieni literowych a pozycją ZZZ. W tym momencie pozycje rdzeni bębnów będą takie same jak pozycje rdzeni w oryginalnej Enigmie, zatem szyfrowanie również będzie takie samo.

Oznacza to, iż napięcie elektryczne przyłożone do wejścia S1 pierwszej rozwartej Enigmy, które odpowiada zamianie na łącznicy wtyczkowej literki R, pojawi się na wyjściu S2, które odpowiada zamianie litery N na łącznicy. Ponieważ wyjście to połączone jest z kolejną rozwartą maszyną Enigma, prąd wchodzi przez wejście S2 i wychodzi na wyjściu S3 odpowiadającym zamianie litery S przez łącznicę wtyczkową. Wyjście S3 połączone jest z trzecią rozwartą maszyną Enigma - prąd wchodzi przez wejście S3 i wychodzi na wyjściu S1 odpowiadającym zamianie litery R. Stąd pozycja bębnów odpowiada pozycjom w rzeczywistej Enigmie, które szyfrują S1→S2→S3→S1.

Magiczna sztuczka polega na połączeniu wyjść ostatniej rozwartej maszyny Enigma z powrotem z wejściami pierwszej Enigmy. Powstaje teraz fizyczne połączenie przez rozwarte Enigmy od wejścia S1 do wyjścia S1 połączonego z wejściem S1. Tworzy to pętlę elektrycznych połączeń nie łączącą się z innymi wyjściami na żadnej z rozwartych maszyn Enigma.

Zatem jeśli napięcie zostanie przyłożone do wejścia S1, to prąd popłynie tylko przez wyjścia S1, S2 i S3. Jeśli ciąg 26 żarówek zostanie podpięty pomiędzy połączeniami rozwartych maszyn Enigma, to zaświecą się tylko lampki S1, S2 oraz S3 potwierdzając przepływ prądu przez styki S1, S2 i S3.

W tym miejscu pojawia się geniusz Turinga. Jeśli S1 nie jest znane a napięcie zostanie przyłożone powiedzmy do styku wejściowego A, to prąd ten przebiegnie przez wszystkie rozwarte maszyny Enigma ponieważ są one połączone wkoło wyjściami z wejściami, lecz nie trafi na ścieżkę pętli S1, S2 i S3, ponieważ nie łączy się ona z żadnymi innymi wyjściami. Prąd pobiegnie wzdłuż przewodów przez rozwarte maszyny Enigma aż do momentu, gdy osiągnie końcówkę z przyłożonym do niej napięciem. Wtedy ogromnie skomplikowana sieć połączeń elektrycznych osiągnie stabilny stan.

Teraz jeśli ciąg żarówek połączony jest z wyjściami i wejściami kolejnych rozwartych maszyn Enigma, to wiele z nich zaświeci się pokazując miejsca, gdzie prąd pojawił się na różnych wyjściach, lecz właściwe żarówki S1, S2 i S3 nie zaświecą się. W sprzyjających warunkach zaświeci się 25 żarówek. Nie zaświecone żarówki wskażą rdzenne litery S1, S2 lub S3. Będą one zinterpretowane jako wymiany przez łącznicę wtyczkową liter z menu.

Jeśli kolejność bębnów oraz ich pozycje są poprawne w porównaniu do pozycji w rzeczywistej maszynie Enigma, to istnieje tylko jedno połączenie przez wszystkie rozwarte Enigmy na stykach S1, S2 i S3. Jednakże Turing zauważył, iż taki system połączonych ze sobą rozwartych maszyn Enigma mógłby szybko odrzucać nieprawidłowe pozycje bębnów.

Jeśli bębny nie znajdują się w prawidłowej pozycji, to pętla S1, S2 i S3 nie istnieje i napięcie może się również przenosić na te końcówki. Stąd możliwe jest, iż napięcie pojawi się na wszystkich 26 stykach pomiędzy dwoma rozwartymi maszynami Enigma. Wynika z tego, iż nie istnieje możliwe połączenie na łącznicy wtyczkowej, a stąd ta konfiguracja bębnów szyfrujących nie może być prawidłowa. Lecz z powodu sposobu prowadzenia połączeń wewnątrz rzeczywistych bębnów szyfrujących Enigmy, zamknięte pętle mogą się pojawiać przy pozycji bębnów, które nie odpowiadają poszukiwanej właściwej konfiguracji łącznicy wtyczkowej. Układ rozwartych maszyn Enigma nie jest w stanie rozpoznawać takich mylnych pętli od pętli prawdziwej.

Test pętli możliwych połączeń na łącznicy wtyczkowej dla określonej kolejności bębnów szyfrujących i ich pozycji startowych polega na sprawdzeniu, czy tylko jedna z 26 żarówek nie jest zaświecona. Jeśli zaświeci się wszystkie 26 żarówek, to pozycja ta może być odrzucona, a odrzucenie to można wykonywać przy bardzo dużej prędkości. Prąd elektryczny biegnie po przewodach niemal z prędkością światła, zatem cała skomplikowana sieć połączeń elektrycznych osiąga stabilny punkt w ciągu zaledwie kilku mikrosekund. Potrzebny jest jedynie układ synchronicznej zmiany pozycji wszystkich bębnów oraz szybkiego wykrywania sytuacji odrzucenia danej pozycji.

Przekaźnik elektryczny

W roku 1939 jedyną dostępną techniką tworzenia połączeń elektrycznych w szybko zmieniających pozycje bębnach było zastosowanie małych szczotek z drucików, które stykały się z kontaktami stałymi na Tablicy Testowej. Technologię tę stosowano z powodzeniem w czytnikach kart perforowanych. Do wykrywania napięć na połączeniach w owym czasie można było jedynie zastosować szybkie przekaźniki. Testowano żarowe lampy elektroniczne, lecz te nie były wystarczająco niezawodne w roku 1939. Później z powodzeniem zastosowano gazowe tyratrony, które pracowały 1000 razy szybciej od najszybszych przekaźników.

Bomba kryptologiczna Victory

Firma The British Tabulating Machine Co (BTM) zaprojektowała rozwarte maszyny Enigma i zbudowała Tablicę Testową. Następnie pod kierownictwo H. H. Keena trafił projekt budowy kompletnej maszyny poszukiwawczej, zwanej Bombą. Maszynie nadano nazwę Victory (Zwycięstwo) i gotową dostarczono w marcu 1940 roku do tajnego ośrodka wywiadu w Bletchley Park. Początkowo zainstalowano ją w Pawilonie nr 1. Teraz rozpoczęto prace nad określeniem sposobu wykorzystania tego nowego urządzenia. Początkowo wyniki nie były zachęcające. Trudności w uzyskaniu ściąg oznaczały, iż po skonstruowaniu menu pomiędzy przechwyconym zaszyfrowanym tekstem a ściągą okazywało się zwykle, iż menu nie zawierało wystarczającej liczby pętli do zapewniających dobre odrzuty ustawień bębnów szyfrujących i maszyna zatrzymywała się przy olbrzymiej liczbie niepoprawnych pozycji.

Gordon Welchman

Gordon Welchman wymyślił tablicę przekątną opartą na prostej zasadzie, iż jeśli B jest zastępowane przez przełącznicę wtyczkową literą G, to z kolei G jest również zastępowane przez B. Jeśli umieścimy jeden nad drugim 26 rzędów 26-stykowych kontaktów, to dowolny punkt połączenia można opisać przez jego kolumnę i wiersz literowy. Prosty odcinek przewodu może teraz połączyć ze sobą element G w wierszu B z elementem B w wierszu G. Urządzenie to nazwano tablicą przekątną (ang. diagonal board), ponieważ ten odcinek przewodu był ułożony przekątnie w matrycy połączeń. Teraz konfiguracja rozwartej maszyny Enigma nic nie wie na temat zamiany liter przez łącznicę wtyczkową, Może jedynie wydedukować pozycje rdzeni bębnów szyfrujących zgodne z menu. Jednakże możliwe zamiany liter przez łącznicę wtyczkową, takie jak R↔S1 można wykryć za pomocą Tablicy Przekątnej. Jeśli połączenia pomiędzy rozwartymi Enigmami podłączone również zostaną do Tablicy Przekątnej na pozycji odpowiadającej parze oryginalnego szyfru i czystego tekstu z menu, to połączenie to może znacząco zwiększyć odrzucanie nieprawidłowych pozycji bębnów szyfrujących w rozwartych Enigmach.

Pokazaliśmy już, iż jeżeli dany zestaw pozycji bębnów szyfrujących zostanie znaleziony przy którym spełnione jest szyfrowanie S1→S2→S3→S1, to zostanie utworzone fizyczne połączenie pomiędzy kontaktami w rozwartych maszynach Enigmach na stykach S1, S2 i S3. Wynika z tego, iż R jest zamieniane przez łącznicę wtyczkową w S1 itd. Teraz jeśli połączenie reprezentujące literę R w menu zostanie podłączone do wiersza R Tablicy Przekątnej, to fizyczny odcinek przewodu  utworzy połączenie poprzez Tablicę Przekątną z wiersza R na pozycji S1 do wiersza S1 na pozycji R. Ponieważ wiersz S1 nie jest do niczego podłączony, to napięcie elektryczne już dalej nigdzie nie przejdzie z tego miejsca. Podobnie stanie się z pozostałymi połączeniami pomiędzy rozwartymi maszynami Enigma. Stąd Tablica Przekątna nie przeszkadza w znalezieniu poprawnej pozycji bębnów szyfrujących.

Lecz jeśli bębny szyfrujące znajdują się w niepoprawnej pozycji, która nie tworzy połączeń S1, S2 i S3, to napięcie elektryczne wędrujące po sieci przewodów pojawi się w końcu powiedzmy w wierszu N na pozycji S i zostanie przeniesione poprzez Tablicę Przekątną do wiersza S na pozycję N, co spowoduje dalszy przepływ prądu przez nowe fragmenty sieci elektrycznej w rozwartych maszynach Enigma po obu stronach połączenia S. Stąd Tablica Przekątna w znacznym stopniu przyczynia się do dalszego przepływu prądu w sieci przewodów wewnątrz maszyn Enigma ze względu na stworzenie dodatkowych połączeń. Zwiększa to odrzucanie niepoprawnych pozycji, które nie satysfakcjonują menu.