Frekvensanalyse (kryptografi)

En typisk fordeling av forekomsten av bokstavene i det engelske alfabetet. Svake chiffer vil ikke i tilstrekkelig grad maskere denne fordelingen og kan brukes for en analyse

Frekvensanalyse innen kryptografi er en teknikk som brukes for å finne mønster i kryptert informasjon. Det vil si at man undersøker om det er enkelte kombinasjoner eller tegn som gjentas oftere enn andre.

Frekvensanalyse brukes i hovedsak mot substitusjonschiffer, det vil si tekst hvor man har byttet ut en bokstav med en annen. Metoden baserer seg på at det innenfor et språk er en ujevn fordeling mellom de forskjellige bokstavene, slik at noen bokstaver opptrer svært hyppig, mens andre opptrer sjeldnere. I norsk og engelsk er e den vanligste bokstaven. Det gjør at man kan anta at det tegnet som gjentas oftest, representerer e.

Dette kan benyttes til å gjette seg frem til hvilke bokstaver som forekommer i teksten. Tekster som er kortere enn ca. 30 tegn gir dårlig grunnlag for frekvensanalyse. Jo lengre teksten er, jo større sikkerhet vil en få i resultatene.

Fordeling av bokstaver i norsk

I det norske språk er fordelingen omtrent slik :

Bokstav	Frekvens
a	6,07 %
b	1,47 %
c	0,34 %
d	4,21 %
e	15,38 %
f	2,02 %
g	3,90 %
h	1,64 %
i	6,16 %
j	1,02 %
k	3,83 %
l	5,26 %
m	3,40 %
n	7,81 %
o	5,03 %
p	2,06 %
q	0,02 %
r	8,53 %
s	6,36 %
t	7,84 %
u	1,80 %
v	2,40 %
w	0,15 %
x	0,05 %
y	0,74 %
z	0,04 %
æ	0,20 %
ø	0,76 %
å	1,50 %

En angriper vil derfor forsøke å finne hvilke bokstaver som forekommer mest.

Eksempel

For eksempel kan man la følgende bokstaver bytte plass: h og x, e og w, p og u, r og q samt i og z. Da vil setningen «hei Per» bli til «xwz, uwq», en tilsynelatende sterk kryptering med mange mulige kombinasjoner. Men ved hjelp av frekvensanalyse kan man arbeide seg fram til løsningen.

I eksemplet «xwz uwq» kan vi se at bokstaven w forekommer to ganger, siden e er den vanligste bokstaven i norsk (ca. 11,5 %), så kan vi gjette på at w er e. Vi har nå «xEz uEq» (E er kandidat til riktig bokstav). Videre kan vi gjette på at «q» er en mye brukt bokstav slik som r, t eller s. Ved å sette inn r i stedet for q, har vi nå «xEz uER» Siden vi vet at meldingen kanskje skal til en person som heter Per, så gjetter vi på at det siste ordet er Per. Siden xEz er først i setningen, gjetter vi på at ordet er Hei. Vi har nå funnet 5 bokstaver og fortsetter med å gjette og bytte ut bokstaver i resten av setningen. Som man ser av dette, er kjennskap til språket, og andre opplysninger man måtte ha, en viktig del av frekvensanalysen.

Ved analyse av en lengre tekst vil man også ofte benytte en utvidet form for frekvensanalyse, der man ser på sammenstillinger av bokstaver. I mange språk er det kombinasjoner av to bokstaver som forekommer spesielt hyppig, og gjerne på spesielle steder i ordet. På engelsk har man for eksempel hyppig th- i begynnelsen av ord, på grunn av den bestemte artikkelen the og en rekke andre, vanlige ord. På norsk vil man ofte se på endelser, som -en(e), -er og -e.

Frekvensanalyse er lettest dersom den krypterte teksten har beholdt mellomrommene i klarteksten; dersom man skriver alt som en sammenhengende streng eller legger mellomrom på galt sted vil analysen være noe mer tidkrevende fordi man ikke så lett kan gjette seg frem til ord. Dette gjelder ikke minst artikler, som hyppig vil forekomme som likelydende sammenstillinger foran lengre ord. Dersom mellomrommene er bevart kan man oftest enkelt identifisere to-tre vanlige bokstaver i artikkelen, og man får samtidig vite at neste ord er et substantiv.

For å gjøre det noe vanskeligere å benytte frekvensanalyse er det mulig å legge inn ett eller flere blindtegn, tegn som ikke står for noen bestemt bokstav. Dette er svært lett dersom man bruker andre symboler enn alfabetet, men også når man bruker alfabetet kan man bruke sjeldne bokstaver på denne måten. På norsk kan det for eksempel være naturlig å bruke q og x som blindtegn; disse svært sjeldne bokstavene vil da opptre hyppig i teksten, noe som forstyrrer frekvensanalysen.

Bruk

Maria Stuart fikk smertelig erfare svakhetene ved et monoalfabetisk substitusjonschiffer. Hun ville styrte den engelske dronningen Elizabeth. Meldingene mellom Mary og hennes tilhengere ble oppdaget. Ved hjelp av frekvensanalyse lyktes det Thomas Phelippes å dechifrere meldingene og konspirasjonen ble oppdaget. I 1587 ble hun og hennes tilhengere, torturert og halshugd.

Se også

• Kryptoanalyse