Frekvenční analýza a luštění substituční šifry pro začátečníky

Ahoj,

Na fóru jsem našel několik vláken s dotazy na téma použití frekvenční analýzy, ale spíš takové obecné řeči - nic konkrétního.

To bych rád změnil a tímto se dělím o zkušenost s luštěním pomocí frekvenční analýzy.

Obsah tohoto článku jsem uložil do pdf a připojil ho k blogu,

Excelový soubor pro rozšifrování textu najdete zde v několika verzích:

Verze 1 - Frekvenční analýza .(umí jen analyzovat četnost výskytu znaků)
Verze 2 - Frekvenční analýza 2 (doplněna analýza Bigramů a Trigramů, automatické rovnání výsledků + upraveno počítání % v tabulce frekvenční analýzy)

 Frekvenční analýza.pdf (620,24K)
Počet stažení: 2001


Frekvenční analýza a substituční šifra pro začátečníky:

Před nějakou dobou jsem luštil jednu obzvláště vypečenou mystery keš z okolí Plzně. Když jsem vyčerpal všechny dobré nápady, došlo na frekvenční analýzu (FA). Prohledal jsem internet a nalezl několik slušných stránek o tom, jak frekvenční analýza funguje a dokonce stáhnul i pár šifrovacích programů, které FA umějí. Žádný z programů, ale nedokázal uživatelsky přívětivě proměnit výsledek analýzy v rozšifrovaný text. To mě přimělo vytvořit vlastní jednoduchý program, díky kterému se mi podařilo šifru rozluštit. V tomto krátkém článku bych se rád podělil o program samotný a o zkušenosti s jeho použitím.
1) Co je frekvenční analýza? Stručně řečeno, je to analýza frekvence, tedy četnosti výskytu jednotlivých znaků v textu. Pokud máme například text o 100 písmenech a písmenko „A“ se v něm vyskytuje 10x, „B“ 5x a „C“ 1x, znamená to, že průměrná četnost písmena „A“ v daném textu je 10%, „B“ 5% a „C“ 1%... Tímto způsobem zjistíme četnost výskytu všech v textu obsažených znaků. Důležité je zmínit, že v každém jazyce jsou výskyty písmen různé. Tedy četnost výskytu písmene „a“ v Češtině se bude lišit od četnosti výskytu písmene „a“ v Angličtině. Na internetu se dají najít frekvence znaků pro většinu řečí, Češtinu nevyjímaje. Další důležité upozornění je, že záleží na velikosti referenčního vzorku (čím více textu, tím přesnější čísla) a na druhu textu, který analyzujete.
Například kapitola o chovu okounů bude mít jinou četnost výskytu písmene „O“, než například text písničky Královské Rege, kde zase bude výrazně vyšší četnost písmene „R“.

K čemu to mohu využít? Frekvenční analýzu je možné použít na luštění různých mono/polyalfabetických substitučních šifer – jednoduše – když jsou v textu nahrazena písmena jinými písmeny. Například: nezašifrovaný text: „Harry Potter „ Zašifrovaný text: „jsttx úpzzrt“.
Případně, když jsou písmena nahrazena znaky, nebo obrázky.

2) Jak to využít v praxi? Uvádím příklad.
K rozluštění mám následující text:

„ABCEDFG HIJAJ KAL GUIBMHA NA OKFKEGHAHF A OELEPIHUNGF CNIKYJF LECNEK GDABM OKEODINA UGI NIJOIKAJIHNHF KIBF VZHAGAJ ZI HA NEJ HAZEKHIJ OKFCDALV U CAGAKHEV BDEGICIJ A JFUEV CEPDFM HIBE SI DZI HA HIJ AUOEH OKFPDFZHI VCAZAN SACYJ BDEGICIJ SI UANVKHFH LECNEK GDABM UF NENFZ KEZLIDFD DFLF OELDI NEME SAC UI BMEGASF G OEDEOKAZLHI CAGAKHI JASFDF OKIL UIPEV JFUV CEPDFM OKILUNAGNI UF DVXVUHF CAGAKHV ZA HILIDHFME ELOEDILHI GIHCV SI CKAUHY LIH A MEUNV G CAGAKHI SI JADE VZ SUNI UI HAUHFLADF OKIBINDF SUNI GUIBMHY HEGFHY A NIL SUNI UI OEMELDHI EOKIDF G JICCIJ PEXV A ZAJYUDIHI UI LFGANI HA JFUV CEPDFM HVLA UI OEJADV KEZDIZA LE GUIBM CEVNV CAGAKHY A NV UI NILY JA VCAZAN LE CNIKI UCVOFHY DFLF OELDI NIEKFI LECNEKA GDABMA OANKFNI SUNIDF OKY BDEGICIJ PIZ QAHNAZFI PIZ NEVMY OE LYHAJFBI A PIZ UJYUDV OKE MVJEK PVLINI UI HA NY CEPDFMY LFGAN NVOI A PIZJYUDIHCEGFNI NKIPA AZ LE OEDILHI A OAC UI ZGILHINI A OVSLINI C EPILV JAJ LVGELHI OELIZKIHF ZI LE NINE OKGI UCVOFHY ZAKAZVSI LECNEK GDABM NACI JHI JYUDFJ ZI HIHF G OKAGV E MVJEKV A E NI LYHAJFBI HIPVLIJI JDVGFN ADI NE ZI JF VOFKA QAHNAZFF CLYZ GF ZI UI JF OEGILDE UOKAGHI„

a) Jako první krok přiřadíme každému symbolu jedno písmeno z naší abecedy, abychom mohli zanalyzovat. Nejsnazší postup je začít u A, a pokračovat přes B…. až do Z. Výsledkem bude:
„ABCEDFG HIJAJ KAL GUIBMHA NA OKFKEGHAHF A OELEPIHUNGF CNIKYJF LECNEK GDABM OKEODINA UGI NIJOIKAJIHNHF KIBF VZHAGAJ ZI HA NEJ HAZEKHIJ OKFCDALV U CAGAKHEV BDEGICIJ A JFUEV CEPDFM HIBE SI DZI HA HIJ AUOEH OKFPDFZHI VCAZAN SACYJ BDEGICIJ SI UANVKHFH LECNEK GDABM UF NENFZ KEZLIDFD DFLF OELDI NEME SAC UI BMEGASF G OEDEOKAZLHI CAGAKHI JASFDF OKIL UIPEV JFUV CEPDFM OKILUNAGNI UF DVXVUHF CAGAKHV ZA HILIDHFME ELOEDILHI GIHCV SI CKAUHY LIH A MEUNV G CAGAKHI SI JADE VZ SUNI UI HAUHFLADF OKIBINDF SUNI GUIBMHY HEGFHY A NIL SUNI UI OEMELDHI EOKIDF G JICCIJ PEXV A ZAJYUDIHI UI LFGANI HA JFUV CEPDFM HVLA UI OEJADV KEZDIZA LE GUIBM CEVNV CAGAKHY A NV UI NILY JA VCAZAN LE CNIKI UCVOFHY DFLF OELDI NIEKFI LECNEKA GDABMA OANKFNI SUNIDF OKY BDEGICIJ PIZ QAHNAZFI PIZ NEVMY OE LYHAJFBI A PIZ UJYUDV OKE MVJEK PVLINI UI HA NY CEPDFMY LFGAN NVOI A PIZJYUDIHCEGFNI NKIPA AZ LE OEDILHI A OAC UI ZGILHINI A OVSLINI C EPILV JAJ LVGELHI OELIZKIHF ZI LE NINE OKGI UCVOFHY ZAKAZVSI LECNEK GDABM NACI JHI JYUDFJ ZI HIHF G OKAGV E MVJEKV A E NI LYHAJFBI HIPVLIJI JDVGFN ADI NE ZI JF VOFKA QAHNAZFF CLYZ GF ZI UI JF OEGILDE UOKAGHI „

Nyní přijde na řadu frekvenční analýza. Doporučuji otevřít excelovský soubor a prohlédnout si ho.

Do políčka F6 – s popisem Zkoumaný text nakopírujeme text, který jsme získali převodem znaků na písmena. (Bude to vypadat asi takto)


Vlevo ve sloupci D jsou uvedeny vzorové četnosti výskytů znaků v Českém jazyce.
A zmáčkněte tlačítko „Analyzuj!“


V políčku Upravený text se nám zpráva automaticky převede na malá písmena, odstraní se diakritika a další znaky, které nechceme.
Nyní můžete prozkoumat výsledky Frekvenční analýzy:


Na první pohled jsou vidět rozdíly mezi četnostmi znaků v analyzovaném textu a vzorové četnosti. (např. znak „O“ je v textu obsažen 2%, kdežto v běžné řeči až 8,1%....)
Je dobré všechny hodnoty srovnat podle četnosti. (v Excelu nakopírujeme na další list a srovnáme)

Výsledek bude vypadat takto:

Co nám to říká? Analýza říká, že znak „I“ v zašifrovaném textu odpovídá znaku „E“ v rozšifrované podobě, A odpovídá A, E odpovídá O ……..
Nyní musíme ověřit, zda to funguje i v praxi.
Do sloupečku E (Substituce) je třeba ručně přiřadit písmena podle výsledků analýzy. Je dobré začít několika nejpoužívanějšími znaky. ( Pro ukázku doplním 5 nejčastějších.) Doplněná tabulka bude vypadat následovně:


Po doplnění písmen, která chcete nahradit, zmáčkněte tlačítko „Substituce !“
Další dvě políčka se nám zaplnila textem. Výsledkem je následující zpráva:



Pokud se analýza nespletla, máme dobrý základ pro odhadnutí dalších znaků. Pokud se analýza spletla, je dobré mezi sebou prohodit několik nejfrekventovanějších znaků, než dostaneme výsledek, který se nám bude zdát smysluplný. Horní buňka „Substituce“ kombinuje rozšifrovaná písmena (psaná Velkými písmeny) s původním textem. Druhá buňka ukazuje rozšifrovaný text + nahrazuje původní text znakem hvězdičky.
Myslím, že nyní můžeme uhodnout několik dalších znaků a slov. (druhé slovo NEjAj by mohlo být slovem NEMAM = J v zašifrované podobě odpovídá M) Slovo nEMoEkAMENnNI by mohlo být TEMPERAMENTNI = n – T, o – P, k – R,)
! Po každé změně v tabulce Substituce, je třeba znovu zmáčknout tlačítko „Substituce !“

Nyní výsledky vypadají takto:



Stejným způsobem pokračujeme dál, dokud nedoplníme matrici. Finální podoba substituce znaků bude následující:


a výsledný text:



Snadné, že?

c) Tipy a triky.
- Na adrese http://www.mojepixwords.cz/napoveda/ funguje vyhledávání slov podle písmen. Prázdné znaky jsou nahrazovány hvězdičkami. Stačí tedy slovo nakopírovat z buňky obsahující písmena proložená hvězdičkami. (T6)

d) Jak to celé funguje? Soubor je ve formátu Excel a používá funkce VBA. (je třeba povolit)
Soubor dávám k dispozici pro další úpravy a testování.

Přeji hodně zdaru s luštěním. V případě dotazů mě kontaktujte na emailu: pankun@centrum.cz



Předpokládám, že si většina čtenářů FA otestovala a našla nějaký zašifrovaný text na internetu, nebo se s chutí vrhla na kešky, které dlouho odolávaly. Pro ty, kteří by návod rádi vyzkoušeli a nemají zrovna žádný vhodný text k rozluštění, přikládám jeden krátký textík, který si o rozšifrování pomocí FA přímo říká.
 fa text 2.pdf (17,79K)
Počet stažení: 1018

Poznáte někdo, ze které je to knihy?