Přejít na obsah






Doporučeno
Fotka
* * * * * 2 hlasy

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

Příspěvek od pankun , 22 duben 2016 · 31 208 Zobrazení

doporučení návod
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)

Přiložený soubor  Frekvenční analýza.pdf (620,24K)
Počet stažení: 1817


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

B) 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)
Vložený obrázek

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

Vložený obrázek
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:

Vložený obrázek
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:
Vložený obrázek
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ě:
Vložený obrázek

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:
Vložený obrázek

Vložený obrázek
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:

Vložený obrázek

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

a výsledný text:

Vložený obrázek

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á. :)
Přiložený soubor  fa text 2.pdf (17,79K)
Počet stažení: 886

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

  • 8



Něco se nepovidlo. Odkaz na excelovou tabulku píše že soubor je v jiném formátu a když ho otevřu, je tam jen věta Tento soubor nelze editovat.

    • 0
Diky za info. Odpoledne to poresim a soubor nahraju jinam.
    • 0

Ahoj, prolítnul jsem Tvoje PDF-ko a bylo to příjemné čtení. Nevím jak je to programátorsky náročné, ale doporučoval bych doplnit ještě analýzu bi a trigramů. Občas mi tyto dvě věci při luštění významně pomohly.

    • 0
Tak to PDF je nádherně názorné. Fa.xls nemám v excelu mobilu podporováno.
    • 0
Aha, soubor má 28 bytů a obsahuje větu: Tento soubor nelze editovat.
    • 0

Nahrál jsem, snad již funkční xls soubor. Odkazy ke stažení by měly být funkční. Pokud bude problém, dejte vědět. 

    • 0

Nahrál jsem, snad již funkční xls soubor. Odkazy ke stažení by měly být funkční. Pokud bude problém, dejte vědět. 

3 x sláva, podařilo se mi obelstít i blog a přidat obrázky :))   Snad už bude vše fungovat bez problémů

    • 0

Ahoj, prolítnul jsem Tvoje PDF-ko a bylo to příjemné čtení. Nevím jak je to programátorsky náročné, ale doporučoval bych doplnit ještě analýzu bi a trigramů. Občas mi tyto dvě věci při luštění významně pomohly.

Ahoj, analýzu bigramů, trigramů a pár odkazů na frekvence výskytů českých slov plánuji přidat do pokračování. Určitě je také zajímavá frekvence výskytu znaků na začátcích a koncích slov, případně písmen, která se objevují samostatně.. Témat je spousta, času málo. :)

    • 0

Fa.xls už je excelovský a už se v něm dá hrabat. Díky. Díky. Díky.

    • 0

Hned jak jsem viděl tenhle blog mě napadlo tohle téma: http://www.geocachin...fra#entry463515. Jak by se s tím FA poprala?

    • 0

Hned jak jsem viděl tenhle blog mě napadlo tohle téma: http://www.geocachin...fra#entry463515. Jak by se s tím FA poprala?

v tomhle stavu ten excel nikoliv, u vigenerovy šifry je potřeba "odhadnout" délku hesla, přičemž počet znaků hesla určuje počet použitých abeced. dobře popsáno zde http://www.jifox.cz/...kvencni_analyza

    • 0

A co když jako heslo použiju jednu z werichovských jednoslabičných veršovánek, která nemá v jiných jazycích obdoby? Tam jde myslím FA do .....

    • 0

Opravdu zajímavý příspěvek. Škoda, že těch přínosných článků je tu opravdu málo. Díky moc.

    • 2
Fotka
jardavera
dub 20 2016 9:09

Nádhera!!! O to více smekám před lidmi, kteří prolomili Enigmu bez excelu a podobných "udělátek".....

    • 0

Nádhera!!! O to více smekám před lidmi, kteří prolomili Enigmu bez excelu a podobných "udělátek".....

No bez těch "udělátek" jak ty říkáš, by to fakt nešlo.... Poláci měli rejewského bombu, britové colossus (předchůdce dnešních PC).

    • 0

Připojen krátký zašifrovaný text na vyzkoušení FA. Přeju hodně zdaru s luštěním !

    • 0

Díky za bezva nástroj! Teď zrovna jsem s ním během pár minut rozluštil jednu mysterku, u níž bylo při pohledu na text jasné, že to je jednoduchá substituční šifra, ale dosud jsem nepřišel na to, jaká. Tedy po pravdě, na použitou šifru jsem nepřišel ani po vyluštění, ale text mám rozluštěný celý...

    • 0

Do textu jsem přidal odkaz na stažení nové verze FA (tedy FA2) Nyní umí i analyzovat Bigramy a Trigramy, automaticky rovnat výsledky + jsem upravil výpočet procentuálního výskytu znaků, tak aby to odpovídalo realitě. (dříve se počítal průměr ze všech znaků včetně mezer, nyní bere jen a-z)

    • 0

Pěknej návod i excelovské pomůcky. Velké díky...
 
Doplnil jsem si jen automatickou náhradu písmen, pokud se změní definice substituce. Abych nemusel furt mačkat tlačítko. Stačí do programu na listu "Frekvenční analýza" přidat:
 

Private Sub Worksheet_Change(ByVal Target As Range)
    Dim KeyCells As Range
    Set KeyCells = Range("E2:E27")
    If Not Application.Intersect(KeyCells, Range(Target.Address)) Is Nothing Then
          Substituce
          SubstituceHvezda
    End If
End Sub
    • 0

 

Pěknej návod i excelovské pomůcky. Velké díky...
 
Doplnil jsem si jen automatickou náhradu písmen, pokud se změní definice substituce. Abych nemusel furt mačkat tlačítko. Stačí do programu na listu "Frekvenční analýza" přidat:
 

Private Sub Worksheet_Change(ByVal Target As Range)
    Dim KeyCells As Range
    Set KeyCells = Range("E2:E27")
    If Not Application.Intersect(KeyCells, Range(Target.Address)) Is Nothing Then
          Substituce
          SubstituceHvezda
    End If
End Sub

Díky za kód. Připojil jsem ho k FA2 a je k dispozici ke stažení.

    • 0

Reklama