Pokročílá frekvenční analýza

V tomto článku vám představím pokročilou frekvenční analýzu, pomocí které je možno vyluštit šifru zašifrovanou pomocí Vigenerovy šifry a je tak mocným nástrojem kryptoanalytika. Pokud nevíte ještě nic o Vigenerově šifře, tak doporučuji se podívat na článek Vigenerova šifra, kde naleznete kompletní popis této šifry. Pokročilou frekvenční analýzu vymyslel Charles Babage, který se také proslavil koncepčním návrhem moderního počítače. Luštění této šifry je obtížnější než u obyčejné monoalfabetické substituční šifry. Tím, že je možno použít až 26 šifrových abeced, tak frekvence četnosti znaků jsou mnohem vyrovnanější a také může být jeden znak zašifrován více zůsoby, tak nám obyčejna frekvenční analýza nebude stačit a budeme muset použít pokročilou frekvenční analýzu. Také bych vám možná doporučil si nejdříve přečíst článek o Frekvenční analýze abyste věděli, co to frekvenční analýza je.

Jako vždy, způsob dešifrování vysvětlím na příkladu, což je nejlepší způsob, jak celý proces dešifrování pochopit. Vysvětlím ho na příkladu anglického textu. Velice dobrý příklad je v knize Kniha kódů a šifer, takže ho použiji i v tomto článku. Řekněme teda, že jsme zachytili tento zašifrovaný text:

Šifrový text
První krok kryptoanalýzy spočívá v hledání sekvencí, které se opakují 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 stejnou částí klíče. Dále také 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 stejný tentýž výsledek. Omezíme-li se na delší sekvence, tak 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 následující tabulce je seznam těchto 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 a vzdálenosti mezi oběma výskyty je 95 písmen.

Tabulka 1
Klíčové slovo se používá jak k šifrování, tak k dešifrování. Jestliže jej dokážeme indentifikovat, tak dešifrování již pak bude snadné. Zatím nemáme dost informací, abychom ho mohli identifikovat, ale tato tabulka nám poskytuje dobrou nápovědu, pokud jde o délku klíčového slova. Kromě tohoto tabulka také obsahuje 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 co dvacet písmen, 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 nám plyne 6 možností.

Klíč tvoří 1 písmeno a opakuje se 20x mezi sekvencemi.
Klíč tvoří 2 písmena a opakuje se 10x mezi sekvencemi.
Klíč tvoří 4 písmena a opakuje se 5x mezi sekvencemi.
Klíč tvoří 5 písmen a opakuje se 4x mezi sekvencemi.
Klíč tvoří 10 písmen a opakuje se 2x mezi sekvencemi.
Klíč tvoří 20 písmen a opakuje se 1x mezi sekvencemi.

První možnost můžeme vyloučit, protože klíč o délce jednoho znaku by odpovídal monoalfabetické šifře. Zaznačíme tedy všechny možnosti do tabulky. To nám indikuje možnou délku klíče. Abychom určili, jestli je klíč dlouhý 2, 4, 5, 10 nebo 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 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. 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 10x. Druhá 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 zopakoval 4x. Čtvrtá sekvence E-T-R-L se dá vysvětlit klíčovým slovem o délce 5, který se mezi oběma výskyty zopakoval 24x. Vše teda nasvědčuje tomu, že klíčové slovo má 5 písmen.

Pomocí tohoto předpokladu se pokusíme zjistit klíčové slovo. 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. L1 právě definuje jeden z řádků Vigenerova č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 Vigenerova čtverce. Třetí písmeno se šifruje pomocí L3, čtvrté pomocí L4 a pátek pomocí L5. Každé písmeno otevřeného textu 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 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. A monoalfabetickou šifru již luštit dovedeme. Pokud ne, tak si přečtěte tento článek o Frekvenční analýze.

Dále pokračujeme následujícím způsobem. Víme již, že jeden z řádků Vigenerova čtverce, definovaný písmenem L1, tvoří šifrovou abecedu pro 1., 6., 11., 16., ... znak zprávy. Pokud tedy vezmeme z šifrovaného textu právě tyto znaky, budeme je moci podrobit staré dobré frekvenční analýze. Ná následujícím obrázku vidíte, jak dopadla frekvenční analýza těchto znaků, jimiž jsou W, I, R, E. Připomeňme si, že každá šifrová abeceda ve Vigenerově čtverci je obyčejnou abecedou posunutou o nějakou hodtnou mezi 1 a 26. Frekvenční distribuce na následujícím obrázku 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 distribuce L1 s distribucí normální abecedy by se nám mohlo podařit zjistit, o jaké posunutí se jedná. Na spodním obrázku vidíte standardní rozložení anglického textu.

Tabulka 2 a 3
Standardní rozložení má své vrcholy, údolí a náhorní plošiny. Když se je snažíme srovna 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í a napravo od nich dlouhý pokles, který 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 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 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 provnáme je se standardním rozložením. Na následujícím obrázku vidíte toto srovnání. Shoda je značná a dá se z ní usoudit, že L1 můžeme skutečně pokládat za E.

Tabulka 4 a 5
Hledáním opakujících se sekvencí v šifrovém textu nám umožnilo identifikovat délku klíče, který 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, která odpovídá prvnímu písmenu klíče, jsme zjistili, že toto písmeno L1 je patrně E. Tento proces nyní můžeme zopakovat pro 2., 7., 12., 17., ... znak šifrového textu. Odpovídající rozložení, jež vidíme na dalším obrázku, je třeba znovu porovnat se standardním rozložením a zkusit uhodnout délku posunutí.

Tabulka 6
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 UZ 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 otestovat posunutím L2 o 12 písmen nazpět a porovnáním se standardním rozložením. Na následujícím obrázku vidíte 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.

Tabulka 7
Dál již v analýze pokračovat nebudu, to už snad zvládnete sami. :-) Další analýzou bychom zjistily, že L3 = I, L4 = L a L5 = Y. Tímto jsme zjistili klíčové slovo, pomocí kterého byl zašifrování náš šifrový text. Po dešifrování zašifrovaného textu dostaneme tohle:

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 lose 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). Takže tímto článkem jsem se pokusil vysvětlit pokročilou frekvenční analýzu, která slouží k dešifrování Vigenerovy šifry. Tato kryptoanalýza je trochu těžší, takže doufám, že ji pochopíte. Pokud ne, nebo budete mít jakékoli jiné dotazy, tak opět zanechte vzkaz v komentáři.