Rejewského strategie útoku na Enigmu vycházela ze skutečnosti, že opakování je nepřítelem bezpečnosti: opakování vede k zákonitostem, jež pak mohou kryptoanalytici luštit. Nejnápadnějším opakováním byl v případě Enigmy klíč zprávy, zašifrovaný vždy dvakrát na začátku každé zprávy. Pokud operátor zvolil klíč ULJ, pak jej musel zašifrovat dvakrát, ULJULJ převedl na PEFNWZ a tuto sekvenci odeslal na počátku vlastní zprávy. Němci trvali na opakování, aby se vyhnuli chybám způsobeným překlepem nebo rádiovou interferencí. Nepředvídali však, že tak mohou ohrozit bezpečnost komunikace.
Rejewski každý den dostal nový balík zachycených zpráv. Všechny začínaly šesti písmeny opakovaného třípísmenného klíče zprávy, všechny byly zašifrovány podle téhož dohodnutého denního klíče. Tak například mohl obdržet čtyři zprávy, které začínaly následujícími zašifrovanými klíči zprávy:
1. 2. 3. 4. 5. 6.
První zpráva L O K R G M
Druhá zpráva M V T X Z E
Třetí zpráva J K T M P E
Čtvrtá zpráva D V Y P Z X
V každé z těchto zpráv vzniklo první a čtvrté písmeno zašifrováním téhož písmene, a to prvního písmene klíče zprávy. Také druhé a páté písmeno jsou zašifrováním téhož písmene, a to druhého písmene klíče zprávy. I třetí a šesté písmeno jsou zašifrováním téhož písmene, a to třetího písmene klíče zprávy. Například v první zprávě jsou L a R zašifrováním téhož písmene, prvního písmene klíče zprávy. Stejné písmeno je zašifrováno různě, poprvé jako L a potom jako R, z toho důvodu, že se mezi dvěma šifrováními první scrambler Enigmy posunul o tři kroky a změnil tak celkový způsob šifrování.
Skutečnost, že L a R jsou zašifrováním téhož písmene, umožnila Rejewskému vyvodit drobná omezení týkající se počátečního nastavení přístroje. Počáteční neznámé nastavení scramblerů zašifrovalo první písmeno denního klíče, který je také neznámý, jako L. Další nastavení scramblerů, tři kroky od původního nastavení, které je stále neznámé, zašifrovalo týž znak jako R.
Takové vymezení se může zdát mlhavé, protože je plné neznámých, ale přinejmenším to dokazuje, že písmena L a R jsou těsně spojena původním nastavením přístroje Enigma, denním klíčem. S každou další zachycenou novou zprávou lze identifikovat další vztahy mezi prvním a čtvrtým písmenem opakovaného klíče zprávy. Všechny tyto vztahy jsou odrazem počátečního nastavení Enigmy. Například druhá zpráva (viz výše) nám říká, že písmena M a X jsou v určitém vztahu, třetí řádek napovídá, že stejná závislost existuje mezi J a M, a čtvrtá zpráva ukazuje, že totéž existuje i mezi D a P. Rejewski shrnul tyto vztahy tak, že je uspořádal do tabulky. Pro čtyři zprávy, které zatím máme, odráží tabulka vztahy mezi (L, R), (M, X), (J, M) a (D, P):
1. písmeno A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
4. písmeno P M R X
Když dostal Rejewski během jediného dne dostatek zpráv, mohl sestavit úplnou abecedu vztahů. Kompletní množinu závislostí představuje následující tabulka:
1. písmeno A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
4. písmeno F Q H P L W O G B M V R X U Y C Z I T N J E A S D K
Rejewski neznal denní klíč ani neměl představu, jaký klíč zprávy operátor zvolil, ale věděl, že výsledkem je tato tabulka vztahů. Kdyby byl denní klíč jiný, potom by také tabulka vztahů byla naprosto jiná. Následovala otázka, zda existuje nějaký způsob, jak z této tabulky stanovit denní klíč. Rejewski začal hledat v tabulce zákonitosti – struktury, které mohly denní klíč naznačit. Nakonec se zaměřil na jeden konkrétní typ takové zákonitosti, v níž figurovaly řetězce písmen. Například ve výše uvedené tabulce je A v horní řadě spojeno s F v dolní řadě. Když nyní vyhledáme F v horní řadě, ukáže se, že F je spojeno s W. Podíváme se na W v horní řadě. Zjistíme, že W je spojeno s A, u kterého jsme začali. Řetězec se uzavřel.
Se zbývajícími písmeny abecedy mohl Rejewski vytvořit více řetězců. Sestavil jejich strukturu a v každém řetězci zaznamenal počet spojení:
A Ý F Ý W Ý A 3 spojení
B Ý Q Ý Z Ý K Ý V Ý E Ý L Ý R Ý I Ý B 9 spojení
C Ý H Ý G Ý O Ý Y Ý D Ý P Ý C 7 spojení
J Ý M Ý X Ý S Ý T Ý N Ý U Ý J 7 spojení
Dosud jsme pouze uvažovali o spojeních mezi prvním a čtvrtým písmenem šestipísmenného opakovaného klíče. Rejewski však pracoval i se vztahy mezi druhým a pátým písmenem a třetím a šestým písmenem. Vždy se snažil sestavit strukturu řetězců včetně počtu spojení.
Rejewski si povšiml, že se řetězce každý den mění. Někdy sestavil hodně krátkých řetězců, jindy pouze pár dlouhých. A samozřejmě se také měnila uvnitř řetězců jednotlivá písmena. Charakter řetězců byl jasně dán nastavením denního klíče, který vznikal důsledkem nastavení propojovací desky, uspořádání scramblerů a jejich orientace. Otázkou zůstávalo, jak z těchto řetězců určit denní klíč. Který z 10 000 000 000 000 000 možných denních klíčů je spojen s konkrétní strukturou řetězce? Počet možností byl jednoduše příliš velký.
V tomto bodě pronikl Rejewski do podstaty problému. Přestože na podobu řetězců mělo vliv jak nastavení propojovací desky, tak scramblerů, jejich působení mohlo být do určité míry rozdílné. Zvláště jedna vlastnost řetězce byla zcela závislá na nastavení scramblerů, avšak neměla nic společného s nastavením propojovací desky: byla to délka řetězce. Ukážeme si to na příkladu, v němž denní klíč vyžaduje, aby písmena S a G byla vzájemně prohozena jako součást nastavení propojovací desky. Pokud tuto součást denního klíče změníme tím, že odstraníme kabel, který spojuje S a G, a použijeme jej místo toho k výměně například T a K, potom se řetězce změní následujícím způsobem:
A Ý F Ý W Ý A 3 spojení
B Ý Q Ý Z Ý T Ý V Ý E Ý L Ý R Ý I Ý B 9 spojení
C Ý H Ý S Ý O Ý Y Ý D Ý P Ý C 7 spojení
J Ý M Ý X Ý G Ý K Ý N Ý U Ý J 7 spojení
Některá písmena v řetězci se změnila, ale počet spojení v každém řetězci rozhodně zůstal konstantní. Rejewski identifikoval tu vlastnost řetězce, která byla výhradně důsledkem nastavení scramblerů.
Celkový počet nastavení scramblerů je dán jako počet uspořádání (6) vynásobený počtem možných orientací (17 576), což dává číslo 105 456. Takže místo toho, aby se trápil, který z 10 000 000 000 000 000 denních klíčů odpovídá určité sadě řetězců, mohl se Rejewski soustředit na mnohem jednodušší problém: Které z 105 456 nastavení scramblerů odpovídá pozorovanému počtu spojení v rámci sady řetězců? Toto číslo je stále velké, ale zhruba sto miliardkrát menší než celkový počet možných denních klíčů. Jinými slovy, náročnost úkolu poklesla o řád sta miliard. Takový úkol je již pravděpodobně řešitelný.
Rejewski postupoval následujícím způsobem: díky špionáži Hans-Thilo Schmidta měl k dispozici repliku přístroje Enigma. Jeho tým se dal do namáhavé práce: prozkoušel všech 105 456 nastavení scramblerů a katalogizoval délky řetězců, jež byly každým nastavením generovány. Dokončit katalog zabralo celý rok, ale jakmile Biuro nashromáždilo všechna data, Rejewski mohl konečně začít dešifrovat Enigmu.
Každý den se podíval na zašifrované klíče zprávy, tedy na prvních šest písmen každé zachycené zprávy, a tuto informaci použil k vybudování své tabulky vztahů. To mu umožnilo najít jednotlivé řetězce a v každém z nich určit počet spojení. Například analýza prvního a čtvrtého písmene by mohla vyústit ve čtyři řetězce se 3, 9, 7 a 7 spojeními. Analýza druhého a pátého písmene by mohla také vést ke čtyřem řetězcům – se 2, 3, 9 a 12 spojeními. Analýza třetího a šestého písmene by mohla vést k pěti řetězcům s 5, 5, 5, 3 a 8 spojeními. Rejewski stále ještě neměl ponětí o denním klíči, ale věděl, že z něj vyplývají tři sady řetězců s následujícím počtem řetězců a spojení:
4 řetězce z 1. a 4. písmene se 3, 9, 7 a 7 spojeními
4 řetězce z 2. a 5. písmene se 2, 3, 9 a 12 spojeními
5 řetězců z 3. a 6. písmene s 5, 5, 5, 3 a 8 spojeními
Rejewski nyní mohl nahlédnout do svého katalogu, který obsahoval každé nastavení scramblerů indexované podle druhu generovaných řetězců. Když našel položku v katalogu, jež obsahovala správný počet řetězců s odpovídajícím počtem spojení, znal nastavení scramblerů pro daný denní klíč. Řetězce byly jakoby otisky prstů – důkaz, který odhalil původní uspořádání a orientaci scramblerů. Rejewski pracoval jako detektiv, který na místě zločinu sejme otisk prstu a potom použije databázi, aby našel odpovídajícího podezřelého.
Když Rejewski identifikoval scramblerovou část denního klíče, musel ještě odhalit nastavení propojovací desky. Ačkoli zde bylo kolem sta miliard možností, šlo o poměrně jednoduchý úkol. Rejewski začal nastavením scramblerů ve své replice Enigmy podle zjištěné scramblerové části denního klíče. Potom odstranil všechny kabely z propojovací desky, aby neměla na šifrování žádný vliv. Nakonec vzal část zachycené zprávy a naťukal ji do přístroje. Výsledkem byla převážně jakási hatmatilka, protože správná kabeláž propojovací desky byla zatím neznámá. Poměrně často se však objevily mlhavě rozeznatelné věty jako třeba plijedtedobelrina – pravděpodobně to mohlo znamenat „přijeďte do Berlína“. Pokud byl tento předpoklad správný, potom to znamenalo, že písmena R a L jsou spojena a vyměněna kabely propojovací desky, zatímco A, I, E, B a N nikoli. Analýzou dalších vět pak bylo možné určit další písmena, jež je třeba vzájemně prohodit pomocí propojovací desky. Když se takto podařilo určit nastavení propojovací desky při znám
ém nastavení scramblerů, měl Rejewski k dispozici úplný denní klíč a mohl tedy rozšifrovat jakoukoliv zprávu zaslanou toho dne.
Rejewski si velmi zjednodušil úkol nalézt denní klíč tím, že oddělil problém nastavení scramblerů od problému nastavení propojovací desky. Každý z nich byl sám o sobě řešitelný. Původně jsme odhadli, že prověřit každý možný klíč k Enigmě by zabralo delší dobu, než je celkové stáří vesmíru. Rejewski však strávil sestavováním svého katalogu délek řetězců pouhý rok. Pak již mohl najít denní klíč téhož dne, kdy jej nepřítel začal používat. A jakmile měl denní klíč, disponoval stejnou informací jako zamýšlený příjemce, a tak mohl zprávu snadno dešifrovat.
Po Rejewského průlomu se německá komunikace stala průhlednou. Polsko sice ve válce s Německem nebylo, ale přesto mu hrozila invaze, takže úleva po přemožení Enigmy byla obrovská. Pokud mohli Poláci zjistit, co měli němečtí generálové za lubem, pak měli naději, že se dokážou ubránit. Osud polského národa závisel na Rejewském a on svou zemi nezklamal. Rejewského útok na Enigmu je jedním ze skutečně skvělých výkonů kryptoanalýzy. Bohužel jsem musel jeho práci shrnout na několika stránkách, proto jsem vynechal některé technické detaily a všechny slepé uličky. Enigma je komplikovaný šifrovací přístroj a její rozlomení vyžadovalo obrovský intelektuální výkon. Toto zjednodušení by vás nemělo svést k mylným závěrům a podcenit to, co Rejewski dokázal.
Polský úspěch v prolomení Enigmy byl dán třemi faktory: strachem, matematikou a špionáží. Beze strachu z invaze by Poláky odradila zdánlivá nezranitelnost šifry. Bez matematiky by Rejewski
nebyl schopen analyzovat řetězce. A bez Schmidta, kódovým jménem „Asche“, a jeho dokumentů by nebylo známo vnitřní zapojení scramblerů a kryptoanalýza by nemohla ani začít. Rejewski se nezdráhal vyjádřit svůj dík Schmidtovi: „Jeho dokumenty byly jako nebeská mana, všechny dveře byly rázem otevřeny.“
Poláci úspěšně používali Rejewského techniku po několik let. Když Hermann Göring navštívil v roce 1934 Varšavu, neměl ani ponětí, že jeho komunikace je zachycována a dešifrována. Když on a další němečtí hodnostáři pokládali věnec k hrobu Neznámého vojína v blízkosti kanceláří Biura Szyfrow, Rejewski se na ně mohl dívat z okna a spokojeně myslet na to, že dovede číst jejich nejtajnější komunikaci.
Dokonce i když Němci učinili malou změnu ve způsobu vysílání zpráv, Rejewski situaci zvládl. Jeho starý katalog délek řetězců byl po této změně k ničemu. Než by jej dával znovu dohromady, sestavil jeho mechanickou verzi, která automaticky vyhledávala správná nastavení scramblerů. Rejewského vynález byl adaptací Enigmy, která byla schopná rychle prověřit každé ze 17 576 nastavení, dokud nenarazila na to správné. Protože existovalo šest možných uspořádání scramblerů, bylo nutné mít šest Rejewského přístrojů pracujících paralelně. Každý z nich představoval jedno z šesti možných uspořádání. Dohromady tvořily jednotku, která byla asi metr vysoká a dovedla najít denní klíč zhruba během dvou hodin. Říkalo se jim bomby – jméno mohlo narážet na hlasitý tikot, který vydávaly, když prověřovaly nastavení scramblerů. Další verze říká, že Rejewski dostal nápad postavit tyto přístroje, když v kavárně jedl „bombu“, zmrzlinu ve tvaru polokoule. Bomby účinně mechanizovaly proces dešifrování. Byla to přirozená odpověď na Enigmu, jež byla mechanizací šifrování.
Po velkou část 30. let 20. století pracoval Rejewski se svými kolegy neúnavně na odhalování klíčů k Enigmě. Měsíc po měsíci se tým musel vypořádávat se stresem a napětím kryptoanalýzy, opravovat mechanické poruchy bomb, zvládat nekončící přísun zašifrovaných odposlechů. Jejich životy začaly být ovládány pronásledováním denních klíčů, té rozhodující informace, která odhalí smysl zašifrovaných zpráv. Polští kryptoanalytici však nevěděli, že velká část jejich práce je zbytečná. Šéf Biura major Gwido Langer v té době už vlastnil denní klíče Enigmy, ukrýval je však schované ve svém stole.
Langer prostřednictvím Francouzů získával informace od Schmidta. Aktivity německého špiona neskončily v roce 1931 dodáním dvou dokumentů o fungování Enigmy, ale pokračovaly po dalších sedm let. Schmidt se setkal s francouzským agentem Rexem asi dvacetkrát, často na odlehlých horských chatách, kde bylo zaručeno jejich soukromí. Na každém setkání Schmidt předal jednu nebo více kódových knih, z nichž každá obsahovala měsíční dávku denních klíčů. Byly to právě ty kódové knihy, jež byly distribuová-
ny všem německých operátorům Enigmy a které obsahovaly všechny informace potřebné k zašifrování a dešifrování zpráv. Celkem Schmidt dodal kódové knihy, které obsahovaly denní klíče na 38 měsíců. Klíče by Rejewskému ušetřily obrovské množství času a námahy, nebylo by třeba konstruovat bomby a bylo by možné uvolnit pracovní sílu pro jiné sekce Biura. Pozoruhodně prohnaný Langer se však rozhodl Rejewskému neprozradit, že má klíče k dispozici. Tím, že Rejewského připravil o snadno získané klíče, jej Langer připravoval na nevyhnutelný okamžik, kdy už klíče nebudou k dispozici. Věděl, že když vypukne válka, nebude již Schmidt moci pokračovat v tajných schůzkách a Rejewski bude muset být soběstačný. Langer si myslel, že by měl Rejewski trénovat své dovednosti ještě v době míru jako přípravu na události, které je čekají.
Rejewski nakonec narazil na meze svých možností. V prosinci 1938 němečtí kryptografové zvýšili bezpečnost Enigmy. Všichni operátoři dostali dva nové scramblery, takže jejich uspořádání mohlo být tvořeno jakýmikoli třemi z pěti možných scramblerů. Předtím byly k dispozici pouze tři scramblery (označené 1, 2 a 3), ze kterých se mohlo vybírat, a tedy pouze šest způsobů jejich uspořádání, nyní však navíc přibyly dva scramblery (označené 4 a 5), počet uspořádání tedy vzrostl na 60, jak vidíme v tabulce 10. Prvním úkolem Rejewského bylo nalézt vnitřní zapojení dvou nových scramblerů. Horší však bylo, že také musel postavit desetkrát více bomb, aby mohl i nadále testovat všechna možná uspořádání scramblerů. Náklady na vybudování takové baterie bomb byly patnáctinásobkem ročního rozpočtu na vybavení celého Biura. Následující měsíc se situace dále zhoršila, protože Němci zvýšili počet kabelů propojovací desky z šesti na deset. Místo dvanácti písmen, která se měnila před vstupem do scramblerů, se jich nyní měnilo dvacet. Počet možných klíčů vzrostl na 159 000 000 000 000 000 000.
V roce 1938 dosáhly dovednosti Poláků v odposlechu a dešifrování svého vrcholu, začátkem roku 1939 však nové scramblery a přidané kabely zarazily tok špionážních informací. Rejewski, který v předchozích letech posouval hranice možností kryptoanalýzy, byl dočasně poražen. Dokázal, že Enigma není nerozlomitelná šifra, ale bez prostředků nutných k prověření každého nastavení scramblerů nemohl najít denní klíč a dešifrování nebylo možné. V takových beznadějných podmínkách by mohl být Langer v pokušení předat klíče, které získal od Schmidta, ale už je neměl. Právě před zavedením nových scramblerů Schmidt zrušil kontakty s agentem Rexem. Po sedm let mu dodával klíče, které nebyly nezbytné. Když však nyní Poláci klíče opravdu potřebovali, už nebyly k dispozici.
Nová nezranitelnost Enigmy byla zdrcujícím úderem pro Polsko, protože Enigma nebyla pouze prostředkem komunikace, ale také klíčovou součástí Hitlerovy strategie tzv. blitzkriegu. Koncept této bleskové války zahrnoval rychlý, intenzivní, koordinovaný útok, což znamenalo, že velké tankové divize musely komunikovat mezi sebou navzájem stejně jako s pěchotou a dělostřelectvem. Kromě toho měly být pozemní síly podporovány hloubkovými bombardéry Stuka, což vyžadovalo účinnou a rychlou komunikaci mezi frontou a letišti v zázemí. Heslem blitzkriegu byla „rychlost útoku díky rychlosti komunikace“. Pokud Poláci nemohli přijít Enigmě na kloub, neměli naději, že by zastavili prudký německý útok, který byl očividně záležitostí pouhých několika měsíců. Němci už okupovali Sudety a 27. dubna 1939 odvolali pakt o neútočení s Polskem. Hitlerova protipolská rétorika byla čím dál tím ostřejší. Langer se rozhodl, že pokud dojde k invazi do Polska, pak jeho kryptografický průlom, který byl do té doby držen v tajnosti před Spojenci, nesmí být ztracen. Jestliže Polsko nemohlo mít užitek z Rejewského práce, potom měli mít možnost ji vyzkoušet a pokračovat v ní Spojenci. Langer uvažoval, že Británie a Francie, země daleko bohatší než Polsko, by možná dokázaly plně využít princip bomb.
30. června major Langer zatelegrafoval svým francouzským a britským protějškům a pozval je do Varšavy, aby prodiskutovali některé naléhavé záležitosti týkající se Enigmy. 24. června vedoucí francouzští a britští kryptoanalytici dorazili do ústředí Biura, aniž by věděli, co je čeká. Langer je uvedl do místnosti, ve které stál objekt pokrytý černou látkou. Látku stáhl a dramaticky tak odhalil jednu z Rejewského bomb. Jeho publikum užaslo, když slyšelo, jak Rejewski po léta luštil Enigmu. Poláci byli o deset let popředu před kýmkoli jiným na světě. Zvláště Francouzi žasli, protože práce Poláků byla založena na výsledcích francouzské špionáže. Francouzi předali informaci od Schmidta Polákům, protože se domnívali, že nemá žádnou hodnotu, ale Poláci dokázali, že tomu tak není.
Jako překvapení na závěr Langer nabídl Britům a Francouzům dvě náhradní repliky Enigmy a detailní plány bomb, které pak byly převezeny v diplomatických zavazadlech do Paříže. Odtamtud byl 16. srpna jeden z přístrojů Enigma poslán do Londýna. Přes kanál La Manche jej ve svých zavazadlech propašoval dramatik Sacha Guitry a jeho žena, herečka Yvonne Printempsová, aby případní němečtí špioni pozorující přístav nepojali podezření. O dva dny později,
1. září 1939 Hitler vpadl do Polska a začala válka.
V nakladatelství Dokořán právě vychází extrémně zajímavý text, Kniha kódů a šifer. Autorem je Simon Singh, od něhož česky už vyšla Velká Fermatova věta. Nakladatel byl tak laskav, že čtenářům Humpoláka nabízí v elektronické podobě k přečtení některé kapitoly.
Zdroj: Simon Singh, Kniha kódů a šifer, Dokořán, Praha, 2003, http://www.dokoran.cz
