Biblioteka
  Wiw.pl   Na bieżąco:  Informacje   Co nowego   Matematyka i przyroda:  Astronomia   Biologia   Fizyka   Matematyka   Modelowanie rzeczywistości   Humanistyka:  Filozofia   Historia   Kultura antyczna   Literatura   Sztuka   Czytaj:  Biblioteka   Delta   Wielcy i więksi   Przydatne:  Słowniki   Co i gdzie studiować   Wszechświat w obrazkach    
  Jesteś tutaj:   Wirtualny Wszechświat > Biblioteka > Matematyka > ENIGMA  



[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10] 
Bomba Turinga

Przypuśćmy, że w pełnej Enigmie z łącznicą szyfrem słowa GENERAL jest z całą pewnością ciąg LAKNQKR. Tym razem nie warto poszukiwać tego ciągu na układzie podstawowych Enigm i sprawdzać, co się otrzymuje na wyjściu, ponieważ przed wprowadzeniem słowa na wirniki zastosowano na łącznicy pewne nieznane podstawienie. Mimo to można podjąć pewne działania. Rozważmy tylko jedną literę, mianowicie A. Łącznica może ją przekształcić na 26 sposobów, warto więc pomyśleć o sprawdzeniu wszystkich. Zacznijmy, na przykład, od przyjęcia hipotezy (AA), tzn. od przypuszczenia, że łącznica pozostawia tę literę niezmienioną.

Teraz należy wykorzystać fakt, że maszyna zawiera tylko jedną łącznicę, wykonującą taką samą zamianę liter przed ich wpuszczeniem na wirniki, jak i po. (Gdyby Enigmę wyposażono w dwie łącznice - jedną zamieniającą wprowadzane litery i drugą dokonującą podstawień na literach wychodzących - sprawa wyglądałaby zupełnie inaczej). Można także wyciągać pewne wnioski z tego, że nasza przykładowa ściągawka ma pewną szczególną właściwość - zamkniętą pętlę. Łatwo to widać, gdy dostrzeże się konsekwencje założenia (AA).

Popatrzmy na drugą literę ciągu: wprowadzamy A na wirniki Enigmy i otrzymujemy na wyjściu, powiedzmy, O. Oznacza to, że łącznica musi realizować podstawienie (EO).



Teraz zajmijmy się czwartą literą w ciągu. Istnienie podstawienia (EO) niesie pewną implikację dla N, na przykład (NQ); dalej, trzecia litera daje pewną implikację dla K, powiedzmy (KG).


Rozważmy wreszcie szóstą literę: tu pętla się zamyka i można ustalić albo zgodność, albo sprzeczność między wnioskiem (KG) i pierwotną hipotezą (AA). Jeśli zachodzi drugie, to hipoteza musi być fałszywa, więc należy ją odrzucić.

Metoda była daleka od ideału, zależała bowiem całkowicie od wystąpienia w ściągawce zamkniętej pętli - a nie w każdym przypadku musiało tak się zdarzyć11. A jednak działała - dzięki temu, że zasada uzupełniania do pełnej pętli dawała się łatwo przetłumaczyć na język obwodów elektrycznych. Wskazywało to na możliwość pokonania bariery, jaką stanowiła duża liczby możliwych połączeń w łącznicy.

Tak wyglądał początek prac i tak pojawił się pierwszy sukces Alana. Podobnie jak w przypadku większości poszukiwań czasu wojny, praca wymagała nie tyle najnowszej wiedzy naukowej, ile tej szczególnej umiejętności, jaka jest potrzebna do prowadzenia zaawansowanych badań, którą tu należało zastosować do zagadnień bardziej elementarnych. Pomysł automatyzacji procesów nikogo już w XX wieku nie zaskakiwał, nie wymagał nawet udziału autora "Liczb obliczalnych", natomiast niezwykle istotne dla sprawy okazało się jego poważne zainteresowanie maszynami matematycznymi, jego fascynacja wykonywaniem działań w postaci maszynowej [Bomba nie miała jednak nic wspólnego z uniwersalną maszyną Turinga. Ogólniejsza od polskiej Bomby, nie zależała co prawda od określonego systemu wskaźników, lecz pod każdym innym względem była jak najdalsza od jakiejkolwiek uniwersalności. Przystosowana do układu elektrycznego Enigmy, wymagała bezwzględnie dokładnej ściągawki]. Odnoszące się do łącznicy warunki "sprzeczności" i "zgodności" składały się na problem jak najbardziej skończony, daleki od tego, o czym mówiło twierdzenie Gödla, czyli od nieskończonej różnorodności teorii liczb. Mimo to rzucała się w oczy analogia z formalistyczną koncepcją matematyki, w ramach której implikacje powstają w ramach procesów mechanicznych.

Alanowi udało się ująć tę koncepcję w projekcie nowej Bomby na początku 1940 roku. Rozpoczęto praktyczną realizację konstrukcji w zakładach British Tabulating Manufacture w Letchworth; pod kierownictwem Harolda "Doca" Keena odbywało się to z szybkością niewyobrażalną w czasach pokoju. Dotychczas pracownicy fabryki trudnili się wytwarzaniem biurowych arytmometrów i sortowników, w których przekaźniki służyły do wykonywania prostych funkcji logicznych, takich jak dodawanie czy rozpoznawanie. Teraz musieli zająć się produkcją przekaźników potrzebnych do rozpoznawania przez Bombę zgodnych ze wzorcem położeń wirników i zatrzymania maszyny. I znów Alan był najodpowiedniejszą osobą do określenia owych potrzeb, gdyż dzięki doświadczeniu z przekaźnikową maszyną mnożącą poznał problemy związane z realizacją operacji logicznych przez tego rodzaju maszyny. Przypuszczalnie w 1940 roku nikt inny nie nadawał się lepiej do kierowania takimi pracami niż on.

A jednak nawet Alan nie zauważył, że do projektu można wprowadzić radykalne usprawnienie. Tu zasadniczą rolę odegrał Gordon Welchman. Dołączając do grupy kryptoanalityków, którzy pracowali nad Enigmą, miał za sobą poważne osiągnięcie: sam wymyślił metodę arkuszy dziurkowanych, nie wiedząc, że Polacy opracowali ją wcześniej i że Jeffries właśnie je produkował. Ponadto jednak, badając projekt Bomby Turinga, zauważył, że nie wykorzystuje ona do końca słabości Enigmy.

Powróćmy do schematu Bomby Turinga: widzimy, że pozostały jeszcze inne, niewykorzystane implikacje, wskazane na rysunku przez linie pogrubione:


Od poprzednich różnią się one tym, że nie można było ich przewidzieć. Wynikają z tego, iż podstawienie (KG) jest tym samym, co (GK), a więc wpływa na L na pierwszym miejscu. Podobnie podstawienie (NQ) oznacza także (QN), stąd jego związek z literą R na piątym miejscu, co z kolei wpływa na los litery L na miejscu siódmym. Oczywiście, zachodzi możliwość, że niezależnie od zamknięcia pętli na miejscu szóstym, nowe implikacje doprowadzą do sprzeczności. Tak więc wystąpienie sprzeczności nie wymaga już wystąpienia pętli w tekście, natomiast zwiększone możliwości wnioskowania wymagają instrumentów pozwalających przechodzić automatycznie od (KG) do (GK) i podobnie dla każdej innej uzyskanej implikacji - bez informacji o tym, kiedy i gdzie to przejście może się okazać konieczne.

Welchman nie tylko dostrzegł możliwość usprawnień, lecz szybko rozwiązał problem uwzględnienia owych dalszych implikacji w zmechanizowanym procesie. Wymagało to tylko prostego elementu obwodu elektrycznego - nazwanego niebawem tablicą przekątniową. Nazwa odnosiła się do macierzy 676 końcówek elektrycznych, rozstawionych w kwadracie 26 x 26, z których każda odpowiada pewnemu podstawieniu, na przykład (KG); przy czym przewody biegną po przekątnych, łącząc na stałe, na przykład, (KG) z (GK). Podłączenie owej tablicy przekątniowej do Bomby pozwoliło osiągnąć zamierzony efekt. Nie wymagało to żadnych przełączników; kolejne implikacje można było nadal otrzymywać w wyniku nieomal natychmiastowego dopływu prądu do podłączonego obwodu.

Welchman z trudem mógł uwierzyć, że udało mu się rozwiązać problem, ale naszkicował schemat elektryczny i przekonał się, iż wszystko będzie działać jak należy. Spiesząc do Chatki, pokazał go Alanowi, na początku także niedowierzającemu, lecz po krótkiej chwili równie jak autor pełnemu entuzjazmu wobec otwierających się nowych możliwości. Postęp rysował się wyraźnie; szukanie pętli przestało być konieczne, wystarczyło dysponować mniejszą liczbą krótszych ściągawek.

Dzięki tablicy przekątniowej Bomba nabrała niemal tajemniczej elegancji i mocy. Każde uzyskane twierdzenie, powiedzmy (BL), owocowało wnioskami dotyczącymi każdego wystąpienia liter B i L tak w tekstach otwartych, jak i w zaszyfrowanych. Czterokierunkowe rozprzestrzenianie się wniosków na każdym etapie pracy Bomby pozwalało ograniczyć się do ściągawek złożonych z trzech lub czterech słów. Analityk mógł wybrać z ciągu tworzącego ściągawkę zestaw złożony z około dziesięciu liter - niekoniecznie zawierający pętlę, ale z odpowiednio dużym udziałem liter, które prowadziłyby do wniosków odnoszących się do innych liter. To z kolei dostarczałoby bardzo mocnego warunku zgodności, dzięki któremu odrzucenie miliardów fałszywych hipotez przebiegałoby z prędkością światła.

Zasada bardzo sugestywnie kojarzyła się z regułami logiki matematycznej, gdzie szuka się jak największej liczby wniosków, które wynikają z zadanego zbioru interesujących aksjomatów. W procesie dedukcji także kryła się pewna logiczna subtelność. Jak się przekonaliśmy do tej pory, operacja wymagała sprawdzania za każdym razem jednej hipotezy łącznicowej. Jeśli uzyskana sprzeczność nakazywała odrzucić hipotezę (AA), sprawdzano (AB) itd., aż do wyczerpania wszystkich 26 możliwości. Dopiero wtedy przesuwano wirniki o jeden krok i w taki sam sposób badano nowe ustawienia. Alan zauważył, że tak być nie musi.

Jeśli (AA) prowadzi do sprzeczności, to na ogół w procesie śledzenia wszystkich implikacji dochodzi się do (AB), (AC) itd. Oznacza to, że wszystkie te hipotezy są także wewnętrznie sprzeczne, nie ma zatem potrzeby ich ponownego badania - z jednym wyjątkiem: gdy ustawienie wirników jest dobre. W tym przypadku albo hipoteza łącznicowa jest również poprawna i nie prowadzi do sprzeczności, albo jest niepoprawna i wnioskowanie na jej podstawie kończy się każdym innym twierdzeniem oprócz poprawnego. W rezultacie Bomba się zatrzymuje, gdy prąd elektryczny dotarł albo do dokładnie jednej końcówki, albo do dokładnie 25 spośród 26 końcówek. Taki właśnie dość skomplikowany warunek należało sprawdzić za pomocą przekaźników. Nie było to bynajmniej oczywiste, ale uświadomienie sobie tej możliwości dwudziestosześciokrotnie przyspieszyło proces. Alan przywoływał tu podobieństwo do logiki matematycznej, gdzie z jednej sprzeczności wynika każde zdanie. Wittgen-stein, omawiając tę kwestię, twierdził, że sprzeczności nigdy jeszcze nie sprawiły nikomu kłopotu. Ale te sprzeczności miały sprawić wiele kłopotu Niemcom i doprowadzić do burzenia mostów.

Tak więc cudownie prosta logiczna zasada Bomby polegała na doprowadzeniu implikacji do samego końca. Niestety, konstrukcja maszyny nie miała w sobie nic z prostoty. Aby zapewnić praktyczną użyteczność Bomby, sprawdzenie przeciętnie pół miliona ustawień wirników musiałoby zajmować kilka godzin, co oznaczało z kolei, że w każdej sekundzie należałoby zastosować proces logiczny do co najmniej 20 hipotetycznych ustawień. Mieściło się to w ramach technicznych możliwości urządzeń realizujących automatyczne połączenia telefoniczne, które potrafiły dokonać przełączenia w czasie tysięcznych części sekundy. W odróżnieniu jednak od przekaźników w centralach telefonicznych składniki Bomby musiałyby funkcjonować w sposób ciągły i w pełni zgodny, przez kilka godzin bez przerwy, z wirnikami współpracującymi absolutnie synchronicznie. Bez rozwiązania tych problemów inżynierskich - i to w czasie, który w normalnych okolicznościach wystarczałby zaledwie do sporządzenia wstępnego projektu - wszystkie pomysły logiczne pozostałyby w sferze marzeń.

Projekt Bomb, a nawet jego bliska realizacja nie wystarczały do rozwiązania problemu Enigmy. Bomba nie była w stanie przejąć wszystkich zadań wynikających z przyjęcia metody prawdopodobnego słowa. Jedno z istotnych utrudnień brało się stąd, że gdy w wyniku spełnienia warunków zgodności maszyna się zatrzymywała, nie musiało to wcale oznaczać, iż otrzymano prawidłową konfigurację wirników, takie zatrzymanie bowiem mogło być dziełem przypadku. (Obliczenie częstości, z jaką należało się spodziewać przypadkowych zatrzymań, samo w sobie stanowiło ciekawe zastosowanie rachunku prawdopodobieństwa). Każde zatrzymanie wymagało sprawdzenia na Enigmie, czy w danym ustawieniu przetworzy ona resztę zaszyfrowanego tekstu w poprawny tekst niemiecki - i tak aż do wykrycia prawidłowego ustawienia wirników.

Odgadywanie prawdopodobnego słowa i dopasowanie go do zaszyfrowanego komunikatu także trudno uznać za zadanie trywialne. Co gorsza, dobry szyfrant mógł uniemożliwić obie operacje. Mądre korzystanie z Enigmy, jak z każdej maszyny szyfrującej, polegało na chronieniu jej przed ewentualnym atakiem metodą prawdopodobnego słowa. Wystarczyłyby sposoby tak oczywiste, jak dopisywanie na początku każdego przekazu pewnej nie ustalonej z góry liczby losowo dobranych słów bezsensownych, umieszczanie w długich słowach dodatkowej litery X, "maskowanie" standardowych lub powtarzających się składników komunikatu czy, mówiąc ogólniej, korzystanie z systemu w sposób tak nieprzewidywalny, tak daleki od mechanicznych prawidłowości, jak tylko jest to możliwe bez utraty dostępności tekstów dla uprawnionego nadawcy. Gdyby stosowano się sumiennie do tych zasad, odkrycie dokładnych ściągawek koniecznych do działania Bomby stałoby się niemożliwe. Użytkownicy Enigmy sądzili jednak zapewne, że maszyna w wystarczającym stopniu sama zadba o siebie, i dzięki temu natrafiano często na regularności ułatwiające pracę brytyjskim kryptoanalitykom.

Wszakże nawet pokonanie subtelności tego rodzaju i opanowanie sztuki odgadywania słów z doskonałą dokładnością nie kończyło sprawy. Odczytanie jednego komunikatu na pewno nie pomogłoby w wygraniu wojny. Chodziło o to, by rozwiązać wszystkie komunikaty, a napływały ich codziennie tysiące z każdej sieci. Problem dotyczył zatem systemu szyfrowego jako całości. W systemie tak prostym, jak przedwojenne powtarzane trójki liter wskaźnikowych, jeden rozwiązany komunikat mógł doprowadzić do rozpoznania całego procesu, odnalezienia ustawień początkowych i w konsekwencji przejęcia całej korespondencji. Trudno jednak oczekiwać od nieprzyjaciela, że zechce tak bardzo ułatwić zadanie swojemu wrogowi. Co więcej, powstawało swego rodzaju błędne koło, gdyż proces odgadywania słowa z prawdopodobieństwem bliskim pewności stawał się możliwy jedynie przy dostatecznej wiedzy o całym ruchu korespondencyjnym. Niewielki byłby pożytek z Bomby, gdyby wcześniej nie udało się dokonać wyłomu w korespondencji w jakiś inny sposób.

W przypadku sygnałów Luftwaffe taki inny sposób istniał - metoda arkuszy dziurkowanych, sprawdzona na dziewięcioliterowym systemie wskaźników. Jesienią 1939 roku zakończono przygotowania sześćdziesięciu arkuszy i kopię zestawu zawieziono francuskim kryptoanalitykom do Vignolles. Był to akt nadziei. Od grudnia 1938 roku nie rozwiązano żadnego przekazu Enigmy, nie było zatem pewności, czy prawie rok później arkusze okażą się jeszcze przydatne. Nadzieja nie była pozbawiona podstaw, albowiem:

"Pod koniec roku - zapisano w GCCS - nasz emisariusz przywiózł wspaniałą wiadomość, że na [...] arkuszach, które zabrał ze sobą, złamano klucz (28 października, Zielony [Welchman, którego pierwsze zadanie polegało na identyfikacji różnych systemów kluczy, określał je nazwami kolorów. I tak, system ogólnego przeznaczenia w Luftwaffe nazywał się Czerwony, termin Zielony określał system stosowany w krajowym dowództwie Wehrmachtu. Mimo wymienionych w sprawozdaniu sukcesów, Zielony okazał się przykładem prawie całkowicie nierozwiązalnego systemu Enigmy, stosowano go bowiem zgodnie z wszelkimi zasadami ostrożności]). Natychmiast zabraliśmy się do pracy nad kluczem (25 października, Zielony) [...]; ten pierwszy w okresie wojny klucz Enigmy, jaki pojawił się w tym kraju, złamano na początku stycznia 1940". Dalej sprawozdanie GCCS stwierdza: "Czy w nowym roku Niemcy dokonali zmian w maszynie? Podczas gdy my czekaliśmy [...] złamano kilka innych kluczy z 1939 roku. Wreszcie nadszedł pomyślny dzień [...] Ułożono arkusze [...] i Czerwony został wyeliminowany. Niebawem to samo stało się z innymi kluczami".

Los nadal im sprzyjał i arkusze dziurkowane umożliwiły pierwsze włamanie do systemu. Tak jak w polowaniu na skarby w Princeton, każdy sukces dawał wskazówki prowadzące do następnego celu, do szybszego i pełniejszego dekryptażu. Specjalne metody, takie jak metoda arkuszy - a stosowano także wiele innych metod algebraicznych, lingwistycznych i psychologicznych - otwierały drogę do lepszych wyników. Nigdy jednak nie można było spocząć na laurach, ponieważ zasady zmieniały się co chwila i należało działać tak szybko, jak tylko się dało, by nie stracić dystansu. Nadążali z trudem - gdyby spóźnili się o kilka miesięcy, mogliby nigdy więcej nie dogonić przeciwnika. Szczególnie niebezpieczna była wiosna 1940 roku, gdy utrzymali się w wyścigu dzięki mieszance pomysłowości i intuicji - lub, jak to określali wojskowi, dzięki cholernym domysłom.

U podstaw ówczesnych brytyjskich działań leżały domysły i nadzieje. Rząd niewiele więcej wiedział o tym, jak wygrać wojnę, ani nawet o tym, co się na niej działo, niż zwyczajni obywatele. Wyglądało to tak, jakby siły zbrojne Wielkiej Brytanii i Niemiec uzgodniły w końcu, że znów stoczą bitwę, ale brytyjski Tweedledee wyraźnie nie miał ochoty zacząć pierwszy, podczas gdy niemiecki Tweedledum liczył na to, że o szóstej po południu będzie już po wszystkim. Uzbrojenie Tweedledee wciąż zalegało w ukryciu pod parasolem Chamberlaina. Czerwony Król chrapał na wschodnim polu i nikt (nawet w Bletchley) nie wiedział, o czym śni. Blokada miała doprowadzić już "powalone" Niemcy do rozpadu wewnętrznego, jeśli tylko Wielka Brytania "przetrzyma". Wśród brytyjskich władców na w pół oczekiwano, na w pół lękano się ponownego przybycia Potwornego Kruka, zagadkowo rozpościerającego skrzydła po drugiej stronie Atlantyku.

Komunikaty Luftwaffe, tak pracowicie i tak dużym kosztem odszyfrowywane w Bletchley w marcu 1940 roku, zawierały, jak się okazało, głównie dziecięce wierszyki, przesyłane w ramach ćwiczeń. Nawet tam, gdzie czas wypełniała pasjonująca praca, panowało często poczucie iluzoryczności i zawodu. Podobnie było w Cambridge. Alan wracał tam od czasu do czasu w wolne dni, by popracować trochę nad matematyką i spotkać się z przyjaciółmi. W King's wszyscy sumiennie zbierali się w schronach przeciwlotniczych (z wyjątkiem Pigou, który odmówił podporządkowania się Luftwaffe), lecz zapowiadane bombardowania nie następowały. W połowie 1940 roku trzy czwarte dzieci ewakuowanych do Cambridge powróciło już do domu.

[1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10] 
[  góra strony  ]

Wiw.pl  |  Na bieżąco  |  Informacje  |  Co nowego  |  Matematyka i przyroda  |  Astronomia  |  Biologia  |  Fizyka  |  Matematyka  |  Modelowanie rzeczywistości  |  Humanistyka  |  Filozofia  |  Historia  |  Kultura antyczna  |  Literatura  |  Sztuka  |  Czytaj  |  Biblioteka  |  Delta  |  Wielcy i więksi  |  Przydatne  |  Słowniki  |  Co i gdzie studiować  |  Wszechświat w obrazkach