Analiza de frecvență, criptoanaliza de frecvență - una dintre metodele criptoanalizei , bazată pe presupunerea existenței unei distribuții statistice netriviale a caracterelor individuale și a secvențelor acestora, atât în text simplu, cât și în text cifrat, care, până la înlocuirea caracterelor , vor fi păstrate în procesul de criptare și decriptare .
Simplistic, analiza frecvenței presupune că frecvența de apariție a unei anumite litere a alfabetului în texte suficient de lungi este aceeași pentru diferite texte din aceeași limbă. În același timp, în cazul criptării monoalfabetice , dacă există un caracter în textul cifrat cu o probabilitate similară de apariție, atunci putem presupune că este litera cifrată indicată. Raționament similar se aplică bigramelor (secvențe de două litere), trigramelor etc. în cazul cifrurilor polialfabetice .
Metoda criptoanalizei frecvenței este cunoscută încă din secolul al IX-lea (opera lui Al-Kindi ), deși cel mai faimos caz al aplicării sale în viața reală este, probabil, descifrarea hieroglifelor egiptene de către J.-F. Champollion în 1822. În ficțiune, cele mai cunoscute referințe sunt poveștile „The Gold-Bug ” de Edgar Allan Poe , „The Dancing Men ” de Conan Doyle și romanul „ Copiii căpitanului Grant ” de Jules Verne .
De la mijlocul secolului al XX-lea, majoritatea algoritmilor de criptare utilizați au fost dezvoltați rezistenți la criptoanaliza de frecvență, deci este utilizat în principal în procesul de formare a viitorilor criptografi.
Utilizează faptul că probabilitatea apariției literelor individuale, precum și ordinea lor în cuvinte și fraze dintr-o limbă naturală, este supusă unor modele statistice: de exemplu, o pereche de litere „sya” stând una lângă alta în Rusă este mai probabilă decât „tsy”, iar „ o ” în limba rusă nu apare deloc (dar se găsește adesea, de exemplu, în cecenă ). Analizând un text suficient de lung criptat prin metoda înlocuirii, este posibil să se facă o înlocuire inversă pe baza frecvențelor de apariție a caracterelor și să se restabilească textul original.
După cum am menționat mai sus, caracteristicile importante ale textului sunt repetarea literelor (numărul de litere diferite în fiecare limbă este limitat), perechile de litere, adică m (m-grame), compatibilitatea literelor între ele , alternanța vocalelor și a consoanelor și alte câteva caracteristici. Este de remarcat faptul că aceste caracteristici sunt destul de stabile.
Ideea este de a număra numărul de apariții ale fiecărui nm m -grame posibile în texte clare suficient de lungi T=t 1 t 2 …t l , compuse din litere ale alfabetului {a 1 , a 2 , …, a n } . În același timp, sunt vizualizate m-grame consecutive ale textului:
t 1 t 2 …t m , t 2 t 3 … t m+1 , …, t i-m+1 t l-m+2 …t l .
Dacă L (a i1 a i2 … a im ) este numărul de apariții ale m-gramei a i1 a i2 … a im în textul T și L este numărul total de m-grame numărate, atunci pentru L suficient de mare frecvențele L (a i1 a i2 … a im )/ L , pentru un m-gram dat diferă puțin între ele.
Din acest motiv, frecvența relativă este considerată o aproximare a probabilității P (a i1 a i2 …a im ) a apariției unui m-gram dat într-un loc aleatoriu din text (această abordare este adoptată în definiția statistică ). de probabilitate).
În cazul general, frecvența literelor în termeni procentuali poate fi determinată astfel: se numără de câte ori apare în textul cifrat, apoi numărul rezultat este împărțit la numărul total de caractere din textul cifrat; pentru un procent, rezultatul este înmulțit cu 100.
Frecvența depinde în esență, însă, nu numai de lungimea textului, ci și de natura acestuia. De exemplu, în textul tehnic, litera F, în mod normal rară, poate apărea mult mai frecvent. Prin urmare, pentru a determina în mod fiabil frecvența medie a literelor, este de dorit să aveți un set de texte diferite.