CS Challenge 8, Code Breaking

Kryptering af beskeder har været studeret i tusinder af år. Moderne teknikker baserer sig på vanskelig matematik, men der er også en lang tradition for at benytte substitution af bogstaver.

I denne Challenge ser vi på en variant af Vigenere systemet, og opgaven går ud på at benytte svagheder til at bryde dets koder. Systemet er implementeret som et samlet tool i Crypto.java.

For enkelthedens skyld benytter vi et simplificeret alfabet, der består af af de små bogstaver a-z, cifrene 0-9 og tegnet '_' (underscore), der repræsenterer alle sekvenser af mellemrum og specialtegn. Der er således 37 tegn i alfabetet.

Inden en tekst kan krypteres, skal den først normaliseres til dette format. Antag, at filen fox indeholder teksten:

The quick brown fox: jumps over 189 lazy dogs!
Så vil kommandoen:
java Crypto normalize fox > fox.n
give resultatet:
the_quick_brown_fox_jumps_over_189_lazy_dogs_
på filen fox.n.

Krypteringen foretages med udgangspunkt i et password af vilkårlig længde, sammensat af tegn fra vores alfabet, fx jumpy. En klartekst, som den ovenstående, krypteres ved at den opdeles i blokke af samme længde som passwordet (5 for dette eksempel). Det i'te tegn i en blok roteres cyklisk i alfabetet lige så mangle pladser som nummeret på det i'te tegn i passwordet i alfabetet (startende fra 1 for a). Dette kan foretages af vores tool med denne kommando:

java Crypto encode fox.n jumpy > fox.x
der skriver cifferteksten:
32rpe43p0ylb1bbj01cytez5gj98ufjlkoyvvbdyn9t8y
i filen fox.x. Omvendt kan cifferteksten dekrypteres igen med kommandoen:
java Crypto decode fox.x jumpy 
the_quick_brown_fox_jumps_over_189_lazy_dogs_
Som et større eksempel kan vi kryptere en artikel fra Wikipedia om elefanter:
java Crypto encode elephant.n xyz123 > elephant.x
Hvis passwordet har længde 1, så er teknikken kendt som Caesar kryptering, der (som navnet antyder) har været kendt i 2000 år. Hvis passwordet er mindst lige så langt som klarteksten, så er det en one-time pad, der er den eneste form for garanteret ubrydelig kryptering (hvorfor?). I mellem disse to yderpunkter er det ikke umiddelbart oplagt at koden kan brydes, specielt hvis længden af passwordet er ukendt.

Alle sprog har en karateristisk fordeling af frekvenserne af tegnene i alfabetet i almindelige tekster. I denne Challenge ser vi specielt på engelske Wikipedia artikler om dyr. Da alle teksterne yderligere normaliseres, kalder vi denne variant af engelsk for Normalized Wikipedia Animals (NWA). På baggrund af 1.5MB data er frekvensfordelingen af NWA beregnet ti:

_ e a t i n o s r h l d c u m f g p b w y v k 0 x z 1 2 j q 3 4 5 6 7 8 9
169 99 74 68 59 58 58 58 53 38 37 31 26 22 21 17 17 17 13 12 12 8 5 2 1 1 1 1 0 0 0 0 0 0 0 0 0

Frekvenserne er angivet i promille. Toolet kan beregne frekvensfordelinger med kommandoen:

java Crypto frequency zwahili.n > zwa
der beregner resultatet for en tekst i zwahili. Resultatet for NWA ligger tilsvarende i filen nwa, og de to kan ses at være ret forskellige. Man kan observere, at en frekvensfordeling hurtigt bliver stabil og med vores alfabet faktisk kan laves på baggrund af kun ca. 500 tegn. Disse observationer har allerede afsløret en fatal svaghed ved vores krypteringssystem.

Spørgsmål A

Udfyld kroppen af 2-parameter metoden guess i Crypto.java, så den automatisk kan gætte et password af en givet længde for en krypteret NWA tekst. Fx skal følgende fungere:
java Crypto guess elephant.x 6
xyz123
Start med at studere virkemåden af klasserne Counter og Frequency. Giv en meget kort forklaring på din løsning. Hint: overvej først, hvordan problemet kunne løses, hvis passwordet har længde 1.

Bonus

Hver deltager modtager en fil af formen animalXY.x, der indeholder en krypteret Wikipedia artikel om et hemmeligt dyr, hvor passwordet har længde 8. Hvis man fredag den 23. september i Datalogisk Fredagsbar annoncerer sit navn og navnet på sit hemmelige dyr, så vil man modtage en gratis øl (eller sodavand).
Frekvensfordelinger siger en del om de forskellige sprog, hvilket vi kan udnytte til at gøre guess endnu smartere.

Hvis vi betragter de 37 tal i en frekvensfordeling som en 37-dimensionel vektor, så kan vi definere afstanden mellem to fordelinger som den Euklidiske afstand mellem de to vektorer (i et 37-dimensionelt reelt vektorrum).

Observationen er nu, at sprog, der minder meget om hinanden, har en lille afstand. Afstande mellem fordelinger kan beregnes af vores tool med kommandoen:

java Crypto distance nwa zwa
0.16374675569305186
Følgende tabel viser de gensidige afstande mellem nwa, zwa, gtb (The Gettysburg Address), eln (elephant.n og elx (elephant.x):

  nwa zwa gtb ele elx
nwa0.000.160.060.010.26
zwa0.160.000.190.160.27
gtb0.060.190.000.060.29
eln0.010.160.060.000.26
elx0.260.270.290.260.00

Tabellen er naturligvis symmetrisk med 0'er langs diagonalen (hvorfor?). Brug noget tid på at tænke over tallene i tabellen og deres betydning.


Spørgsmål B

Udfyld kroppen af 1-parameter metoden guess i Crypto.java, så den automatisk kan gætte et password uden at kende længden for en krypteret NWA tekst. Fx skal følgende fungere:
java Crypto guess elephant.x
xyz123
Giv en meget kort forklaring på din løsning.

Strategien er klart at prøve forskellige længder, men det efterlader to spørgsmål: Hvor lange passwords giver mening? Hint: hvis passwordet bliver for langt, er der ikke nok tegn tilbage på hver position til at lave en god frekvensfordeling. Hvordan ved man automatisk, at man har fundet klarteksten? Hint: man skal nok bruge distance metoden.

Man kan afprøve sin løsning ved at finde det ultrahemmelige dyr, der er beskrevet i secret.x.


BlueJ version: CryptoBlueJ.zip.


Du deltager i vores Challenge ved senest den 25. september at sende en e-mail til mis@cs.au.dk med subject Challenge 8 og svarene på spørgsmål A og B (i plain text) og koden til spørgsmål A og B i form af et attachment med en ny udgave af programmet Crypto.java.