Frekvenční analýza , frekvenční kryptoanalýza - jedna z metod kryptoanalýzy , založená na předpokladu existence netriviálního statistického rozložení jednotlivých znaků a jejich sekvencí, jak v prostém textu, tak v šifrovém textu, který až do nahrazení znaků , budou zachovány v procesu šifrování a dešifrování .
Zjednodušeně frekvenční analýza předpokládá, že četnost výskytu daného písmene abecedy v dostatečně dlouhých textech je stejná pro různé texty stejného jazyka. Zároveň v případě monoalfabetického šifrování , pokud je v šifrovém textu znak s podobnou pravděpodobností výskytu, pak můžeme předpokládat, že se jedná o uvedené zašifrované písmeno. Podobná úvaha platí pro bigramy (dvoupísmenné sekvence), trigramy atd. v případě polyalfabetických šifer .
Metoda frekvenční kryptoanalýzy je známá již od 9. století (práce Al-Kindiho ), i když asi nejznámějším případem její aplikace v reálném životě je rozluštění egyptských hieroglyfů J.-F. Champollion v roce 1822. V beletrii jsou nejslavnějšími odkazy příběhy „The Gold-Bug “ od Edgara Allana Poea , „The Dancing Men “ od Conana Doyla a román „ Děti kapitána Granta “ od Julese Verna .
Od poloviny 20. století byla většina používaných šifrovacích algoritmů vyvinuta tak, aby odolávala frekvenční kryptoanalýze, takže se používá hlavně v procesu školení budoucích kryptografů.
Využívá toho, že pravděpodobnost výskytu jednotlivých písmen, stejně jako jejich pořadí ve slovech a frázích přirozeného jazyka, podléhá statistickým vzorcům: například dvojice písmen „sya“ stojící vedle sebe v Ruština je pravděpodobnější než „tsy“ a „ o “ se v ruštině vůbec nevyskytuje (ale často se vyskytuje například v Čečensku ). Analýzou dostatečně dlouhého textu zašifrovaného metodou nahrazování je možné provést zpětnou náhradu na základě četnosti výskytu znaků a obnovit původní text.
Jak bylo uvedeno výše, důležitými vlastnostmi textu jsou opakování písmen (počet různých písmen v každém jazyce je omezený), dvojice písmen, tedy m (m-gramů), vzájemná kompatibilita písmen . , střídání samohlásek a souhlásek a některé další rysy. Je pozoruhodné, že tyto vlastnosti jsou poměrně stabilní.
Cílem je spočítat počet výskytů každého n m možných m-gramů v dostatečně dlouhých otevřených textech T=t 1 t 2 …t l , složených z písmen abecedy {a 1 , a 2 , …, a n } . Současně jsou zobrazeny po sobě jdoucí m-gramy textu:
t 1 t 2 …t m , t 2 t 3 … t m+1 , …, t i-m+1 t l-m+2 …t l .
Jestliže L (a i1 a i2 … a im ) je počet výskytů m-gramu a i1 a i2 … a im v textu T , a L je celkový počet spočítaných m-gramů, pak pro dostatečně velké L frekvence L (a i1 a i2 … a im )/ L , pro daný m-gram se od sebe málo liší.
Z tohoto důvodu je relativní četnost považována za aproximaci pravděpodobnosti P (a i1 a i2 …a im ) výskytu daného m-gramu na náhodně vybraném místě v textu (tento přístup je převzat ve statistické definici pravděpodobnosti).
V obecném případě lze četnost písmen v procentech určit takto: spočítá se, kolikrát se vyskytuje v šifrovém textu, pak se výsledné číslo vydělí celkovým počtem znaků v šifrovém textu; pro procento se výsledek vynásobí 100.
Frekvence však zásadně závisí nejen na délce textu, ale také na jeho povaze. Například v technickém textu se běžně vzácné písmeno F může objevovat mnohem častěji. Pro spolehlivé určení průměrné frekvence písmen je proto žádoucí mít soubor různých textů.