Frekvenční analýza

Jen tak na úvod bych řekl, že frekvenční analýzu vymysleli Arabové, kteří již v 9. století byli v tomto směru o dost vyspělejší, než ve střední Evropě. Frekvenčí analýza je v podstatě taky založená i na lingvistických znalostech. V podstatě je to zjištění frekvence použitých znaků a porovnáním s frekvencí znaků daného jazyka a potom pomocí trochy znalostí daného jazyka ji dešifrovat až do konce. Tohle se ovšem nedá jen tak jednoduše vysvětlit, takže rovnou pojďme na jeden příklad, na kterém si vše názorně ukážeme a vše se pokusím vhodně popsat. I když je frekvenční analýza založena hodně na logické úvaze, budete také potřebovat trochu intuice a jisté lstivosti. Jako příklad použiji anglický text.

Takže jako první začneme tím, že s si zanalyzujeme nějaký delší úsek anglického textu. Vhodné jsou například noviny, beletrie atd. Čím delší text, tím je frekvece přesnější. Já tady použiji tabulku, kterou sestavili H. Beker a F. Piper.

ZnakČetnostZnakČetnost
a8,2n6,7
b1,5o7,5
c2,8p1,9
d4,3q0,1
e12,7r6,0
f2,2s6,3
g2,0t9,1
h6,1u2,8
i7,0v1,0
j0,2w2,4
k0,8x0,2
l4,0y2,0
m2,4z0,1



A nyní zašifrovaný text. Jak jsem se již zmínil v jednom z minulých článků, tak šifrový text se většinou kvůli přehlednosti píše velkými písmeny a otevřený text malými. Tímto pravidlem se budu řídit i u tohoto příkladu. Takže řekněme, že se k nám dostala tahle zašifrovaná zpráva:

PCQ VMJYPD LBYK LYSO KBXBJXWXV BXV ZCJPO EYPD KBXBJYUXJ LBJOO KCPK. CP LBO LBCMKXPV XPV IYJKL PYDBL. QBOP KBO BXV OPVOV LBO LXRO CI SX'XJMI, KBO JCKO XPV EYKKOV LBO DJCMPV ZOICJO BYS, KXUYPD: "DJOXL EYPD, ICJ X LBCMKXPV XPV CPO PYDBLK Y BXNO ZOOP JOACMPLYPD LC UCM LBO IXZROK CI FXKL XDOK XPV LBO RODOPVK CI XPAYOPL EYPDK. SXU Y SXEO KC ZCRV XK LC AJXNO X IXNCMJ CI UCMJ SXGOKLU?"
OFYRCDMO, LXROK IJCS LBO LBCMKXPV XPV CPO PYDBLK


A nyní si uděláme frekvenční analýzu našeho zašifrovaného textu.

ZnakPočet výskytůV procentechZnakPočet výskytůV procentech
A30,9N30,9
B257,4O3811,2
C278,0P319,2
D144,1Q20,6
E51,5R61,8
F20,6S72,1
G10,3T00,0
H00,0U61,8
I113,3V185,3
J185,3W10,3
K267,7X3410,1
L257,4Y195,6
M113,3Z51,5



Tím, že šifrovaná zpráva je celkem krátká, tak frekvenční analýzu nemůžeme jen tak jednoduše aplikovat na text, protože ne všechny znaky mají stejnou četnost, takže ne všechny znaky bychom hned zjistili správně. Zkusíme se teda soustředit na 3 znaky, které se v šifrovém textu vyskytují více než třicetkrát. Jedná se o písmena O, X a P. S velkou jistotou můžeme předpokládat, že nejběžnější znaky šifrového textu odpovídají nejběžnějším znakům anglické abecedy, ovšem nemusí nutně odpovídat pořadí. Nemůžeme si být například jisti, že O = e, X = t a P = a, ale můžeme předběžně odhadnout, že O = e, t nebo a, X = e, t nebo a a P = e, t nebo a. Nyní použijeme trochu jemnější formu frekvenční analýzy a podíváme se, jak často se jednotlivá písmena vyskytují v sousedství jiných. Například, sousedí písmeno O s mnoha různými písmeny, nebo je jeho výskyt vázán na několik konkrétních písmen? Tímto zjistíme, zda je O souhláska nebo samohláska. Pokud jde o samohlásku, bude se zřejmě vyskytovat vedle většiny ostatních písmen. Je-li to souhláska, bude se většině ostatních písmen vyhýbat. Například písmeno se se může v angličtině vyskytnout vedle každé jiné hlásky, zatímco písmeno t se sotva najde v kombinaci s b, d, g, j, k, m, q nebo v.

Nyní si sestavíme tabulku, která si všímá tří nejčastěji se vyskytující písmena O, X a P a shrnuje, jak často je nalezneme před nebo po jiném písmenu. Například písmeno O se vyskytuje před A jednou a po něm už vůbec, takže první políčko tabulky má hodnotu 1. Písmeno O nalezneme v sousedství většiny jiných hlásek a zcela se vyhnulo pouze sedmi, takže v prvním řádku tabulky je sedm nul. Stejně tak písmeno X, u kterého je osm nul. O dost méně se ovšem mezi ostatními hláskami vyskytuje P a patnácti se zcela vyhnulo. Zdá se tedy, že O a X rezprezentují samohlásky a P souhlásku.

 ABCDEFGHIJKLMNOPQRSTUVWXYZ
O19031110146012280410030112
X07011110246303190240332001
P105600000112208000000110990



Nyní je potřeba zjistit, které samohlásky se skrývají pod O a X. Pravděpodobně to budou hlásky e a a, nejběžnější anglické samohlásky. Zajímavostí našeho šifrového textu je třeba to, že OO v něm nalezneme dvakrát, zatímco XX ani jednou. V angličtině se kombinace ee vyskytuje mnohem častěji než aa, takže je pravděpodobné, že O = e a X = a. Tímto jsme spolehlivě identifikovali dvě z písmen šifrového textu. Taky nás ve správnosti ujišťuje i to, že X = a se objevuje v šifrovém textu samostatně. Slovo a (neurčitý člen) je jedním ze dvou anglických slov tvořeným jediným písmenem. Jediné další písmeno, které se v šifrovém textu vyskytuje samostatně, je Y, takže je velmi pravděpodobné, že reprezentuje jediné další anglické slovo I (osobní zájméno "já"). Zaměření se na jednopísmenná slova je jedna z užitečných metod, ovšem krytograf je většinou odstraní, aby ztížil analýzu.

Dále si zjistíme písmeno h, jelikož jsme již odhalili písmeno e a pro angličtinu je typický výskyt h před e, například slova the, then, they atd. Velmi vzácně se však vyskytuje po e. Na následující tabulce vidíme, jak často se písmeno O, o němž se domníváme, že reprezentuje písmeno e, vyskytuje. Z tabulky můžeme teda odvodit, že písmeno B reprezentuje pravděpodobně písmeno h, protože před O se vyskytuje devětkrát, zatímco po něm ani jednou.

 ABCDEFGHIJKLMNOPQRSTUVWXYZ
po 010010100104000250000020100
před 809021010042012230410010012



Nyní jsme již určili čtyři písmena O = e, X = a, Y = i a B = h. A teď nahradíme šifrový text již námi zjištěnými písmeny.

PCQ VMJiPD LhiK LiSe KhahJaWaV haV ZCJPe EiPD KhahJiUaJ LhJee KCPK. CP Lhe LaRe CI Sa'aJMI, Khe JCKe aPV EiKKev Lhe DJCMPV ZeICJe hiS, KaUiPD: "DJeaL EiPD, ICJ a LhCMKaPV aPV CPe PiDhLK i haNe ZeeP JeACMPLiPD LC UCM Lhe IaZReK CI FaKL aDeK aPV Lhe ReDePVK CI aPAiePL EiPDK. SaU i SaEe KC ZCRV aK LC AJaNe a IaNCMJ CI UCMJ SaGeKLU?"
eFiRCDMe, LaReK IJCS Lhe LhCMKaPV aPV CPe PiDhLK


A nyní můžeme identifikovat další písmena, protože už můžeme hádat některá slova. Nejčastější třípísmenná anglická slova jsou the a and. V našem šifrovém textu je rozeznáme celkem lehce. Lhe se vyskytuje šestkrát a aPV pěktrát, takže L je pravděpodobně písmeno t, P písmeno n a V písmeno d. Nyní opět nahradíme tyto písmena v našem šifrovém textu a dostaneme:

nCQ dMJinD thiK tiSe KhahJaWad had ZCJne EinD KhahJiUaJ thJee KCnK. Cn the thCMKand and IiJKt niDht. Qhen Khe had ended the taRe CI Sa'aJMI, Khe JCKe and EiKKed the DJCMnd ZeICJe hiS, KaUinD: "DJeat EinD, ICJ a thCMKand and Cne niDhtK i haNe Zeen JeACMntinD tC UCM the IaZReK CI FaKt aDeK and the ReDendK CI anAient EinDk. SaU i SaEe KC ZCRd aK tC AJaNe a IaNCMJ CI UCMJ SaGeKtU?"
eFiRCDMe, taReK IJCS the thCMKand and Cne niDhtK.


Jakmile víme s jistotou pár písmen, tak již kryptoanalýza jde celkem rychle. Například slovo na konci druhé věty zní Cn. Každé anglické slovo obsahuje samohlásku, takže C musí být samohláska. Zbývá identifikovat jen dvě samohlásky. A to u a o. U se nehodí, takže C musí reprezentovat o. Také v šifrovém textu nalezneme slovo Khe, což znamená, že K představuje buď t, nebo s. A protože už víme, že L = t, tak to znamená, že K = s. Když tato písmena vložíme do šifrového textu, objeví se slovní spojení thoMsand and one niDhts. Lze předpokládat, že jde o <>ithousand and one nights.

Pokud bychom takto pokračovali, tak za chvíli bychom dešifrovali celý text. Víme, že každý znak je nahrazen jiným znakem abecedy. Pojďme se podívat na rozložení znaků, které již známe:

Otevřená abecedaabcdefghijklmnopqrstuvwxyz
Šifrová abecedaX--VOIDBY--RSPC--JKLM-----



Když se podíváme na tabulku, tak to vypadá, že pro zašifrování byla použita fráze a zbytek jsou písmena v abecedním pořadí, ovšem kromě těch, která jsou již použita v té frázi. Podle odhadu by teda fráze mohla znít A VOID BY GEORGES PEREC, což by odstraněním mezer a opakujících se písmen znělo AVOIDBYGERSPC. Pak již dosadíme zbývající písmena a dostaneme celou naši šifrovou abecedu.

Otevřená abecedaabcdefghijklmnopqrstuvwxyz
Šifrová abecedaXZAVOIDBYGERSPCFHJKLMNQTUW



A po dešifrování našeho zašifrovaného textu dostaneme:

Now during this time Shahrazad had borne King Shahriyar three sons. On the thousand and first night, when she had ended the tale of Ma'aruf, she rose and kissed the ground before him, saying: "Great King, for a thousand and one nights I have been recounting to you the fables of past ages and the legends of ancient kings. May I make so bold as to crave a favor of your majesty?"
Epilogue, Tales from the Thousand and One Nights


Doufám, že vám tento návod hodně pomohl naučit se dešifrovat pomocí frekvenční analýzy, protože se pomocí ní dá dešifrovat hodně druhů šifer a nezáleží, jestli kryptograf použil pro zašifrování jinak poskládanou abecedu nebo úplně jiné znaky. Jenom bych ještě upozornil, že se taky pro ztížení kryptoanalýzy používají tzv. nulové znaky, které nereprezentují žádný znak, nebo mají nějako funkci, například, že mažou předchozí znak. Tím se kryptoanalýza ztěžuje, ale pokud budete trochu více přemýšlet, zvládnete dešifrovat i takto zašifrovaný text s různými nástrahami.

A úplně nakonec bych ještě dodal, že příklad tohoto textu jsem převzal z knihy "Kniha kódů a šifer", ze které jsem také hodně čerpal.