Černé komnaty
Zdokonalení monoalfabetické šifry jejím nasazením na úrovni slabik nebo homofonní substitucí mohlo v 17. století ještě postačovat, avšak v 18. století se kryptoanalýza již dostala na průmyslovou úroveň. Působily v ní týmy vládních kryptoanalytiků, kteří spo-lečným úsilím dovedli vyluštit i nejsložitější šifry. Každá evropská mocnost měla svou tzv. černou komnatu – mozkové centrum pro dešifrování zpráv a shromažďování zpravodajských informací. Nejslavnější, nejdisciplinovanější a nejvýkonnější z nich byla Geheime Kabinets-Kanzlei ve Vídni.
Fungovala podle pevně daného časového řádu, neboť bylo třeba, aby její nekalé aktivity nenarušily hladký chod poštovní služby. Dopisy určené vídeňským ambasádám byly nejprve doručeny do černé komnaty, a to přesně v sedm ráno. Tajemníci je odpečetili a tým paralelně pracujících stenografů pořídil opisy. Pokud to bylo třeba, účastnili se opisování i jazykoví specialisté, aby pomohli s ne-ob-vyklými abecedami. Během tří hodin byly dopisy opět zapečetěny a vráceny na hlavní poštu, aby je mohla doručit adresátům. Pošta, která Rakouskem jen procházela, putovala do černé komnaty v de-set dopoledne, odchozí pošta z vídeňských velvyslanectví ve čtyři odpoledne. I z této korespondence se rutinně pořizovaly opisy. Vídeňskou černou komnatou prošla denně asi stovka dopisů.
Kopie dopisů se předávaly kryptoanalytikům. Ti seděli po jednom v malých přístavcích, připraveni hledat význam jednotlivých depeší. Vídeňská černá komnata nejen že dodávala rakouskému panovnickému dvoru neocenitelné informace, ale také umožňovala prodávat získané poznatky jiným evropským mocnostem. V roce 1774 byla například uzavřena smlouva s tajemníkem francouzského vyslanectví opatem Georgelem, na jejímž základě dostával za tisíc zlatých dvakrát týdně zpravodajský souhrn. Získané informace posílal přímo králi Ludvíku XV.
Černé komnaty způsobily, že všechny varianty monoalfabetické šifry byly rázem zastaralé. Tváří v tvář takové kryptoanalytické přesile museli kryptografové konečně přejít na složitější, ale bezpečnější Vigenčrovu šifru. Šifranti začali postupně používat polyalfabetické šifry. Kromě potřeby účinnější kryptoanalýzy zde byla ještě jedna motivace, která souvisela s vývojem telegrafu a snahou zabezpečit telegramy před odposlechem a dešifrováním.
Přestože telegraf a s ním spjatá telekomunikační revoluce je dílem 19. století, kořeny telegrafie sahají již do roku 1753. Anonymní článek v časopise vydávaném ve Skotsku popisoval, jak lze zasílat zprávy na velkou vzdálenost, spojíme-li odesilatele a příjemce svazkem 26 kabelů, jedním pro každé písmeno abecedy. Odesilatel by pak mohl zaslat zprávu pomocí elektrických pulsů. Například slovo ahoj by se odeslalo tak, že nejprve by prošel signál kabelem odpovídajícím písmenu a, pak kabelem odpovídajícím písmenu h a tak dále. Tato „rychlá metoda sdělování informací“, jak ji vynálezce nazval, nebyla nikdy realizována, protože se nepodařilo překonat s ní spojené technické potíže.
Jedním z problémů byla absence dostatečně citlivého systému pro detekování elektrického signálu. Sir Charles Wheatstone a William Fothergill Cooke dokázali v Anglii sestavit detektory ze zmagnetizovaných jehel, které se vychylovaly, pokud blízkým okruhem procházel elektrický proud. Roku 1839 byl Wheatstoneův-Cookeův systém použit pro zasílání zpráv mezi železničními stanicemi West Drayton a Paddington, tedy na vzdálenost 29 km. Dobrá pověst telegrafu se brzy rozšířila a pozornost vzbudila mimořádná rychlost komunikace. Nic mu neposloužilo lépe než narození druhého syna královny Viktorie prince Alfréda, který přišel na svět dne 6. srpna 1844 na zámku Windsor. Zprávu odeslali telegraficky do Londýna a do hodiny se na ulicích prodávalo zvláštní vydání The Times. Článek upozorňoval na technologii, jež tento výkon umožnila, výslovnou zmínkou, že za něj „vděčíme mimořádné výkonnosti elektro-magnetického telegrafu“. Následujícího roku si telegraf vydobyl ještě větší proslulost, když byl s jeho pomocí polapen John Tawell – vrah, jenž zabil svou milenku ve městě Slough a pak ve snaze uprchnout naskočil do londýnského vlaku. Místní policie telegrafovala jeho popis do Londýna, kde byl vrah při vystupování z vlaku zatčen.
V téže době postavil v Americe Samuel Morse svou první telegrafní linku spojující Baltimore a Washington. Pro zesílení signálu použil elektromagnet, takže signál u příjemce byl dost silný, aby zaznamenal na kus papíru krátké a dlouhé značky – tečky a čárky. Morse také sestavil známou Morseovu abecedu pro kódování písmen do teček a čárek (viz tabulka 6). Svůj systém završil akustickým měničem, který umožnil příjemci tečky a čárky slyšet.
Morseův vynález postupně nabyl vrchu nad Wheatstoneovým-Cookeovým systémem i v Evropě. Roku 1851 se na celé evropské pevnině začala používat mírně modifikovaná forma Morseovy abecedy obsahující dodatečné kódy pro písmena s diakritikou. Každým rokem rostl vliv Morseovy abecedy a telegrafu na celém světě. Policie díky těmto vymoženostem dostihla více zločinců, noviny otiskovaly nejčerstvější zprávy, podnikatelé disponovali aktuálními informacemi z finančního trhu a podniky mohly obchodovat na velké vzdálenosti.
Ochrana této často citlivé komunikace však představovala vážný problém. Morseova abeceda sama o sobě nepatří mezi kryptografické nástroje, protože obsah zprávy nijak nechrání. Tečky a čárky nejsou ničím jiným než výhodnou reprezentací písmen pro přenos prostřednictvím telegrafu. Morseovka není nic jiného než jiná formy obyčejné abecedy. Problém utajení vznikl především proto, že kdo chtěl poslat telegram, musel se obrátit na operátora, který si zprávu nutně musel přečíst, aby ji mohl odeslat. Telegrafisté měli přístup ke všem zprávám v systému. Existovalo proto riziko, že například firma může operátora podplatit, aby se dostala k depeším své konkurence. Podstatu problému shrnuje článek o telegrafii publikovaný roku 1853 v anglickém časopisu Quarterly Review:
„Rovněž je třeba přijmout opatření týkající se vážného problému, jímž je v dnešní době obtěžkána komunikace telegrafní, a sice narušení veškerého soukromí. Za současného stavu věcí je vždy dobrý půltucet lidí obeznámen s obsahem zprávy, již zasílá jedna osoba druhé. Jakkoli jsou úředníci Anglické telegrafní společnosti vázáni přísahou, je zřejmé, že často píšeme sdělení, u nichž nelze tolerovati, aby je četl kdokoli cizí dříve než zamýšlený adresát. Toto je těžká vada telegrafie, již je třeba napraviti tím či oním způsobem.“
Řešení spočívá v zašifrování zprávy předtím, než se předá telegrafistovi. Ten pak převede do morseovky šifrový text. Nejen že se tím zabrání operátorovi ve čtení citlivého textu, ale rovněž se zmaří úsilí každého špiona, který by odposlouchával telegrafní komunikaci. Prokazatelně nejlepším způsobem utajení důležité obchodní korespondence byla polyalfabetická Vigenčrova šifra. Protože byla pokládána za nerozluštitelnou, vešla ve známost jako le chiffre indéchiffrable (nerozluštitelná šifra). Kryptografové získali – přinejmenším na nějakou dobu – převahu nad kryptoanalytiky.
Pan Babbage versus Vigene`rova šifra
Nejpozoruhodnější postavou kryptoanalýzy 19. století je Charles Babbage, výstřední britský génius, jenž se proslavil především koncepčním návrhem moderního počítače. Narodil se roku 1791, jeho otcem byl bohatý londýnský bankéř Benjamin Babbage. Když se Charles proti otcově vůli oženil, ztratil přístup k rodinnému majetku, ale stále měl dost peněz na to, aby zůstal finančně zabezpečen a aby mohl strávit život jako nezávislý učenec, jenž se zabývá jakýmkoli problémem, který ho právě zaujme. K jeho vynálezům patří rychloměr stejně jako lapač krav – zařízení, jež se připev-
ňovalo na přední část parní lokomotivy, aby odehnalo dobytek z ko-lejí. Pokud jde o vědecké objevy, Babbage si jako první povšiml souvislosti mezi letokruhy a stářím stromu, přičemž správně usoudil, že z velmi starých stromů lze získat poznatky o klimatu dávných dob. Rovněž se zajímal o statistiku a pro rozptýlení si sestavil první tabulky úmrtnosti, dnes základní nástroj v pojišťovnictví.
Babbage se neomezoval jen na vědecké a technické problémy. V jeho době se výše poštovného u dopisu odvozovala od vzdálenosti, na kterou je dopis odesílán. Babbage upozornil, že práce spojená s výpočtem vzdálenosti stojí víc, než kolik činí poštovné. Navrhl systém poštovného, který používáme v rámci jedné země dnes – jednotnou cenu bez ohledu na bydliště adresáta. Zajímal se rovněž o politické a sociální otázky, ke konci svého života uspořádal kampaň za vyhnání flašinetářů a potulných muzikantů z Londýna. Stěžoval si, že jejich hudba „nikoli zřídka povzbuzuje k tanci malé otrhané ničemy, někdy i osoby podnapilé, jež se pak často přidávají a svými disharmonickými hlasy ještě zvětšují množství hluku. Jinou třídou společenskou, jež patří k zastáncům pouliční hudby, jsou dámy, jejichž ctnost je pozoruhodně vrtkavá, dámy kosmopolitních sklonů, jež tak získávají vhodnou záminku, jak ukájet vlastní zvědavost u otevřených oken“. Babbage se však dočkal pomsty, neboť hudebníci se na oplátku scházeli ve velkých skupinách kolem jeho domu a tam hráli, jak jen nejhlasitěji dovedli.
Obrat v Babbagově vědecké kariéře nastal roku 1821, kdy se spolu s astronomem Johnem Herschelem zabýval sadou matematických tabulek používaných při astronomických, technických a navigačních výpočtech. Oba muži byli znechuceni množstvím chyb, jež v tabulkách našli. Tyto chyby mohly vést k závažným nepřesnostem při výpočtech. Jedna sada takových tabulek (Nautické efemeridy pro nalezení zeměpisné šířky a délky na moři) obsahovala přes tisícovku chyb. Těmto chybám se přičítalo mnoho ztroskotání lodí a technických katastrof.
Matematické tabulky se sestavovaly ručně, chyby byly důsledkem selhání lidského faktoru. Babbage prohlásil: „Kéž by Bůh dal a ty-to výpočty mohla pohánět pára!“ Tím začalo podivuhodné dobrodružství, snaha postavit stroj schopný sestavit takové tabulky
bezchybně a s vysokou přesností. Roku 1823 navrhl Babbage tzv. Difference Engine No. 1 – obrovský kalkulátor sestávající z 25 000 mechanických součástek, jenž měl být postaven za vládní peníze. Babbage, ač geniální vynálezce, nedovedl své projekty uvést do života. Po deseti letech pachtění zcela opustil Difference Engine No. 1, sestavil nový plán a zahájil práce na Difference Engine No. 2.
Když Babbage zanechal práce na prvním stroji, vláda ztratila důvěru v jeho záměry, rozhodla se omezit své ztráty a z projektu se stáhla. Tou dobou již výdaje dosáhly 17 470 liber, což by stačilo na stavbu dvou bitevních lodí. Patrně právě proto si Babbage později postěžoval: „Navrhněte Angličanovi jakýkoli princip, jakýkoli nástroj, třeba sebeobdivuhodnější, a seznáte, že veškeré úsilí jeho mysli je obráceno k tomu, aby na novince našel obtíž, chybu či nemožnost realizace. Budete-li mu vyprávět o stroji na škrábání brambor, prohlásí, že něco takového je nemožné. Když stroj oškrábe bramboru před jeho očima, řekne, že to je stejně k ničemu, protože nedovede oloupat ananas.“
Kvůli nedostatku prostředků Babbage nikdy nedokončil svůj Difference Engine No. 2. Vědecká tragédie spočívala v tom, že tento stroj byl přímým předstupněm tzv. Analytical Engine. Ten už neměl sestavovat předem danou sadu tabulek, ale řešit širokou škálu matematických problémů podle vložených instrukcí. Analytical Engine je předobrazem dnešních počítačů. Struktura stroje obsahovala „sklad“ (paměť) a „mlýnici“ (procesor), což mu umožňovalo činit rozhodnutí a opakovat instrukce, přesně jako to dělají dnešní počítače pomocí příkazů IF … THEN … a LOOP.
O století později, během druhé světové války, to byla právě první elektronická realizace Babbagova stroje, která se zasloužila o velký pokrok v kryptoanalýze. Avšak již za svého života přispěl Babbage k rozvoji této oblasti zásadním způsobem: dokázal rozluštit Vigenčrovu šifru a učinil tak největší pokrok v kryptoanalýze od 9. století, kdy arabští učenci objevili frekvenční analýzu a rozluštili s její pomocí monoalfabetickou substituční šifru. Babbagův postup nevyžadoval žádné složité výpočty ani mechanické pomůcky. Stačila jen dobrá hlava.
Babbage se o šifry zajímal od dětství. Později napsal, jak ho tato záliba občas dostala do potíží: „Starší chlapci vymýšleli šifry, ale mně se obvykle už z několika slov podařilo najít klíč. Důsledky této dovednosti bývaly bolestivé: tvůrci takové šifry mě dost často zbili, přestože chyba spočívala jen v jejich vlastní hlouposti.“ Výprasky ho neodradily, kryptoanalýza byla pro něj i nadále přitažlivá. Ve své autobiografii napsal, že „luštění šifer je podle mého názoru tou nejvíce fascinující ze všech dovedností“.
V londýnské společnosti si Babbage brzy vydobyl pověst kryptoanalytika připraveného zdolat každou šifrovanou zprávu, a proto se na něj cizí lidé obraceli s nejrůznějšími problémy. Bezradnému životopisci pomohl například rozluštit rukopisné poznámky prvního anglického královského astronoma Johna Flamsteeda. Stal se spásou pro historika, jenž potřeboval přečíst šifru Henrietty Marie, manželky anglického krále Karla I. Roku 1854 spolupracoval s advokátem a použil kryptoanalýzu k odhalení klíčového důkazu v právní při. Během let nashromáždil silný svazek dešifrovaných zpráv, jež hodlal použít jako základ autorské knihy o kryptoanalýze, pro niž zvolil název The Philosophy of Decyphering (Filozofie dešifrování). Kniha měla obsahovat po dvou příkladech každého typu šifry, jeden ukázkově rozluštěný, druhý ponechaný jako cvičení pro čtenáře. Bohužel, kniha dopadla stejně jako mnoho jeho dalších grandiózních plánů – zůstala nedokončena.
Zatímco většina kryptoanalytiků se vzdala veškeré naděje na rozluštění Vigenčrovy šifry, Babbage byl k takovému pokusu inspirován výměnou korespondence s bristolským zubařem jménem John Hall Brock Thwaites, jehož pohled na šifrování byl poněkud přímočarý. Roku 1854 Thwaites prohlásil, že vytvořil zcela novou šifru, která však ve skutečnosti byla ekvivalentem Vigenčrovy šifry. Napsal sdělení do časopisu Journal of the Society of Arts (List Společnosti nauk) se záměrem patentovat svůj nápad, přičemž si očividně nebyl vědom, že je starý několik set let. Babbage pak Společnosti sdělil, že „tato šifra je velmi stará a dá se najít ve většině knih“. Thwaitese to nijak nerozházelo a vyzval Babbage, ať se pokusí jeho šifru rozluštit. To, zda lze šifru rozluštit nebo ne, nemělo samozřejmě žádný vztah k otázce jejího autorství, avšak výzva vzbudila Babbagovu zvědavost. Začal tedy hledat ve Vigenčrově šifře slabiny.
Luštění obtížné šifry se podobá zlézání strmé skalní stěny. Kryptoanalytik hledá každou sebemenší škvíru a skulinu, která by mohla pomoci v cestě vzhůru. U monoalfabetické šifry se lze chytit frekvence hlásek, neboť nejběžnější písmena jako e, t a a se nakonec prozradí, ať už byla ukryta jakkoli. U polyalfabetické Vigenčrovy šifry jsou frekvence daleko vyrovnanější, protože se při šifrování přepíná mezi abecedami pomocí klíče. Skalní stěna je na první pohled dokonale hladká.
Připomeňme si, že zásadní výhoda Vigenčrovy šifry spočívá v tom, že stejné písmeno lze zašifrovat více způsoby. Zní-li například klíčové slovo KING („král“), pak může být každé písmeno otevřeného textu potenciálně šifrováno čtyřmi různými způsoby, neboť klíčové slovo sestává ze čtyř písmen. Každé písmeno klíčového slova definuje jinou šifrovou abecedu – součást Vigenčrova čtverce – jak je to vidět v tabulce 7. Zvýraznili jsme sloupec e, aby bylo patrné, jak se toto písmeno zašifruje čtyřmi různými způsoby v závislosti na tom, který znak klíčového slova byl použit:
Jestliže šifrování definuje písmeno K slova KING,
pak znaku e v otevřeném textu odpovídá O v šifrovém textu.
Jestliže šifrování definuje písmeno I slova KING,
pak znaku e v otevřeném textu odpovídá M v šifrovém textu.
Jestliže šifrování definuje písmeno N slova KING,
pak znaku e v otevřeném textu odpovídá R v šifrovém textu.
Jestliže šifrování definuje písmeno G slova KING,
pak znaku e v otevřeném textu odpovídá K v šifrovém textu.
Z toho plyne, že i celá slova budou šifrována různými způsoby. Například slovo the (anglický určitý člen) se zašifruje jako DPR, BUK, GNO nebo ZRM podle toho, v jaké se nachází poloze vůči klíčovému slovu. Kryptoanalýza se tím komplikuje, není však nemožná. Je důležité si uvědomit, že existují jen čtyři způsoby, jak zašifrovat the. Pokud otevřený text obsahuje toto slovo několikrát, pak je velmi pravděpodobné, že některé ze čtyř jeho možných zašifrování se budou v šifrovém textu opakovat. To vidíme na následující ukázce, kde je fráze The Sun and the Man in the Moon (Slunce a muž na Měsíci) zašifrována pomocí Vigenčrovy šifry a klíčového slova KING.
Klíčové slovo K I N G K I N G K I N G K I N G K I N G K I N G
Otevřený text t h e s u n a n d t h e m a n i n t h e m o o n
Šifrový text D P R Y E V N T N B U K W I A O X B U K W W B T
Slovo the je zde poprvé zašifrováno jako DPR, podruhé a potřetí jako BUK. Důvod, proč se BUK opakuje dvakrát, spočívá v tom, že třetí the je v otevřeném textu vzdáleno osm písmen od druhého a osm je násobkem délky klíčového slova, tedy čtyř. Jinými slovy, druhé the bylo šifrováno podle písmen ING klíčového slova, třetí the pak podle týchž písmen, protože než jsme k němu dospěli, klíčové slovo se zopakovalo přesně dvakrát.
Babbage si povšiml, že tato pravidelnost mu může poskytnout právě ten opěrný bod, který potřeboval, aby mohl začít Vigenčrovu šifru dobývat. Podařilo se mu definovat řadu poměrně jednoduchých kroků, jež mohl zopakovat každý kryptoanalytik zápasící s chiffre indéchiffrable. Abychom si předvedli jeho brilantní techniku, předpokládejme, že jsme zachytili šifrový text, jenž je na obrázku 13. Víme, že byl šifrován Vigenčrovou šifrou, nevíme však nic o původní zprávě a klíč je rovněž neznámý.
První krok Babbagovy kryptoanalýzy spočívá v hledání sekvencí, jež se opakují v šifrovém textu vícekrát. Takové opakování může vzniknout dvěma způsoby. Nejpravděpodobnější je, že táž sekvence písmen v otevřeném textu byla zašifrována touž částí klíče. Vedle toho však existuje i méně pravděpodobná možnost, že dvě odlišné sekvence písmen v otevřeném textu byly zašifrovány rozdílnými částmi klíče a náhodou poskytly týž výsledek – stejné pořadí písmen v šifrovém textu. Omezíme-li se na delší sekvence, pak je druhá možnost velmi nepravděpodobná. Proto bychom si měli všímat jen sekvencí o délce čtyř znaků a více. V tabulce 8 najdeme seznam
ta-kových opakujících se sekvencí včetně vzdáleností mezi nimi. Například sekvence E-F-I-Q se nachází v prvním a pak v pátém řádku šifrového textu, vzdálenost mezi oběma výskyty činí 95 písmen.
Klíčové slovo se nepoužívá jen k šifrování, ale samozřejmě také k dešifrování. Pokud jej tedy dokážeme identifikovat, je dešifrování snadné. Zatím nemáme dost informací, abychom dokázali nalézt klíčové slovo, ale tabulka 8 poskytuje dobrou nápovědu, pokud jde o jeho délku. Vedle toho, které sekvence se opakují a jak jsou od sebe vzdáleny, obsahuje zbytek tabulky pomocné údaje, tzv. faktory opakování – čísla, jež jsou děliteli vzdálenosti mezi opakováním sekvencí. Například sekvence W-C-X-Y-M se opakuje po dvaceti písmenech, faktory jsou proto čísla 1, 2, 4, 5 a 20, protože ta jsou celočíselnými děliteli čísla 20 (dělí jej beze zbytku). Z toho plyne šest možností:
Klíč tvoří 1 písmeno a opakuje se 205 mezi sekvencemi.
Klíč tvoří 2 písmena a opakuje se 105 mezi sekvencemi.
Klíč tvoří 4 písmena a opakuje se 55 mezi sekvencemi.
Klíč tvoří 5 písmen a opakuje se 45 mezi sekvencemi.
Klíč tvoří 10 písmen a opakuje se 25 mezi sekvencemi.
Klíč tvoří 20 písmen a opakuje se 15 mezi sekvencemi.
První možnost lze vyloučit, protože klíč o délce 1 znaku odpovídá monoalfabetické šifře – použil by se k ní jen jeden řádek Vigenč-rova čtverce a šifrová abeceda by se neměnila. Je nepravděpodobné, že by kryptograf udělal právě tohle. Všechny další možnosti jsou označeny v příslušném sloupci tabulky 8 zaškrtnutím. To indikuje možnou délku klíče.
Abychom určili, zda je klíč dlouhý 2, 4, 5, 10 či 20 písmen, musíme se podrobněji podívat na faktory u ostatních sekvencí. Zdá se, že klíč tvoří maximálně 20 písmen, proto se tabulka 8 zabývá jen hodnotami opakování menšími nebo rovnými dvaceti a obsahuje všechny faktory u všech sekvencí, jež se do tohoto rozmezí vejdou. Tendence k opakování klíče, jehož délka je dělitelná pěti, je zřejmá: v podstatě mu odpovídají všechny výskyty opakujících se sekvencí. První z nich E-F-I-Q lze vysvětlit jako účinek klíčového slova o délce 5, jež se mezi prvním a druhým zašifrováním zopakovalo 195. Druhá opakující se sekvence P-S-D-L-P může být objasněna jako účinek klíče o délce 5, který se mezi oběma výskyty téže fráze zopakoval jen jednou. Třetí sekvence W-C-X-Y-M odpovídá klíčovému slovu o délce 5, jež se mezi oběma výskyty zopakovalo čtyřikrát. Čtvrtá E-T-R-L je vysvětlitelná klíčovým slovem o délce 5, jež se mezi oběma výskyty zopakovalo 245. Zkrátka a dobře, vše nasvědčuje tomu, že klíčové slovo má 5 písmen.
Za tohoto předpokladu se pokusíme zjistit, jak klíčové slovo zní. Prozatím si jej označíme jako L1-L2-L3-L4-L5, přičemž L1 označuje první písmeno klíče a tak dále. Šifrování probíhalo tak, že první písmeno otevřeného textu bylo zašifrováno pomocí prvního písmene klíče, tedy L1. Je to právě L1, které definuje jeden z řádků Vigenčrova čtverce a tím určuje monoalfabetickou substituční šifru pro první znak zprávy. Druhý znak otevřeného textu se šifruje pomocí L2, jež definuje jiný řádek Vigenčrova čtverce a tím i jinou monoalfabetickou substituční šifru. Třetí písmeno otevřeného textu se šifruje pomocí L3, čtvrté pomocí L4, páté pomocí L5. Každé písmeno klíče určuje jinou šifrovou abecedu. Avšak šesté písmeno otevřeného textu se šifruje znovu pomocí L1, sedmé pomocí L2 a cyklus se dál opakuje. Jinými slovy, polyalfabetická šifra sestává z pěti monoalfabetických šifer a každá z nich šifruje jednu pětinu textu zprávy. Monoalfabetickou substituční šifru, jak známo, luštit dovedeme.
Dál pokračujeme následujícím způsobem: víme již, že jeden z řád-ků Vigenčrova čtverce, definovaný písmenem L1, tvoří šifrovou abecedu pro 1., 6., 11., 16., … znak zprávy. Pokud tedy vezmeme z šifro-vého textu právě tyto znaky, budeme je moci podrobit staré dobré frekvenční analýze. Obrázek 14 ukazuje, jak dopadla frekvenční analýza těchto znaků, jimiž jsou W, I, R, E. Připomeňme si na tomto místě, že každá šifrová abeceda ve Vigenčrově čtverci je obyčejnou abecedou posunutou o nějakou hodnotu mezi 1 a 26. Frekvenční distribuce na obrázku 14 má proto stejné vlastnosti jako frekvenční distribuce obyčejné anglické abecedy, jen s tím rozdílem, že její počátek je posunut o nějakou neznámou hodnotu. Porovnáním dis-tribuce L1 s distribucí normální abecedy by se nám mohlo podařit zjistit, o jaké posunutí se jedná. Obrázek 15 ukazuje standardní frekvenční rozložení anglického textu.
Standardní rozložení má své vrcholy, údolí a náhorní plošiny. Když se je snažíme srovnat s rozložením L1, je třeba se zaměřit na jeho nejvýraznější rysy. Tak například tři vrcholy R-S-T v normálním rozložení (obrázek 15) a napravo od nich dlouhý pokles, jež se táhne přes šest písmen od U až po Z, představuje velmi zřetelný vzor. Jediným podobným útvarem v rozložení L1 (obrázek 14) jsou tři vrcholy u V-W-X následované poklesem přes šest písmen od Y po D. Z toho by se dalo usoudit, že všechny znaky šifrované pomocí L1 jsou oproti normální abecedě posunuty o čtyři písmena (čili že L1 je abecedou, která zní E, F, G, H, …) a že samo L1 – první písmeno klíčového slova – je písmeno E. Tuto hypotézu je možné testovat tak, že posuneme rozložení L1 o čtyři písmena nazpět a porovnáme je se standardním rozložením. Obrázek 16 ukazuje takové srovnání. Shoda je značná a dá se z ní usoudit, že L1 můžeme skutečně pokládat za E.
Shrňme dosavadní postup. Hledání opakujících se sekvencí v šif-rovém textu nám umožnilo identifikovat délku klíče; ten má pět znaků. Díky této znalosti jsme mohli rozdělit šifrový text na pět částí, z nichž každá je šifrována jednou monoalfabetickou substituční šifrou. Analýzou té části šifrového textu, jež odpovídá prvnímu písmenu klíče, jsme zjistili, že toto písmeno L1 je patrně E. Tento proces můžeme nyní zopakovat pro 2., 7., 12., 17., … znak šifrového textu. Odpovídající rozložení, jež vidíme na obrázku 17, je třeba znovu porovnat se standardním rozložením a zkusit uhodnout délku posunutí.
Tentokrát je to těžší. Žádné tři vrcholy odpovídající R-S-T nejsou vidět. Na druhou stranu, pokles mezi G a L je velmi výrazný a mohl by odpovídat písmenům U až Z z normálního rozložení. Pokud by tomu tak bylo, pak by se tři vrcholy R-S-T měly objevit u D-E-F, avšak vrchol u E chybí. Prozatím to budeme považovat za statistickou chybu a držet se názoru, že pokles mezi G a L ukazuje správný směr. Potom by platilo, že všechna písmena šifrovaná pomocí L2 jsou posunuta o 12 pozic a že L2 definuje šifrovou abecedu M, N, O, P,……,
a proto L2 = M. Tuto hypotézu lze opět testovat posunutím L2 o 12 písmen nazpět a porovnáním se standardním rozložením. Obrázek 18 ukazuje obě distribuce po této operaci a je z něj vidět, že shoda je značná, a proto můžeme L2 pokládat za M.
Dál již v podrobné analýze nebudu pokračovat. Postačí, když uvedu, že analýzou 3., 8., 13., … znaku zjistíme, že třetím písmenem klíče je I, analýza 4., 9., 14., … znaku ukáže, že čtvrtým písmenem klíče je L, a konečně z 5., 10., 15., … znaku zjistíme, že pátým písmenem je Y. Klíčové slovo zní EMILY. Teď již lze Vigenčrovu šifru normálním způsobem dešifrovat. První písmeno šifrového textu je W a bylo zašifrováno pomocí prvního písmene klíče, jímž je E. Podíváme se do Vigenčrova čtverce, najdeme W v řádku, jenž začíná písmenem E, a zjistíme, které písmeno je na vrcholu příslušného sloupce. Jde o s, které tak je prvním písmenem otevřeného textu. Opakováním procesu zjistíme, že otevřený text začíná písmeny sittheedownandhavenoshamecheekbyjowl…
Vložíme-li mezi slova mezery a interpunkci, dostaneme nakonec:
Sit thee down, and have no shame,
Cheek by jowl, and knee by knee:
What care I for any name?
What for order or degree?
Let me screw thee up a peg:
Let me loose thy tongue with wine:
Callest thou that thing a leg?
Which is thinnest? thine or mine?
Thou shalt not be saved by works:
Thou hast been a sinner too:
Ruined trunks on withered forks,
Empty scarecrows, I and you!
Fill the cup, and fill the can:
Have a rouse before the morn:
Every moment dies a man,
Every moment one is born.
Jde o verše z básně Alfreda Tennysona, jež se jmenuje The Vision of Sin (Představa hříchu). Klíčové slovo je křestním jménem Tennysonovy manželky Emily Sellwoodové. Tento úryvek jsem zvolil právě proto, že se stal příčinou kuriózní korespondence mezi Babbagem a velkým básníkem. Babbage jako nadšený statistik a autor tabulek mortality byl podrážděn veršem „Every moment dies a man/Every moment one is born“ (Každou chvíli člověk zemře/a jiný se narodí). Navrhl proto vylepšení Tennysonovy „jinak pěkné“ básně:
„Je třeba zdůraznit, že kdyby toto byla pravda, pak by celková populace světa zůstávala neměnná… Dovoluji si navrhnout, abyste v příštím vydání své verše opravil na znění: ‚Každou chvíli člověk zemře/a 1 1/16 jiného se narodí.‘ … Přesná hodnota má příliš mnoho desetinných míst, než aby se vešla na jeden řádek, avšak mám za to, že číslo 1 1/16 představuje přesnost dostatečnou pro účely poezie.
S pozdravem
Charles Babbage.“
Babbage si s Vigenčrovou šifrou úspěšně poradil patrně roku 1854, krátce po střetu s Thwaitesem, avšak o jeho objevu se nikdo nedověděl, protože jej nepublikoval. Vyšel najevo až při průzkumu jeho poznámek ve 20. století. Stejný postup mezitím objevil nezávisle na Babbagovi vysloužilý důstojník pruské armády Friedrich Wilhelm Kasiski. Od roku 1863, kdy jej publikoval v knize Die Geheimschriften und die Dechiffrirkunst (Tajné šifry a umění je dešifrovat), je příslušná technika známa jako Kasiského test. Babbagův vklad byl zcela ignorován.
Proč Babbage nepublikoval prolomení tak silné šifry? Je známo, že měl ve zvyku zanechávat projekty v nedokončeném stavu a nepublikovat výsledky, takže by se mohlo jednat o další projev jeho flegmatické povahy. Existuje však i jiné vysvětlení. Babbagův objev přišel krátce poté, co vypukla krymská válka. Podle jedné z teorií tím získala britská rozvědka převahu nad Rusy. Je klidně možné, že výzvědná služba požádala Babbage, aby svůj objev utajil, a poskytl jí tak před zbytkem světa devítiletý náskok. Je-li tento názor pravdivý, zapadá dobře do dlouholeté tradice utajování kryptoanalytických objevů v zájmu národní bezpečnosti – tradice, jež pokračuje do dnešních dnů.
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 Science Worldu 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
Omlouváme se za problémy s přidáváním komentářů k článkům. Komentáře prosím zasílejte e-mailem na pavel_houser@idg.cz.
celá kapitola o Vigenerově šifře ke stažení
poznámka: dokument vznikl exportem z DTP programu, omluvte prosím jeho kvalitu (a budiž to motivací i k opatření tištěné knihy :-))
