Er en udtømmende nøglesøgning effektiv mod substitutionschiffere?

by Theresa Sittel / Lørdag, 17 May 2025 / Udgivet i Cybersecurity, Grundlæggende om EITC/IS/CCF klassisk kryptografi, Kryptografiens historie, Modulære aritmetiske og historiske koder

En udtømmende nøglesøgning, også kendt som et brute-force-angreb, involverer systematisk at afprøve alle mulige nøgler i en krypterings nøglerum, indtil den korrekte nøgle findes. Effektiviteten af en sådan tilgang afhænger i høj grad af størrelsen af nøglerummet, som bestemmes af antallet af mulige nøgler, og strukturen af den kryptering, der angribes.

Substitutionschifre er en klasse af klassiske kryptografiske algoritmer, hvor hvert element i klarteksten (oftest et bogstav) systematisk erstattes med et andet fast element i chifferteksten. De mest kendte typer er simple substitutionschifre (hvor hvert bogstav i alfabetet er knyttet til et andet bogstav) og monoalfabetiske substitutionschifre, samt mere komplekse polyalfabetiske substitutionschifre, såsom Vigenère-chifferen.

For at evaluere effektiviteten af en udtømmende nøglesøgning mod substitutionschiffere er det nødvendigt at analysere både de teoretiske og praktiske aspekter, herunder størrelsen af nøglerummet, nøglernes art og den producerede chifferteksts egenskaber.

Nøglerummet for substitutionscifre

En simpel substitutionschiffer, der bruger det engelske alfabet med 26 bogstaver, har en nøgleafstandsstørrelse lig med antallet af mulige permutationer af alfabetet. Matematisk set er dette 26 faktorielt (26!), hvilket svarer til 403,291,461,126,605,635,584,000 eller omtrent 4 x 10^26 mulige nøgler. Til sammenligning har Cæsar-chifferen, en specifik type substitutionschiffer, et meget mindre nøgleafstand på kun 25 nøgler (da hvert bogstav kan forskydes med en hvilken som helst værdi mellem 1 og 25).

Et centralt aspekt ved substitutionschiffere er, at nøglen ikke er en tilfældig bitstreng, men en permutation af alfabetet, hvilket påvirker, hvordan nøgler genereres og testes i en udtømmende søgning.

Udtømmende nøglesøgning på simple substitutionscifre

Princippet om en udtømmende nøglesøgning dikterer, at angriberen for hver mulig nøgle dekrypterer krypteringsteksten og kontrollerer, om den resulterende klartekst er meningsfuld. For substitutionschifre, især dem med store nøglerum såsom monoalfabetisk substitution, udgør dette teoretisk set et beregningsmæssigt vanskeligt problem, da der er et svimlende antal mulige permutationer at teste.

Den praktiske effektivitet af udtømmende søgning på substitutionscifre er dog begrænset af flere faktorer:

1. Nøglebekræftelse

I modsætning til moderne chiffere, hvor en nøgle enten producerer den korrekte klartekst eller ej, skal angriberen med substitutionschiffere afgøre, om outputtet er gyldigt engelsk (eller det forventede klartekstsprog). Der er ingen indikator eller kontrolsum i klassiske chiffere, så angriberen skal manuelt eller automatisk verificere outputtet. I betragtning af redundansen og forudsigeligheden i naturlige sprog er dette typisk let for mennesker at genkende, men svært at automatisere, især i betragtning af antallet af nøgler.

2. Redundans i sprog

Fordi naturlige sprog som engelsk har betydelig redundans og struktur, kan dekrypterede output, der ikke svarer til læsbar tekst, hurtigt kasseres. Statistisk set er sandsynligheden for tilfældigt at permutere alfabetet og producere meningsfuld tekst imidlertid astronomisk lav, hvilket gør den udtømmende søgning ineffektiv.

3. Gennemførlighed

Selvom nøgleområdet er enormt, kunne moderne computere i teorien forsøge at indtaste millioner eller endda milliarder af taster i sekundet. Ikke desto mindre er nøgleområdet på 26! så stort, at selv med enorme beregningsressourcer ville en udtømmende søgning tage upraktisk tid.

Historiske og praktiske angreb

Trods den teoretiske sikkerhed, som størrelsen af nøglerummet giver, betragtes substitutionschiffere ikke som sikre, selv mod angribere uden ressourcerne til en udtømmende nøglesøgning. Hovedårsagen er, at disse chiffere er sårbare over for analytiske angreb, især frekvensanalyse.

Frekvensanalyse

Hvert bogstav i klarteksten erstattes altid af det samme bogstav i krypteringsteksten, så klartekstens statistiske egenskaber bevares. For eksempel er bogstavet 'E' det mest almindelige i engelsk tekst. Ved at analysere hyppigheden af bogstaver i krypteringsteksten kan en angriber udlede, hvilke krypteringstekstsymboler der svarer til hvilke bogstaver i klartekst.

Denne metode er langt mere effektiv end en udtømmende nøglesøgning. Den kræver kun en moderat mængde krypteret tekst for at være effektiv, og den kan gendanne nøglen eller klarteksten med minimal beregningsindsats sammenlignet med en brute-force-tilgang.

Eksempel

Antag, at en angriber opsnapper en krypteret tekst krypteret ved hjælp af en monoalfabetisk substitutionskryptering. En frekvenstælling udføres, hvilket afslører, at symbolet 'Q' forekommer hyppigst. Hvis angriberen ved, at sproget er engelsk, er det sandsynligt, at 'Q' svarer til 'E'. Ved at gentage denne proces for andre hyppigt forekommende bogstaver (såsom 'T', 'A', 'O') kan angriberen rekonstruere substitutionsnøglen, eller i det mindste en del af den, uden at prøve alle 26 permutationer.

Nøglegendannelse vs. gendannelse af almindelig tekst

Udtømmende nøglesøgning søger at gendanne nøglen, så enhver besked krypteret med den samme nøgle kan dekrypteres. Frekvensanalyse og lignende analytiske angreb giver normalt nok af nøglen til at gendanne klarteksten, selvom hele nøglen ikke gendannes med det samme. I praksis er dette tilstrækkeligt til at bryde krypteringens sikkerhed.

Modulær aritmetik og klassiske cifre

Nogle substitutionschiffere, såsom den affine chiffer og Cæsar-chifferen, bruger modulær aritmetik i deres transformationer.

- Cæsar ChifferHvert bogstav i klartekst forskydes med et fast antal positioner i alfabetet. Matematisk set, for et bogstav i klartekst $x$ , chiffertekst beregnes som $(x + k) \mod 26$ Hvor $k$ er shift (nøglen).
- Affine CipherHvert bogstav er krypteret som $(ax + b) \mod 26$ Hvor $a$ og $b$ er nøgler, og $a$ og 26 skal være koprime.

For disse chiffere er nøglerummet meget mindre (25 for Cæsar, 312 for affine), hvilket gør en udtømmende nøglesøgning ikke kun mulig, men også triviel. For eksempel kan en angriber forsøge alle 25 mulige Cæsar-skift på få sekunder. Derfor er brute-force-angreb yderst effektive mod disse chiffere.

Polyalfabetiske substitutionscifre

Mere komplekse chiffere, som f.eks. Vigenère-chifferen, bruger en gentagende nøgle til at ændre substitutionen for hvert bogstav, hvilket gør frekvensanalyse mindre effektiv. Nøglerummet bestemmes dog af nøglens længde og mulige værdier.

Hvis nøglen er lang $n$ , og hvert tegn kan være et hvilket som helst bogstav (26 muligheder), er tasteafstanden $26 ^ n$ For korte nøgler er dette stadig modtageligt for udtømmende søgning. For eksempel giver en nøgle på 5 bogstaver 11,881,376 mulige nøgler ( $26 ^ 5$ ), hvilket er inden for rækkevidde af moderne computere. En længere nøgle øger dog nøgleområdet eksponentielt, men praktisk brug af Vigenère-chiffer involverede ofte korte nøgler, hvilket gjorde dem sårbare over for brute-force og analytiske angreb.

I tilfælde af Vigenère-chifferen kan chifferen, hvis nøglelængden er kendt, opdeles i en ækvivalent af flere Cæsar-chiffere, som hver især kan angribes separat. Metoder som Kasiski-undersøgelsen og Friedman-testen kan hjælpe med at bestemme nøglelængden, hvorefter frekvensanalyse anvendes på hver delmængde.

Praktisk sikkerhedsvurdering

Den praktiske usikkerhed ved substitutionschiffere skyldes ikke alene deres nøglerumsstørrelse, men snarere de strukturelle svagheder, der tillader analytiske angreb. Udtømmende nøglesøgning er teoretisk effektiv, da den garanterer, at nøglen til sidst vil blive fundet, men i praksis er det ikke den foretrukne angrebsmetode på grund af ineffektivitet og tilgængeligheden af mere effektive teknikker.

For klassiske chiffere med små nøglerum (som Cæsar- og affine chiffere) er udtømmende nøglesøgning trivielt effektiv. For monoalfabetiske substitutionschiffere er nøglerummet stort nok til at forhindre udtømmende søgning med selv de mest kraftfulde moderne computere, men disse chiffere er stadig usikre på grund af frekvensanalyse.

Didaktisk værdi

At studere (in)effektiviteten af udtømmende nøglesøgning mod substitutionschiffere giver værdifulde lektioner i kryptografi:

- Tastepladsens størrelse betyder noget, men er ikke altEt stort nøgleområde kan gøre brute-force-angreb umulige, men garanterer ikke sikkerhed, hvis krypteringen lækker strukturel information om klarteksten.
- Betydningen af statistiske egenskaberKlassiske chiffere fejler ofte, fordi de bevarer de statistiske egenskaber ved klarteksten, hvilket muliggør analytiske angreb.
- Modular aritmetiks rolleEn forståelse af, hvordan aritmetiske operationer definerer transformationerne i chifre som Cæsar- og affine chifre, hjælper med at belyse, hvorfor deres nøglerum er så små, og hvorfor de så lette at udføre med brute-force.
- Udviklingen af kryptanalyseDen historiske udvikling fra brute-force til analytiske angreb demonstrerer feltets fremskridt og behovet for chiffere, der ikke lækker information om klartekst eller nøglen.

Eksempel på beregning

Antag, at en angriber ønsker at brute-force en monoalfabetisk substitutionschiffer. Hvis en supercomputer kunne prøve 1 milliard (10^9) nøgler i sekundet, ville det tage:

$[\frac{4 \times 10^{26}}{10^9 \text{ taster/sek}} = 4 \times 10^{17} \text{ sekunder} \]$

$[ = \frac{4 \times 10^{17}}{60 \times 60 \times 24 \times 365} \approx 1.27 \times 10^{10} \text{ år} \]$

Dette er størrelsesordener længere end universets alder, hvilket gør brute-force-angreb praktisk talt umulige.

Moderne perspektiv

Inden for moderne kryptografi er erfaringerne fra substitutionschiffere klare. Nøglestørrelse alene er ikke et tilstrækkeligt sikkerhedsmål; chifferens struktur og dens modstandsdygtighed over for analytiske og statistiske angreb er lige så, hvis ikke vigtigere. Moderne chiffere, såsom AES, er designet til at modstå både udtømmende nøglesøgning (ved at bruge astronomisk store nøglerum) og alle kendte analytiske angreb.

Klassiske chiffere, herunder substitutionschiffere, er således værdifulde undervisningsværktøjer til at forstå samspillet mellem nøglerum, chifferstruktur og metoderne til kryptanalyse.

Andre seneste spørgsmål og svar vedr Grundlæggende om EITC/IS/CCF klassisk kryptografi:

Se flere spørgsmål og svar i EITC/IS/CCF Classical Cryptography Fundamentals

Flere spørgsmål og svar:

Mark: Cybersecurity
program: Grundlæggende om EITC/IS/CCF klassisk kryptografi (gå til certificeringsprogrammet)
Lektie: Kryptografiens historie (gå til relateret lektion)
Emne: Modulære aritmetiske og historiske koder (gå til relateret emne)

Tagged under: Brute-force angreb, Klassisk kryptering, kryptoanalyse, Cybersecurity, Frekvensanalyse, Erstatningscifre

EITCA Academy