Frekvensanalyse , frekvenskryptanalyse - en af metoderne til kryptoanalyse , baseret på antagelsen om eksistensen af en ikke-triviel statistisk fordeling af individuelle tegn og deres sekvenser, både i almindelig tekst og i chiffertekst, som op til udskiftning af tegn , vil blive bevaret i processen med kryptering og dekryptering.
Forenklet antager frekvensanalyse, at hyppigheden af forekomst af et givet bogstav i alfabetet i tilstrækkeligt lange tekster er den samme for forskellige tekster af samme sprog. På samme tid, i tilfælde af monoalfabetisk kryptering , hvis der er et tegn i chifferteksten med en lignende sandsynlighed for forekomst, så kan vi antage, at det er det angivne krypterede bogstav. Lignende ræsonnement gælder for bigrammer (tobogstavssekvenser), trigrammer osv. i tilfælde af polyalfabetiske cifre .
Metoden til frekvenskryptanalyse har været kendt siden det 9. århundrede (værket af Al-Kindi ), selvom det mest berømte tilfælde af dens anvendelse i det virkelige liv måske er dechifreringen af egyptiske hieroglyffer af J.-F. Champollion i 1822. I fiktion er de mest berømte referencer historierne "The Gold-Bug " af Edgar Allan Poe , "The Dancing Men " af Conan Doyle og romanen " Captain Grant's Children " af Jules Verne .
Siden midten af det 20. århundrede er de fleste af de anvendte krypteringsalgoritmer blevet udviklet resistente over for frekvenskryptanalyse, så det bruges hovedsageligt i processen med at træne fremtidige kryptografer.
Den bruger det faktum, at sandsynligheden for udseendet af individuelle bogstaver, såvel som deres rækkefølge i ord og sætninger i et naturligt sprog, er underlagt statistiske mønstre: for eksempel et par bogstaver "sya", der står ved siden af hinanden i Russisk er mere sandsynligt end "tsy", og " o " på russisk sprog forekommer slet ikke (men det findes ofte, for eksempel i tjetjensk ). Ved at analysere en tilstrækkelig lang tekst, der er krypteret med erstatningsmetoden, er det muligt at foretage en omvendt erstatning baseret på hyppigheden af forekomst af tegn og gendanne den originale tekst.
Som nævnt ovenfor er tekstens vigtige egenskaber gentagelsen af bogstaver (antallet af forskellige bogstaver på hvert sprog er begrænset), bogstavparrene, det vil sige m (m-gram), bogstavernes kompatibilitet med hinanden , vekslen mellem vokaler og konsonanter og nogle andre funktioner. Det er bemærkelsesværdigt, at disse egenskaber er ret stabile.
Ideen er at tælle antallet af forekomster af hvert n m mulige m-gram i tilstrækkelig lange klartekster T=t 1 t 2 …t l , sammensat af bogstaver i alfabetet {a 1 , a 2 , …, an } . Samtidig ses på hinanden følgende m-gram af teksten:
t1t2 …tm , t2t3 … tm +1 , … , t i - m +1 tl - m+ 2 … tl .
Hvis L (a i1 a i2 … a im ) er antallet af forekomster af m-grammet a i1 a i2 … a im i teksten T , og L er det samlede antal talte m-gram, så for tilstrækkeligt store L frekvenserne L (a i1 a i2 … a im )/ L , for et givet m-gram afviger lidt fra hinanden.
På grund af dette betragtes den relative frekvens som en tilnærmelse af sandsynligheden P (a i1 a i2 …a im ) for udseendet af et givet m-gram på et tilfældigt udvalgt sted i teksten (denne tilgang er overtaget i den statistiske definition sandsynlighed).
I det generelle tilfælde kan frekvensen af bogstaver i procenter bestemmes som følger: det tælles, hvor mange gange det forekommer i chifferteksten, derefter divideres det resulterende tal med det samlede antal tegn i chifferteksten; for en procentdel ganges resultatet med 100.
Hyppigheden afhænger dog i det væsentlige ikke kun af tekstens længde, men også af dens natur. For eksempel i teknisk tekst kan det normalt sjældne bogstav F forekomme meget hyppigere. Derfor, for pålideligt at bestemme den gennemsnitlige frekvens af bogstaver, er det ønskeligt at have et sæt forskellige tekster.