Frekvensanalys , frekvenskryptanalys - en av metoderna för kryptoanalys , baserad på antagandet om förekomsten av en icke-trivial statistisk fördelning av enskilda tecken och deras sekvenser, både i vanlig text och i chiffertext, som, upp till byte av tecken , kommer att bevaras under kryptering och dekryptering .
Förenklat antar frekvensanalys att frekvensen av förekomsten av en given bokstav i alfabetet i tillräckligt långa texter är densamma för olika texter på samma språk. Samtidigt, när det gäller monoalfabetisk kryptering , om det finns ett tecken i chiffertexten med en liknande sannolikhet för förekomst, kan vi anta att det är den angivna chiffrerade bokstaven. Liknande resonemang gäller för bigram (tvåbokstavssekvenser), trigram, etc. när det gäller polyalfabetiska chiffer .
Metoden för frekvenskryptanalys har varit känd sedan 900-talet ( Al-Kindis arbete ), även om det mest kända fallet av dess tillämpning i verkliga livet kanske är dechiffreringen av egyptiska hieroglyfer av J.-F. Champollion 1822. Inom skönlitteratur är de mest kända referenserna berättelserna "The Gold-Bug " av Edgar Allan Poe , "The Dancing Men " av Conan Doyle och romanen " Captain Grant's Children " av Jules Verne .
Sedan mitten av 1900-talet har de flesta av de använda krypteringsalgoritmerna utvecklats resistenta mot frekvenskryptanalys, så det används främst i processen att utbilda framtida kryptografer.
Den använder det faktum att sannolikheten för utseendet av enskilda bokstäver, såväl som deras ordning i ord och fraser i ett naturligt språk, är föremål för statistiska mönster: till exempel ett par bokstäver "sya" som står bredvid varandra i Ryska är mer sannolikt än "tsy", och " o " på ryska språket förekommer inte alls (men det finns ofta, till exempel i tjetjenska ). Genom att analysera en tillräckligt lång text krypterad med ersättningsmetoden är det möjligt att göra en omvänd ersättning baserat på frekvensen av förekomst av tecken och återställa den ursprungliga texten.
Som nämnts ovan är de viktiga egenskaperna hos texten upprepning av bokstäver (antalet olika bokstäver på varje språk är begränsat), bokstäverparen, det vill säga m (m-gram), bokstävernas kompatibilitet med varandra , växlingen av vokaler och konsonanter, och några andra funktioner. Det är anmärkningsvärt att dessa egenskaper är ganska stabila.
Tanken är att räkna antalet förekomster av varje n m möjliga m-gram i tillräckligt långa klartexter T=t 1 t 2 …t l , sammansatt av bokstäverna i alfabetet {a 1 , a 2 , …, an } . Samtidigt visas på varandra följande m-gram av texten:
t t 2 …t m , t 2 t 3 … t m +1 , …, t i-m+1 t l -m+2 … tl .
Om L (a i1 a i2 … a im ) är antalet förekomster av m-grammet a i1 a i2 … a im i texten T , och L är det totala antalet räknade m-gram, då för tillräckligt stort L frekvenserna L (a i1 a i2 … a im )/ L , för ett givet m-gram skiljer sig lite från varandra.
På grund av detta anses den relativa frekvensen vara en approximation av sannolikheten P (a i1 a i2 ...a im ) för att ett givet m-gram ska uppträda på en slumpmässigt vald plats i texten (detta tillvägagångssätt används i den statistiska definitionen sannolikhet).
I det allmänna fallet kan frekvensen av bokstäver i procent bestämmas enligt följande: det räknas hur många gånger det förekommer i chiffertexten, sedan divideras det resulterande talet med det totala antalet tecken i chiffertexten; för en procentsats multipliceras resultatet med 100.
Frekvensen beror dock i huvudsak inte bara på textens längd utan också på dess karaktär. Till exempel, i teknisk text kan den normalt sällsynta bokstaven F förekomma mycket oftare. Därför, för att på ett tillförlitligt sätt bestämma den genomsnittliga frekvensen av bokstäver, är det önskvärt att ha en uppsättning olika texter.