14. októbra 2019
Dešifrovanie Enigmy

Enigma, časť 3/3: Stroje proti strojom

Prvá časť článku
Druhá časť článku

V tridsiatych rokoch sa Nemecko pripravovalo na vojnu. Zákopy a zúfalé útoky pechoty definujúce predchádzajúci konflikt boli nahradené rýchlymi koordinovanými presunmi motorizovaných jednotiek podporených letectvom. Takýto spôsob vedenia vojny si vyžadoval rýchlu a spoľahlivú šifrovanú komunikáciu. Tú mala Nemecku zabezpečiť Enigma. A Enigma sa zdala byť neprelomiteľná.

Čo však Nemci netušili bolo, že dešifrovanie Enigmy sa začalo skôr, ako padol prvý výstrel. Plány Enigmy vrátane detailov jej valcov obsahujúcich poprehadzovanú abecedu najskôr získali Francúzi, ktorí ich posunuli Poliakom. Bezpečnosť Enigmy však nebola skrytá v jej konštrukčných detailoch, ale v obrovskom množstve možných kľúčov, ktorými sa dali správy zašifrovať. Francúzi si to uvedomovali, preto sa o dešifrovanie ani nepokúsili. Poliaci si to uvedomovali tiež, okrem toho si ale tiež uvedomovali, že keď Nemecko zaútočí, budú prvou obeťou, preto sa do dešifrovania pustili.

Typická situácia v kryptografii je, že v princípe bezpečná šifra je kompromitovaná nerozvážnym používaním. [1] To bol aj prípad Enigmy a podstata poľského dešifrovania (kryptoanalýzy). Heslo Enigmy je zložené z troch častí: výber valcov, výber prepojení prepájacej dosky, počiatočné natočenie valcov. Tieto boli definované na každý deň v šifrovacích manuáloch. Aby sa však heslo neopakovalo, operátori si pre každú správu zvolili nejaké nové počiatočné natočenie valcov. Postup bol nasledovný: operátori Enigmu nastavili denným heslom. Tým zašifrovali heslo správy, teda počiatočné nastavenie valcov, teda tri písmená (napríklad FWS). Dvakrát. Aby znížili vplyv rádiového šumu a preklepov. Správa teda začínala textom FWSFWS zašifrovaným denným heslom. Operátori potom Enigmu nastavili na počiatočnú polohu valcov FWS a písali správu.

Dvojnásobné zopakovanie hesla správy vnieslo do prakticky náhodnej správy pravidelnosť, ktorej sa dalo chytiť. Presne tú využili kryptoanalytici poľskej informačnej služby zvanej Biuro Szyfrów [2]. Ak teda zachytená správa začínala písmenami YOXUEN, Poliaci vedeli, že Y a U zodpovedajú tomu istému písmenu po dvoch otočeniach tretieho valca Enigmy. Rovnako O s E a X s N. Dodajme, že zachytiť správy šifrované Enigmou bolo ľahké, vysielali sa totiž rádiom (v morzeovke) a počúvať ich mohol každý, kto si naladil správnu frekvenciu (používanie ľahko odpočúvateľného rádia bolo aj dôvodom pre hľadanie dobrého šifrovania). Takto mohli Poliaci získať denne veľké množstvo správ a teda aj dvojíc písmen vztiahnutých dvoma otočeniami tretieho valca.

Marian Rejewsky, mladý matematik zamestnaný v Biure Szyfrów si uvedomil, že dvojice písmen možno spojiť do cyklov. Napríklad z prvej správy máme Y -> U. Z ďalších správ môžeme vedieť napríklad U -> G, G -> M a M -> Y. Celý cyklus je potom Y -> U -> G -> M -> Y. Podobne pre vzťah druhého písmena správy s piatym a trietieho so šiestym. Počty cyklov a ich dĺžky boli jednoznačne určené poradím valcov a ich počiatočným natočením, spolu 105456 možností (prepájacia doska na cykly nemala vplyv). To znie ako veľa, avšak nie je to astronomické čislo ako počet všetkých možných nastavení so zahrnutím prepájacej dosky. Po roku skúšania všetkých možností bol hotový katalóg cyklov. Keď potom v Biure zo správ zachytených v jeden deň zistili cykly, vyhľadali, akému nastaveniu zodpovedajú a rozlúštili správy. Nastavenie prepájacej dosky zistili podľa slov, ktoré zrazu po výmene dvoch písmen začali dávať zmysel.

Biuro Szyfrów pracovalo aj na inej metóde využívajúcej fakt, že niektoré písmená sú v bežnom jazyku sú niektoré písmená častejšie ako iné, a ak zarovnáme pod sebou viacero správ, prekvapivo často sa stane, že v hornom aj dolnom riadku budú tie isté písmená. Hľadnie takýchto situácií sa dá mechanizovať a Poliaci, aby prelomili strojovú šifru, postavili stroje spracovávajúce jej správy. Tieto stroje sa nazývali bomby podľa tikavého zvuku, ktorý vydávali.

Zavedenie nových valcov zväčšilo počet možných kľúčov. Pokračovanie v kryptoanalýze bolo nad rámec zdrojov Biura. Poliaci preto oslovili Francúzov a Britov a predstavili im svoj projekt. Plány bômb boli prepašované z Poľska, pričom Francúzi opäť zohrali len úlohu spojky a z dešifrovania sa ospravedlnili. Briti však štafetu prevzali. Onedlho na to Nemecko vyhlásilo Poľsku vojnu a to rýchlo padlo.

Centrom Britských kryptoanalytických aktivít sa stalo vidiecke sídlo Bletchley Park a vďaka poľským úspechom sa okamžite stalo továrňou na informácie. Postupne zamestnávalo vyše 10 tisíc ľudí a ako v mnohých iných továrňach počas vojny, väčšinu pracovnej sily tvorili ženy. V Bletchley predstavovali asi tri štvrtiny personálu a obzvlášť významné boli Ženy britskej námornej služby (Women of Royal Naval Service, WRNS, prezývané wrens, teda oriešky [3]). Okrem nich sa tam stretli vedci od lingivstov po matematikov, majstri v šachu a iných hrách a neskôr aj ľudia, ktorí vyriešili tajnou službou zverejnené novinové krížovky [4].

Asi najvýraznejšou postavou, ako svojou excentrickosťou, tak aj nadaním pre šifry bol matematik Alan Turing. Pracoval na hľadaní novej metódy dešifrovania Enigmy (keby Nemci zmenili svoje operačné postupy),
koordinoval spoluprácu s Američanmi a tiež konzultoval rôzne iné projekty (metódu dešifrovania inej nemeckej strojovej šifry nazvali podľa neho turingizmus). Ako sa čoskoro ukázalo, Nemci operačné postupy zmenili a nová metóda bola nutná.

Medzitým však Briti nazbierali a dešifrovali obrovské množsvo správ. Tak sa dozvedeli veľa o tom, ako sa Enigma používala. A keby neboli Britmi ale nemeckou inšpekciou, nepotešili by sa. Množstvo správ, ktoré museli operátori denne posielať spôsobilo, že si hľadali skratky. Kódy správ často opakovali (rôzni operátori mali svoje obľúbené kódy, predpokladá sa, že iniciály priateliek) alebo používali naivné kombinácie kláves ako napríklad QWE. (Ľudský mozog nie je dobrý generátor náhodných písmen.) Operačné manuály nepomáhali: dva dni po sebe nemohli byť použité tie isté valce a na prepájacej doske nemohli byť spojené za sebou nasledujúce písmená (tieto zdanlivé vylepšenia len zmenšili počet možných kľúčov). Správy tiež vykazovali vojenskú strohosť a šablónovitosť, obsahovali tie isté frázy, každý deň o tom istom čase sa vysielali správy o počasí a podobne. [5]

Turing využil práve poslednú spomínanú slabinu. Tipol si, že správa bude obsahovať nejaké slovo (napríklad Wetter, teda počasie). Tipol si, kde sa bude nachádzať. Polohu hľadanej správy výrazne pomohla určiť konštrukcia reflektora. Ten totiž spôsoboval, že písmeno nemohlo byť zašifrované samé do seba. To znamená, že ak šifrovaný text obsahoval sekvenciu DECTDSANV, slovo Wetter nemohlo byť zašifrované takto:
wEtTer
dEcTdsanv
(prvé E a druhé T sú zašifrované do E a T), ani takto
_weTter
decTdsanv
(prvé T je zašifrované do T),
ale takto už áno:
__wetter
dectdsanv

Po nájdení pozície slova bolo treba “už len” zistiť nastavenie Enigmy. Turing a jeho kolega Gordon Welchman to, podobne ako Poliaci, vyriešil strojovo. Britské bomby obsahovali niekoľko za sebou zapojených Enigiem, navzájom posunutých o jedno pootočenie valcov. Valce týchto Enigiem sa postupne otáčali a keď sa dostali do správnej polohy, Enigmy vytvorili uzavretý elektrický obvod, ktorým prešiel prúd a zasvietil žiarovku. Takýchto sústav Enigiem bolo v jednej bombe niekoľko, líšili sa výberom a poradím valcov. Nastavením prepínacej dosky nemalo vplyv na fungovanie tejto metódy, takže astronomický počet možných prepojení dešifrovanie neznemožnil. Prepojenia sa opäť získali hľadaním zmysluplných slov po vyriešení valcov. Dešifrovanie takouto metódou trvalo niekoľko hodín.

Čítanie Enigmy poskytlo Britom významnú strategickú výhodu a ak neviedlo priamo k víťazstvu vo vojne, určite ju skrátilo a znížilo počet obetí.

Nástup strojových šifier a strojovej kryptoanalýzy zmenil kryptografiu, ktorá sa presunula z humanitných katedier (lingvistika) do matematiky a novovznikajúcej informatiky [6]. Práca v Bletchley Parku poskytla jej účastníkom okno do budúcnosti informačných technológií a výpočtových strojov. Vojnové riziko spôsobilo, že Bletchley Park dokázal dodávať zázraky na počkanie, okrem iného prvý programovateľný “počítač”, stroj Colossus používaný na turingizmus. Povojnový vývoj počítačov bol často brzdený rozchádzajúcimi sa názormi na ich konštrukciu a osobnými ambíciami.

Hrdinovia z Bletchley si však na slávu museli dlho počkať. Všetko, čo sa tam dialo, zostalo po vojne utajené (zrejme aj z dôvodu, že Británia Enigmy zhabané Nemcom “veľkoryso” rozdelila medzi svoje kolónie). Dokumenty boli odtajnené až v 70. rokoch a zverejnené v roku 1974 v knihe Ultra tajné (The Ultra Secret) [7]. Marian Rejewsky utiekol z napadnutého Poľska do Británie, kde opäť pracoval na lúštení šifier, avšak nie v Bletchley Parku a o tom, do čoho vyústil jeho projekt sa dozvedel až z tejto knihy. Istý mladý kryptoanalytik dostal po vojne list od riaditeľa svojej školy, v ktorom ho označil za hanbu školy, pretože nebojoval na fronte. Alan Turing bol odsúdený za svoju homosexualitu, nútený podstúpiť hormonálnu terapiu a neskôr, v roku 1954 vo veku 41 rokov spáchal samovraždu.

[Lukáš]

Poznámky:

Dobrými zdrojmi o dešifrovaní Enigmy sú knihy
Simon Singh: The Code Book (Kniha kódov a šifier)
Andrew Hodges: Alan Turing: The Enigma (životopis Alana Turinga)
no a samozrejme obrovské množstvo internetových zdrojov, napríklad:
https://www.youtube.com/watch?v=V4V2bpZlqx8
a tiež rozsiahly článok na wikipédii s množstvom ďalších odkazov na všetky použité kryptoanalytické metódy
https://en.wikipedia.org/wiki/Enigma_machine

Enigma a jej dešifrovanie sa stalo populárnou témou aj v beletrii a filme, napríklad:
Robert Harris: Enigma (a rovnomenný film)
film The Imitation Game (Kód Enigmy)
Neal Stephenson: Cryptonomicon (Kryptonomikon, môj osobný tip)

– – –

– – –

[1] Pancierové bezpečnostné dvere nepomôžu, keď sú osadené v sadrokartónovej stene, kľúče pod rohožkou a okno otvorené. Silné šifrovanie nepomôže, keď sú tajné správy zálohované v mobile pod slabým heslom. A tak ďalej.
[2] Po poľsky znie všetko akosi lepšie. O operačných praktikách Enigmy vedeli vďaka sieti špiónov.
[3] Vtáky, nie suché plody.
[4] Winston Churchill to okomentoval slovami: “Keď som vám povedal, že máte hľadať pod každým kameňom, nemyslel som to doslova.”
[5] I keď to vo filme Imitation Game vyznelo vtipne, nacistický pozdrav takouto populárnou frázou nebol.
[6] Navyše sa ukázalo, že aj tie najčistejšie oblasti matematiky môžu mať vojenské využitie, niečo čo slávny matematik G.H. Hardy v knihe A Mathematicians Apology (Matematikova obhajoba) považoval za nemožné.
[7] Ultra bol krycí názov pre informácie získané z čítania Enigmy.

One thought on “Enigma, časť 3/3: Stroje proti strojom

Pridaj komentár