Úsvit hackerů: Bombe Alana Turinga

Vypočitatelná čísla

„Vyčíslitelná“ (resp. vypočitatelná – computable) jsou taková reálná čísla, jejichž desetinnou podobu lze spočítat konečnými prostředky. Přestože tématem této studie jsou na první pohled jen vyčíslitelná čísla, je možné v podstatě stejně jednoduše definovat a zkoumat vyčíslitelné funkce a celočíselné proměnné nebo skutečné vyčíslitelné proměnné, predikáty atd. Podstaty problému jsou ve všech případech stejné – zvolil jsem vyčíslitelná čísla jako příklad proto, že práce s nimi je nejméně těžkopádná. Věřím, že se mi podaří ve stručnosti představit a shrnout vzájemné vztahy vyčíslitelných čísel, funkcí atd., včetně rozvinutí teorie funkcí reálných proměnných vyjádřených prostřednictvím vyčíslitelných čísel. Jako vyčíslitelné označuji číslo, jehož podobu v desítkové soustavě může zapsat stroj.“

Univerzální výpočetní stroj

Je možné sestrojit samostatný stroj a využít jej k výpočtu libovolného vyčíslitelného zadání. Pokud je takový stroj U vybaven páskou, na jejímž začátku je zapsáno S.D (standardní definice tabulky akcí) výpočetního stroje S, pak U spočítá stejnou sekvenci jako S.“

Dva úryvky ze studie Alana Turinga „On computable numbers, with an application to the Entscheidungsproblem“, 1936

Mladý matematik

Mezi těmi, kdo v roce 1939 převzali v Bletchley Parku štafetu dešifrování zpráv a prolamování kódů stroje Enigma byla řada významných a nadaných osobností, jedno jméno ale přeci jen již od samého počátku vyčnívalo. Přestože na jeho doktorském diplomu z Princetonu sotva stačil oschnout inkoust (promoval v červnu 1938), byl sedmadvacetiletý Alan Turing považován za věhlasného matematika. Ostatně svou studii o vyčíslitelnosti (resp. vypočitatelnosti) čísel, v níž jaksi mimochodem navrhl moderní koncept počítače (včetně nastínění algoritmů), publikoval ve čtyřiadvaceti. Turing byl zkrátka skvělým příkladem toho, že skutečnou historii dělají, nebo přinejmenším ještě na počátku dvacátého století dělali, mladí lidé. Turingův osobní příběh se ale našeho seriálu týká spíše okrajově, případné zájemce proto odkáži na příslušné heslo na Wikipedii, nebo na článek Jana Kapouna.

Alan Turing v roce 1936

Turing nastoupil do Bletchley Parku 4. září 1939, přesně den poté, co Británie vyhlásila Německu válku. Jeho prvním úkolem bylo sestrojit zařízení pro luštění depeší kódovaných Enigmou – výchozím bodem byly plány geniální polské „Bomby“, kterou ale bylo třeba upravit a vylepšit, neboť Němci na počátku války opakovaně měnili postupy při šifrování a upravovali i samotné Enigmy. Svou verzi mechanického dešifrovacího přístroje nazval Turing „Bombe“.

Zvláštní oříšek představovaly zprávy námořnictva. Kriegsmarine totiž používala odlišný postup než Wehrmacht a Luftwaffe. Armáda a letectvo používaly knihy s denními klíči pro počáteční nastavení Engimy, které bylo dále upraveno klíčem pro přenos konkrétní zprávy volený operátorem (ten ale byl, jak jsme vysvětlili v jednom z předchozích dílů, až do roku 1940 přenášen na počátku zprávy dvakrát, což se ukázalo jako hlavní systémová chyba, nemluvě o řadě chyb z lenosti a lajdáctví, které jsme popisovali v minulém díle). Námořní zprávy byly nejprve šifrovány pomocí šifrovací knihy Kurzsignalheft, s níž se věty překládaly do několika čtyřpísmenných skupin. Kniha umožňovala snadno šifrovat údaje, jako byly pozice na mapě, jména přístavů, země, zbraně, počasí, lodě nepřítele, data, čas nebo logistické informace. Samotné klíče pro počáteční nastavení Enigmy byly v další knize, společně s klíčem pro zprávu, který si tak nevolil sám operátor.

Turingova Bombe

Turing se proto rozhodl, že se zaměří právě na námořní šifry. „Nikdo jiný se tomu nevěnoval a já tak mohl mít celou tu věc jen sám pro sebe“ prohlásil po válce. V prosinci 1939 rozluštil podstatnou část postupů pro počáteční nastavení a zároveň jej napadla nová technika, s jejíž pomocí bylo jednodušší prolomit námořní Enigmu. Turing nazval tento sekvenční statistický postup „Banburismus“. Využíval při ní metodu „Ban“ (angl. zákaz), díky které bylo možné vyloučit některé sekvence rotorů Enigmy a tak výrazně zkrátit dobu dešifrování zpráv pomocí Bombe – tu si ale nejdřív musel postavit a posléze i vylepšit.

Rekonstruovaná Bombe v muzeu v Bletchely Park

Připomeňme, že když v lednu 1939 zvýšili Němci počet propojení na rozvodné desce Engimy na deset a natolik zpomalili dešifrování pomocí původní Bomby, že se Poláci raději vrátili k ručnímu luštění zpráv, protože neměli kapacitu na postavení dalších padesáti či sta Bomb. Alan Turing proto Bombu upravil – jeho „Bombe“ byla navržena tak, aby využívala tzv. „Cribs“ – taháků, tedy slov, o nichž se předpokládalo, že jsou takřka v každé zprávě (například „pro“ jak jsme zmínili minule). Britské bomby byly také mnohem složitější a větší – šlo do nich umístit až sto „bubínků“ které odpovídaly stovce šifrovacích válců Enigmy, tedy 36 přístrojům Enigma. Celý kolos měl zhruba 2×2×0,6 metru a vážil necelou tunu. Výrazně rychleji pracovaly i vlastní válce – při rychlosti až 120 otáček za minutu u pozdějších modelů trvalo vyzkoušení všech 17 500 možných kombinací jednoho válce asi 20 minut.

První dvě bomby byly postaveny v březnu a srpnu 1940 a do konce roku se s jejich pomocí podařilo rozluštit většinu ze 178 zpráv. Do konce války Britové vyrobili přes 150 bomb typů Standard, Jumbo a Standard II emulujících/luštících Engimy se třemi válci (rotory) a asi sedmdesát bomb typu Mammoth a Cobra, které emulovaly/luštily čtyrválcové Enigmy. Zdaleka ne všechny ale byly umístěny v Bletchley Park – ten byl poměrně blízko Londýna a hrozilo tak poškození při náletech, přístroje byly proto instalovány na šesti různých lokalitách.

Prudce klesající úspěšnost německých ponorek v průběhu bitvy o Atlantik v roce 1941 přesvědčila admirála Karla Dönitze, že šifrování pomocí Engimy není patrně tak neprolomitelné, jak se v Německu obecně soudilo. Přesněji řečeno Dönitz si byl jist, že Britové přinejmenším část depeší rozluštili a přikázal proto, aby byly Ponorky (a posléze celé námořnictvo) vybaveno novým typem Enigmy „M4“ s kódovým označením Triton. Nový model měl namísto tří čtyři aktivní válce, celkový počet válců v sadě byl navíc zvýšen z pěti na osm a byly též vydány nové knihy s denními kódy. Skutečnost, že Dönitz nemohl nahradit všechny Enigmy naráz pomohla Turingovi, který záhy zjistil, že nový model M4 je zpětně kompatibilní – čtvrtý válec nové Enigmy totiž fungoval jako volič mezi dvaceti šesti různými reflektory a pokud byl nastaven v pozici A, chovala se Enigma M4 jako model M3 – a umožňovala tak komunikaci s loděmi, které měly starší model. Turing brzy přišel na zapojení čtvrtého válce a mohl tak postavit novou čtyřválcovou Bombu – bez námořního manuálu s denními klíči ale byla stejně většina zpráv nerozluštitelná. Zprávy Kriegsmarine tak byly od února do října 1942 (kdy se podařilo získat námořní knihy s klíči) pro Brity nečitelné a německé ponorky začaly opět slavit bojové úspěchy.

Bombe made in U.S.A.

Po svém vstupu do války přesvědčovali Američané Brity, aby s nimi sdíleli své vědomosti a znalosti prolamování Enigmy. Když se luštění zpráv Kriegsmarine v roce 1942 stalo díky novým Enigmám takřka nemožné, rozhodli se Britové ustoupit a prozradit svá (respektive polská) tajemství. Konstrukcí americké Bombe byl pověřen Joe Desch z National Cash Registers (NCR). Americké námořnictvo původně chtělo, aby bylo celé řešení čistě elektronické, nicméně to by vyžadovalo na 70 000 elektronek a tak byl nakonec zvolen elektromechanický kompromis, který se blížil původnímu britskému designu, byl ale výrazně rychlejší a spolehlivější. První prototypy byly postaveny v průběhu roku 1942 a již na konci roku 1943 bylo v provozu na 120 strojů. Vzhledem k jejich vyšší rychlosti a spolehlivosti se spojenci dohodli, že dešifrování zpráv Kriegsmarine, zejména komunikaci s ponorkami, budou mít na starost Američané.

Po úspěších britské a zejména americké Bombe (s jejíž stavbou pomáhal) pokračoval Alan Turing v práci na dalších šifrách – například Lorenzově, které se budeme věnovat v příštím díle. Na základě svých zkušeností z Bell Labs, které navštívil během cesty do USA navrhl Turing zařízení, které umožňovalo elektronicky šifrovat nahraný hlas (!). Nicméně jeho „Delilah“ byla dokončena pozdě na to, aby mohla být využita během války. Přitom systémy, které se jeho řešení využívající 30 elektronek mohly vyrovnat, se objevily až počátkem šedesátých let.

Po válce pracoval Turing na návrhu ACE – Automatic Computing Engine pro národní fyzikální laboratoř (NPL), ve své práci z února 1946 detailně popsal počítač s programem uloženým v paměti a podle některých by tak měl být za skutečného vynálezce moderního počítače být považován on a nikoliv Von Neumann (který svůj jednodušší návrh EDVAC publikoval sice dříve, ale s využitím některých Turingových myšlenek).

Epilog

Rozkvět Turingovy neobyčejně plodné vědecké činnosti byl náhle přerušen aférou, která se z dnešního pohledu jeví nepochopitelnou. Když v roce 1952 vyšetřovala policie krádež v jeho bytě, Turing naivně přiznal, že je gay a že krádeže se pravděpodobně dopustil jeden z jeho náhodných partnerů. Protože tato sexuální orientace nebyla v Anglii těch let tolerována, byl obviněn ze sexuálních přestupků. Záhy nato musel čelit jak soudnímu procesu, tak řadě urážlivých anonymů. Aféra způsobila, že byl zbaven bezpečnostního prověření.

Myšlenka, že by mohl začít spolupracovat s von Neumannem, se rozplynula, neboť nedostal vízum do Ameriky. Aby se vyhnul vězení, které mu za přečin hrozilo, přistoupil na hormonální léčbu. Ta mu ovšem způsobila značné zdravotní problémy a ve spojení se společenskou izolací, do níž se dostal, jen posilovala jeho deprese. V roce 1954 si uvědomil, že už není s to tomuto stavu čelit a v zoufalství se rozhodl ukončit život vlastní rukou. Ještě za studijních let viděl disneyovskou pohádku o Sněhurce, v níž je scéna s otráveným jablkem. Později přátelé vzpomínali, že o ní občas hovořil, ale nikoho nenapadlo, že se jí bude inspirovat. Jednoho červnového dne roku 1954, krátce přes svými dvaačtyřicátými narozeninami, ponořil jablko do kyanidu draselného, snědl několik soust a zemřel.

Upravený úryvek ze seriálu Jana Kapouna o osobnostech IT (CIO Business World).

Použité zdroje

• Alan Turing Internet Scrapbook
• Cryptomuseum
• Virtual wartime Bletchley Park
• Wikipedie: Alan Turing
• Wikipedie: Bombe
• CIO Business World: Alan Turing