SRP: Kryptologi, Enigma maskinen og RSA-kryptering

Kryptologi, Enigma maskinen og RSA-kryptering

Abstract

This paper examines a few widely used methods of cryptology and takes a look at the German Enigma-machine’s influence on how the 2. World War evolved, especially concerning the Battle of the Atlantic. Throughout time, humans have had the need to communicate secretly. The most practical way of doing this is through cryptology. Due to this, there is an extremely large number of different algorithms to ensure the secureness of transferring information. Not until recently, there has been a method that is practically unbreakable, while also working in the real world. The method is called RSA-encryption, and is widely used all over the world by banks, websites, and basically anyone who wants to transfer information easily and securely. RSA-encryption is based on prime numbers and their unique properties, but the overall principle is the same as any other cryptological method. During the Second World War the Germans used a machine for encrypting and decrypting their messages. This machine was called Enigma, and played an important part in the war. In this paper there is a detailed description of how the Enigma worked and what the influence on the war was, when the Allies broke its code.

Indledning

Kryptologi er en tovejs proces, der består af kryptering og dekryptering. Kryptering bruger man til at gøre meddelelser ulæselige for andre end den rette modtager. Det kan gøres ved hjælp af forskellige krypteringsmetoder. Et fællestræk for de fleste metoder er dog, at de benytter sig af nøgler, dvs. et tal eller lignende, som skal bruges til at dekryptere med, altså vende tilbage til den oprindelige tekst. Under 2. Verdenskrig spillede kryptologi en stor rolle i form af den tyske kodemaskine Enigma, der især havde indflydelse på Slaget om Atlanten.

Kryptologi

Kryptering er en proces, der benyttes til at gøre meddelelser ulæselige for andre end den rette modtager. Der findes et utal er forskellige metoder, der alle har forskellige fordele og ulemper. Som teknologien forbedres og computernes hastigheder forøges, kræves der konstant forbedrede krypteringsmetoder med større tal og flere muligheder, for at undgå såkaldte ’Brute-force attacks’, der går ud på at prøve alle mulige kombinationer. De fleste metoder benytter sig af en nøgle, som både modtager og afsender skal være enige om på forhånd. Et godt eksempel på dette er i Cæsarkryptering. Som navnet angiver, er det angiveligt blevet opfundet af Julius Cæsar. Idéen er, at man i krypteringsprocessen flytter hvert bogstav i den hemmelige meddelelse x antal trin til højre i alfabetet. Hvis man er blevet enige om, at x=1, så vil beskeden ”hej” blive til ”ifk”. I dette tilfælde er nøglen lig med 1. Samme nøgle bruges for at genskabe den originale besked, her flyttes hvert bogstav x plads(er) til venstre i alfabetet.

Positionskryptering

Cæsarkrypteringen er en afart af positionskryptering, også kendte som monoalfabetisk substitutions cifferalgoritme. I de mest forekomne typer af positionskryptering er nøglen at flytte x antal pladser til enten højre eller venstre i alfabetet, ligesom i Cæsars metode. En anden variant er nøglen ikke blot et tal og en retning, men i stedet en hel liste der forbinder hvert bogstav i det rigtige alfabet med et andet. Det kunne fx være at A = G og B = C, på den måde er der altså ikke et fast mønster, hvormed man skal flytte rundt i alfabetet. I stedet skal man kende de to parrede alfabeter; nøglen.

Følgende kodeeksempel er skrevet i det generelle programmeringssprog Python 2.x og viser Cæsarkrypteringen i funktion. I Python benyttes indrykning til at afgrænse og afslutte elementer.

1. # Cæsarkryptering i Python 2.7
2. # Af: 
4. alphabet =[“a”,”b”,”c”,”d”,”e”,”f”,”g”,”h”,”i”,”j”,”k”,”l”,”m”,”n”,”o”,”p”,”q”,”r”,”s”,”t”,”u”,”v”,”x”,”y”,”z”,”æ”,”ø”,”å”]
6. defcrypt(text, direction): # funktionen crypt defineres. Der skal gives to argumenter.
7.   crypted = “” # En tom string laves, for at kunne indeholde den krypterede eller dekrypterede tekst.
9.   if direction == “encrypt”:
10.       key =3
11.   else:                       # Hvis argumentet encrypt er givet, bruges 3, ellers bruges -3 til at dekryptere. Dette er nøglen.
12.       key =-3
13.   forletter in text: # for-loop til at gennemse hver bogstav i teksten.
14.       forposition, item in enumerate(alphabet): # Kører alle bogstaverne i alfabetet igennem.
15.           ifitem ==lower(): # hvis item(bogstav fra alfabet) er lig bogstav fra tekst.
16.                   crypted +=alphabet[position+key] # tilføjes det passende bogstav, ud fra nøglen
17.       ifletter == ” “:
18.           crypted +=letter # bruges til at tilføje mellemrum.
19.   returncrypted # Returnerer den endelige tekst til videre brug.
21. text =”caesar”
22. text_encrypted =crypt(text,”encrypt”) # Her bruges funktionen ud fra den definerede tekst: “caesar”
23. text_decrypted =crypt(text_encrypted,”decrypt”) # text_encrypted køres igennem funktionen med ”decrypt” som direction.
24. print“Start tekst: %s”% text # %s er en pladsholder for en string, som skrives bagefter.
25. print“Krypteret tekst: %s”% text_encrypted
26. print“Dekrypteret tekst: %s”% text_decrypted
29. # Test 1
30. ”’
31. Start tekst: caesar
32. Krypteret tekst: fdhvdu
33. Dekrypteret tekst: caesar
34. ”’
35. # Test 2
36. ”’
37. Start tekst: verdenskrig
38. Krypteret tekst: zhughqvnulj
39. Dekrypteret tekst: verdenskrig
40. ”’

Det er klart for enhver, at Cæsars krypteringsmetode ikke er særlig sikker i dag. Det var noget andet, da den blev brugt, for der var størstedelen af folk analfabeter og ikke særlig veluddannede. Umiddelbart virker den anden positionskryptering med tilfældige bogstaver mere sikker, men den kan dog stadig brydes af en uvedkommende rimelig let, idet visse bogstaver optræder oftere end andre. (Wikipedia) På dansk bruges ’e’ for eksempel meget oftere end ’k’, hvis det vel og mærke er en gennemsnitlig tekst. Ud fra dette kan man lave en statistisk analyse af den krypterede tekst. På samme måde kan man lave bigrammer og trigrammer, dvs. analyser af frekvensen af henholdsvis to eller tre bogstaver i træk. Et godt bud på et bigram kunne være ud fra bogstaverne ’hv’, der ofte optræder i det danske sprog. Ligeledes kan man se efter ord med dobbelte bogstaver. (Vestergaard)

Enigma-kryptering

Enigma-kryptering er, i modsætning til Cæsar-kryptering, baseret ud fra et polyalfabetisk substitutions ciffer. Når flere alfabeter bruges, bliver brydning vha. statistik meget sværere, fordi frekvensen af de forskellige bogstaver nogenlunde bliver spredt ud. Første dokumenterede brug af det polyalfabetiske substitutions ciffer kan føres tilbage til Leon Battista Alberti omkring år 1467. (Wikipedia) Skal krypteringen være fuldkommen sikker, så skal der bruges et nyt alfabet for hvert eneste bogstav i teksten. Dog er det meget upraktisk, idet indstillingerne for hvert alfabet skulle nedskrives i kodebøger, og det ville tage meget lang tid. Som teknologien forbedres, blev der lavet flere og bedre mekaniske og elektro-mekaniske krypteringsmaskiner. Enigma-maskinen er elektro-mekanisk og blev designet og patenteret af den tyske elektroingeniør Arthur Scherbius i 1918. Idéen med maskinen var oprindeligt til brug i banksektoren og lignende, men da krigen kom nærmere skulle det tyske militær bruge hans produkt, der stadig blev solgt til kommercielt brug i en forsimplet udgave.

Enigmas virkemåde

På figur 1 ses en af hærens Enigma-maskiner. Længst væk i den sorte kasse som maskineriet er pakket ind i, kan man se tre riller med metal skiver, disse kaldes rotorer. Tættere på er en række bogstaver med lamper under, dette kaldes lampboardet. Når man trykker en tast ned på tastaturet kører det gennem maskinen og det endelige krypterede ciffer lyser op i rækken med lamper. Nederst på billedet ser man et plugboard, der forbinder visse bogstaver med ledninger.

På figur 2 ses et udsnit fra A til H af det indre kredsløb i Enigma-maskinen. De tre rotorer er oppe i toppen og hedder hhv. L, M og N. E bruges blot til at forbinde tastaturet med klartekst i midten af billedet med rotorerne. Når bogstavet A trykkes, flytter hjulet N sig ét hak, for at sikre sig, at der anvendes et nyt alfabet.

1. Derefter løber et signal ned til A i plugboardet. Idet A i plugboardet ikke er forbundet med andet, sendes signalet videre til E (Entry Wheel).
2. Signalet løber derefter i et indviklet ledningsnet gennem de tre rotorer L, M og N og gennem reflektoren, R. Hver gang sker der en permutation af bogstaverne.
3. Signalet løber derefter tilbage gennem rotorerne, og på grund af reflektoren, er det nu de inverse permutationer.
4. Endeligt ryger signalet tilbage i plugboardet til F, der er forbundet til D, og derefter op til lampboardet, hvor D lyser op.

Denne avancererede proces krypterer altså klarteksten ’A’ til cifferteksten ’D’. Næste gang der trykkes på en tast, rykker N endnu en gang, og derfor vil fx ’A’ ikke bliver ’D’ igen. (Vestergaard)

Rotorer og ringindstillinger

Der fandtes en række forskellige skiver, som kunne sættes i hver rotorplads. De var navngivet med romerske tal og hed således I, II, III, IV osv. Skiverne var identiske i form, og kunne derfor passe i alle rotorpladserne. Forskellen på dem var rækkefølgen i alfabetet, der stod i tal. Ringindstillingerne var startværdien for hver skive, som indstilledes manuelt ved at dreje på skiverne, når de sad i maskinen. (Ibid)

Hak

I rotoren N er der et hak(notch) ud for ét bestemt bogstav. Når hakket i N nås, rykker M en plads. M har ligeledes et hak, der er forbundet med L. Enigma har endvidere en funktion, der hedder doublestepping. Funktionen gør, at M flytter sig endnu en plads efter at hakket i N er nået, hvilket gør at hakket med forbindelse til L kommer dobbelt så hurtigt.

På figur 3 ses princippet i doublestepping, og er mere eller mindre selvforklarende. Når Højre rotor, N, rammer sit hak, ændres Midterste rotor, M, i samme step og i næste. Der rammer den sit hak, hvorefter Venstre rotor, L, ændres. (Ibid)

Plugboard

Plugboardet indstilles ved at forbinde et antal bogstaver med ledninger. Der kan altså varieres på både antallet af forbindelser og hvilke bogstaver, som er forbundet. (Ibid)

Reciprok egenskab – dekryptering

Enigma-maskinen er reciprok, og dette er essentielt for dens popularitet. Indtaster man en krypteret meddelelse med de eksakt samme indstillinger, så kommer man tilbage til den oprindelige tekst. Maskinens reciprokke egenskab, gjorde det let for tyskerne at holde kodebøger med fx ugens indstillinger, da kun én nøgle skulle bruges til både kryptering og dekryptering. (Ibid)

Enigma i brug

Enigma-krypteringsmetodens sikkerhed ligger i antallet af mulige indstillinger, som maskinen kan have. Hæren havde fem rotorer samt to reflektorer at skifte imellem. Desuden brugte de plugboardet for yderligere variation. En nøgle til Enigma-maskinen kunne for eksempel være:

Rotor: I, IV, II                                          Ringindstilling: T, S, A    Plugboard: RT, SA, PB, GH, IU

I rotorpladsen L sættes skiven I, i M sættes IV og i N sættes II. L sættes derefter til T som startposition, M til S og N til A. Til sidst forbindes bogstaverne R med T, S med A osv. i plugboardet. Derefter kan en klarteksten eller cifferteksten(krypteret tekst) skrives ind for henholdsvis at kryptere eller dekryptere. (Ibid)

RSA-kryptering

RSA er en krypteringsmetode, der er baseret på primtal, altså tal, hvor kun 1 og tallet selv går op i. Det er en såkaldt public-key-krypteringsmetode, der gør det let for enhver at kryptere meddelelser, mens kun få kan dekryptere dem. Metoden er fra 1977 og er opkaldt efter dens tre opfindere: Ron Rivest, Adi Shamir og Leonard Adleman. Sikkerheden ligger i sværhedsgraden ved at primfaktorisere, hvilket er en utrolig tidskrævende proces, der ikke stiger lineært med forøgelsen af antallet af cifre. For at kunne forstå RSA-kryptering er det nødvendigt at forstå nogle matematiske principper og metoder, derfor forklares de nu. (Riber, RSA-kryptering, 2008)

Primtalsfaktorisering

Primtal kan betragtes som byggesten, idet alle tal kan skrives som et produkt af primtal. Desuden er der kun én måde at opbygge hvert tal på ved hjælp af primtal. Faktorisering er kunsten til at finde hvad et vilkårligt tal er et produkt af. For eksempel er 3*4*5 = 60, men dette er ikke en primtalsfaktorisering, da 4 i sig selv er et produkt af 2*2. Derfor er den korrekte primfaktorisering af 60: 3*2*2*5. Normalvis sorterer man faktorerne og bruger potenser, for at skrive det kortest muligt: 60=2²*3*5. Det er relativt simpelt at primfaktorisere små tal, man kan blot prøve sig lidt frem, men det bliver hurtigt meget svært når tallet stiger. (Riber, Primtal, 2008)

Indbyrdes primiske tal

To tal er indbyrdes primiske, hvis de eneste tal, der går op i begge er 1 eller -1. To primtal er derfor altid indbyrdes primiske, men det samme kan to trivielle tal være. For eksempel er 9 og 35 indbyrdes primiske, men det er 9 og 27 ikke, da 3 går op i begge. (Ibid)

Modulus

Modulus er en matematisk funktion, ligesom multiplikation og division er det. Dens funktion er at returnere resten ved en heltals division, fx 5 mod 2 = 1, fordi 2 går 2 gange op i 5 med en rest på 1. Modulus skrives typisk på en af disse tre måder: $, MOD eller %. Jeg vil fremover benytte mig af den sidste, %, da den bruges i Python. (Riber, Regning med rester, 2008)

Euklids modificerede algoritme

Euklids algoritme bruges til at finde den største fælles divisor mellem to tal. Den modificerede udgave er en udvidelse, der gør det muligt at beregne mere komplicerede ting. Til RSA-kryptering skal vi imidlertid blot bruge den til at finde den modulært inverse, og derfor kan en forsimplet udgave af den modificerede algoritme bruges. Den modulært inverse mellem to tal kalder vi t, og den skal bestemmes så q * t % p = 1, hvor q og p er indbyrdes primiske.

Her ses et eksempel ud fra de to indbyrdes primiske tal 71 og 31, der i øvrigt er primtal.

Først skrives de to tal under hinanden. Det mindste nederst. Vi se ser, hvor mange gange 31 går op i 71 uden rest, det gør det 2 gange, og skriver det til højre. Resten efter heltalsdivisionen skrives under 31. Derefter ser vi, hvor mange gange 9 går op i 31 og skriver antallet til højre. Processen gentages indtil resten er 1. Hvis resten bliver 0, er de to tal ikke indbyrdes primiske.

Andet trin i processen er at udvide tabellen med endnu en kolonne til højre.

Øverst i den nye kolonne skrives tallet 1. Formlen for at udregne et nyt tal i tredje kolonne er: tallet 2 rækker over – tallet over * tallet til venstre. I tilfælde, hvor pladsen 2 rækker over er tom, bruges 0. Feltet med -2 er blevet således udregnet: 0 – 1*2 = -2.

Næste felt: 1-(-2*3) = 7. Dette forsættes indtil man når næstnederste felt, altså det gule. Hvis tallet er negativt lægges det til tallet man dividerer ud fra, dvs. 71 + (-16) = 55.

Efter Euklids modificerede algoritme er udført, kan man tjekke efter om det endelige tal, t, passer som den modulært inverse. Dette er korrekt, og derfor er 55 den modulært inverse til 71 og 31. Flere eksempler kan findes i regnearksformat som bilag[1]. (Ibid)

RSA-kryptering i funktion

RSA-kryptering foregår som udgangspunkt over fire trin. Lad os sige, at person A ønsker at sende en hemmelig besked til person B.

Trin 1:

Først beder A om en nøgle til at kryptere med fra B. Anmodningen behøver ikke at være hemmelig.

Trin 2:

Derefter skaber B et nøglepar, hvoraf den ene nøgle sendes til A. Denne nøgle er den offentlige nøgle, og B kan derfor skrive den i avisen, hvis han lyster.

Trin 3:

A kan nu kryptere sin meddelelse med den tilsendte nøgle. Den krypterede meddelelse er umiddelbart ikke læselig, og kan derfor også skrives i avisen.

Trin 4:

B bruger nu den anden del af nøgleparret, som han har holdt hemmelig, til at dekryptere meddelelsen fra A. Det er vigtigt at han holder sin nøgle hemmelig, da den kan bruges til at dekryptere alle de meddelelser som A sender, hvis de forsætter med at bruge det nøglepar.

I foregående situation skabes et nyt nøglepar hver gang, A ønsker at sende en meddelelse til B. For at optimere processen kan A vælge at genbruge samme nøgle på al fremtidig kommunikation, det vil sige at trin 1 og 2 kan springes over. Hvis B vælger at offentliggør den offentlige nøgle, så vil alle der lyster det, kunne sende krypterede meddelelser til B. (Riber, RSA-kryptering, 2008)

Oprettelse af nøglepar

I trin to af RSA-krypteringsprocessen skaber B et nøglepar, denne proces vil nu blive forklaret og fremvist.

• Først vælges to store primtal p og q. Sæt n=p*q og k=(p-1)*(q-1).
• Udvælg et tilfældigt stort d, der er mindre end k. Bemærk at d skal være indbyrdes primisk med k.
• Udregn e som den modulært inverse til d modulus k. Altså: e * d % k = 1. Dette gøres vha. Euklids modificerede algoritme.
• Derefter holdes d hemmelig, det er altså den hemmelige nøgle, og de to tal n og e udgør den offentlige nøgle.

Sikkerheden ved RSA-kryptering ligger i brugen af enormt store tal, men for at forstå princippet kan man nøjes med langt mindre tal. Her ses et eksempel på kreationen af et nøglepar ud fra små tal. For oversigtens skyld, vil jeg dele processen op på samme måde som det generelle eksempel gør det.

• p = 11 og q = 13

n=p*q=11*13=143

                      k = (p-1)*(q-1) = (11-1)*(13-1)=10*12=120

• d = 77 — Dette er relativt primisk med k
• Her bruges bilaget xlsx igen.

                      e=53. Der tjekkes efter: d*e % k skal være lig 1. 77*53 % 120 = 1. e er udregnet korrekt.

• n og e er den offentlige nøgle der bruges til at kryptere med, og d er den hemmelige nøgle, der bruges sammen med n til at dekryptere. (Ibid)

Kryptering af en meddelelse

Ud fra forgående nøglesæt (ind)krypteres meddelelsen ’hej’. For at kunne det, skal teksten omdannes til tal. Det gøres ved at give hvert bogstav et nummer ud fra dets position i alfabetet, så a=01, b=02…,å=29 og så videre. ’hej’ bliver altså 08 05 10.

For det første skal n være større end hvert tal(bogstav) i meddelelsen. Da tallet højst kan være 29, som er å i det danske alfabet, skal n blot være større end denne værdi. Meddelelsen kan betragtes som en liste med talværdier for hvert bogstav og kaldes M. M[1] er altså 8, M[2] = 5 og M[3] = 10.

Nu beregnes den krypterede meddelelse.

Den krypterede meddelelse er listen C. Nu tilføjes de to resterende elementer i listen M.

Meddelelsen ’hej’ er nu krypteret og gemt i listen C[138, 70, 43]. Den kan nu sendes sikkert til modtageren, der vil dekryptere den for at kunne læse den originale meddelelse. (Ibid)

Dekryptering af en meddelelse

For at dekryptere beskeden, der ligger i listen C[08, 31, 82], bruges følgende beregning ud fra den hemmelige nøgle d=61 samt n=91:

(Ibid)

Hvorfor virker RSA-kryptering?

Selvom beregningerne undervejs i krypterings- og dekrypteringsprocessen er ganske få, så er baggrunden for dem langt mere kompleks. Her er beviset for at alle meddelelser, hvor 0<M<n gælder:

Ud fra tidligere beskrevet, så må følgende være sandt.

Dette gælder hvis M og n er indbyrdes primiske, altså (M,n)=1. For at få det første til at gælde når:

Bruges den kinesiske restsætning til at vise at p og q er forskellige primtal:

Tallet n er netop et produkt af to forskellige primtal, n=pq, så hvis vil enten p eller q være en divisor i M. Hvis p går op i M, så må , og derfor naturligvis også . Ud fra dette kan man sige at . Sidste del ligger i at bevise at gælder.

Da 0<M<n gælder, kan p og q ikke begge gå op i M, altså være divisorer til M. Så når vi antager at p går op i M, så må (q,M)=1. Ud fra Fermats lille sætning kan man da sige, at . Et helt tal t findes, således at gælder. Og følgende opnås:

Reducerer man med modulus efter at have brugt andre operationer, får man samme resultat, som når man først bruger modulus og derefter udfører andre operationer, for til sidst at bruge modulus. Her ses et algebraisk eksempel.

Samme regel gælder i øvrigt for alle andre operatorer, der bruges sammen med modulus. Her er slutningen på beviset.

Hvilket giver:

Ud over selve teorien der ligger bag RSA-kryptering, er det desuden interessant at kigge på, hvorfor det er sikkert. Som det tidligere er beskrevet, ligger sikkerheden i sværhedsgraden af primtalsfaktorisering af enormt store tal. Da primtalsfaktorisering også kan bruges til andet end kryptering, er der mange gennem tiden, der har forsøgt at finde hurtigere måder at gøre det på. På trods af dette, er det stadig ikke muligt at primfaktorisere et tal på omkring 2¹⁰²⁴ endnu, og RSA-kryptering i banker osv. benytter sig oftest af tal i omegn af 2²⁰⁴⁸. Ud fra dette må man nødvendigvis acceptere at metoden er sikker. (Ibid)

Kryptering af bogstaver

Vi har allerede set, hvorledes bogstaver laves om til tal for at kunne krypteres med RSA-krypteringsmetoden, men hvad gør man med fx mellemrum, kommaer og punktummer? Normalt tildeler man alle kendte tegn en talværdi, fx kunne ’.’ være 86 og ’,’ 87. Den internationale standard for disse værdier hedder ascii, og er meget udbredt. Man kan også vælge at bruge en arbitrær tildeling af talværdierne, så længe både modtager og afsender er enige om tildelingen. (Ibid)

Lange meddelelser

Det er muligt at kombinere ord eller meddelelser til lange beskeder, som krypteres ned samlet. Ved lange beskeder, kan det dog forekomme at tallet bliver meget stort, og derfor overstiger n. For at undgå det, deler man ofte meddelelser op i mindre pakker for eksempel af 100 tegn. Hver pakke krypteres, sendes og dekrypteres da hver for sig, for til sidst at blive samlet. For at lange beskeder er mulige, skal alle tegn i meddelelsen have samme længde. Ved de første 100 forskellige tegn, kan man blot benytte sig af to tal, fx a=00, b=01, osv. Når teksten er dekrypteret splittes pakkerne af fx 100 tegns størrelse op i tal med to cifre, der hver har en relation til et tegn. Når ascii-værdierne bruges, der indeholder 255 tegn, er man nødt til at bruge et andet talsystemet end det med 10 som grundtal. Derfor bruges det hexadecimale, der har 16 som grundtal, fordi det netop giver 256 muligheder inklusiv 00. (Ibid)

Elektronisk underskrift

En anden vigtig brug af RSA-kryptering er, når den bruges som elektronisk underskrift. På internettet er det vigtigt at kunne vide om, hvorvidt den man er i kontakt med rent faktisk er den rigtige, og ikke bare en, der udgiver sig for en anden. Elektroniske underskrifter bruges blandt andet til at forbinde sig med sin netbank og med Skats hjemmeside. Det fungerer på den måde, at alle har deres eget nøglesæt, hvoraf man selvfølgelig holder den ene hemmelig. Lad os sige at A vil forbinde sig til sin bank. Først krypterer A en meddelelse med sin hemmelige nøgle og sender den til banken. Derefter bruger banken A’s offentlige nøgle til at dekryptere meddelelsen med. Hvis meddelelsen giver mening, kan banken være sikker på, at det virkelig er A, der forsøger at få adgang til sin netbank. På den måde kan alle dekryptere A’s meddelelser og dermed verificere ægtheden.

Faktisk kan de to metoder sagtens bruges samtidig. Hvis A krypterer en besked med sin egen hemmelige nøgle og derefter krypterer den med en andens offentlige nøgle, så vil A på en gang gøre den ulæselig for andre en modtageren og verificere ægtheden med sin underskrift. Modtageren, B, kan dog ikke vide hvilken offentlig nøgle han skal bruge for at bekræfte identiteten af afsenderen, derfor er det kutyme at A tilføjer sit navn ukrypteret i sin meddelelse, før han bruger B’s offentlige nøgle til at kryptere den med. (Ibid)

RSA-krypteringsprogram

Følgende program benytter talværdierne fra sidste eksempel på RSA-kryptering – værdierne defineres i første del af programmet. Alfabetet sættes desuden ind i en dictionary(dansk: ordbog) ’alphabet’ sammen med almindeligt forekomne tegn – på samme måde som ascii-alfabetet, dog i en begrænset udgave. En dictionary er en liste med par, som er forbundne. Det kan bruges på følgende måde: alphabet[1] giver ’a’, hvilket bruges i begge konverterings funktioner. Der bruges tre funktioner, hvoraf de to første blot bruges til at konvertere tekst til tal(letter_to_num) og tekst til tal(num_to_letter).

1. # RSA-kryptering i Python 2.7
2. # Af: 
4. alphabet ={1:”a”,2:”b”,3:”c”,4:”d”,5:”e”,6:”f”,7:”g”,8:”h”,9:”i”,10:”j”,11:”k”,12:”l”,13:”m”,14:”n”,15:”o”,16:”p”,17:”q”,18:”r”,19:”s”,20:”t”,21:”u”,22:”v”,23:”w”,24:”x”,25:”y”,26:”z”,27:”æ”,28:”ø”,29:”å”,30:” “,31:”.”,32:”,”,33:”!”,34:”?”,35:”-“}
5. # alphabet indeholder også ofte brugte tegn som ?!., for at de også kan krypteres.
7. p =11
8. q =13 # To primtal vælges
9. n =p*q
10. k =(p-1)*(q-1)
11. d =77 # d og k skal være indbyrdes primiske
12. e =53 # Udregnes ud fra Euklids modificerede algoritme
14. defletter_to_num(text): # Denne funktion tager en tekst string og returnerer den som tal, hvor a=1, v=2 osv.
15.   num_list = [] #En tom liste laves, for at kunne opbevare tallene.
16.   for letter in text:
17.       for num in alphabet: # For hvert tal i dictionarien alphabet.
18.           if letter == alphabet[num]: # Hvis bogstavet er det samme som bogstavspartneren til num, fx alphabet[3] giver ‘c’
19. append(num) # Så tilføjes tallet til num_list
20.   return num_list #Listen returneres til videre brug
22. defnum_to_letter(num_list): # Denne funktion tager en liste med tal og returnerer den, som dens oprindelige bogstaver.
23.   text = “”
24.   for item in num_list:
25.       text += alphabet[item] # alphabet[item] returnerer højre side i et dictionary par. Dette lægges til strengen text.
26.   return text
28. defRSA_crypt(text, direction): # Selve krypteringsfunktionen tager to argumenter.
29.   num_list = [] # Tom liste laves, for at kunne opbevare tallene.
30.   if direction == “encrypt”:
31.       text = letter_to_num(text) # Konverterer teksten om til tal.
32.       key = e # Ved kryptering bruges nøglen e, der er defineret for oven.
33.   elif direction == “decrypt”:
34.       key = d # Her bruges dekrypteringsnøglen d, der er defineret for oven.
35.   else:
36.       print “Not correct direction.” # Tjekker for fejl i argumentet direction til funktionen.
37.   for num in text:
38. append(num**key%n) # tallet^nøglen % n   tilføjes til listen num_list
39.   return num_list # Listen returneres.
42. msg =”glaedelig jul” #På grund af problemer med de danske bogstaver ‘æøå’ bruges ae i stedet for æ
43. print“Start tekst: %s” % msg
44. msg_enc =RSA_crypt(msg, “encrypt”)
45. print“Krypteret: %s” % msg_enc
46. msg_dec =RSA_crypt(msg_enc, “decrypt”)
47. print“Dekrypteret(tal): %s” % msg_dec
48. print“Dekrypteret(bogstaver): %s” % num_to_letter(msg_dec)
50. # Test 1
51. ”’
52. Start tekst: glaedelig jul
53. Krypteret: [24L, 12L, 1, 70L, 75L, 70L, 12L, 3L, 24L, 127L, 43L, 21L, 12L]
54. Dekrypteret(tal): [7L, 12L, 1, 5L, 4L, 5L, 12L, 9L, 7L, 30L, 10L, 21L, 12L]
55. Dekrypteret(bogstaver): glaedelig jul
56. ”’
57. # Test 2
58. ”’
59. Start tekst: rsa-kryptering
60. Krypteret: [57L, 28L, 1, 107L, 33L, 57L, 38L, 48L, 102L, 70L, 57L, 3L, 27L, 24L]
61. Dekrypteret(tal): [18L, 19L, 1, 35L, 11L, 18L, 25L, 16L, 20L, 5L, 18L, 9L, 14L, 7L]
62. Dekrypteret(bogstaver): rsa-kryptering
63. ”’

Bemærk ved output at tallene i listerne efterfølges af et ’L’ for Long, hvilket skyldes tallenes størrelse efter opløftning i hhv. e og d. Programmet her er utraditionelt, idet både den offentlige og den hemmelige nøgle opbevares sammen. Det vil aldrig forekomme når RSA-kryptering bruges i praksis, da det er en seriøs brud på sikkerheden. Dog har jeg valgt at samle det hele under et for overblikkets skyld.

Slaget om Atlanten

Slaget om Atlanten var en søkrig i Atlanterhavet, der foregik fra 1939 til 1945, hvor Nazi-Tyskland overgav sig. Dermed var slaget den længste konflikt uden afbrydelser i 2. Verdenskrig. Slagets kombattanter var på den ene side de allieredes konvojer og på den anden, de tyske ubåde og handelsskibe udstyret med våben. De allieredes konvojer bestod oftest af et antal fragtskibe, der bragte varer og andet materiel fra Nordamerika og Afrika til Europa, samt nogle krigsfartøjer. Under hele 2. Verdenskrig benytte Nazi-Tyskland sig af forskellige kodemaskiner, for at sikre deres interne kommunikation fra at blive læst og udnyttet af de allierede. Den klart mest udbredte kodemaskine var Enigma, og derfor brugte de allierede uanede mængder af ressourcer for at forsøge at bryde koden og distribuere den viden, som de fik deraf. Hele processen med brydning og distribuering fik kodenavnet ULTRA. Den tyske marine var i modsætning til hæren ikke sikker på Enigma-kodens ubrydelighed, og derfor ombyggede de deres Enigma-maskiner i 1942, så der var plads til blandt andet fire rotorer, disse kaldtes ’Marine-Enigma 4’, og desuden forsynede de brugerne af maskinen med otte forskellige skiver i stedet for hærens fem. (Faurholt, 2009)

Brydning af Enigma

Efter 1. Verdenskrig var polakkerne naturligvis meget opmærksomme på, hvad tyskerne foretog sig. Da Tyskland i 1920’erne begyndte at bruge Enigma-maskinen, var det derfor den Polske efterretningstjeneste, der begyndte at bryde den først. Desuden havde både den engelske og franske efterretningstjeneste operationer, som gik ud på at bryde Enigma-koden. Der var ikke de store gennembrud i sagen før 1931, hvor Hans Thilo Schmidt, der arbejdede i det tyske forsvarsministeriums kryptoafdeling, blev spion for Frankrig. Umiddelbart gav det ikke noget væsentligt udbytte, før franskmændene valgte at sende al deres information fra spionagen til den polske efterretningstjeneste i slutningen af 1931. Det lykkedes for den polske kodebrydere i 1932 at fremstille maskiner, der løbende kunne bryde Enigma-koden. Fremskridtet var enormt på trods af, at forceringen tog lang tid. Den polske efterretningstjeneste hemmeligholdte deres forcering af Enigma-koden indtil faren for deres sikkerhed blev overvældende stor i 1939. Derefter delte de deres viden og specialiserede regnemaskiner til englænderne og franskmændene. Regnemaskinerne var essentielt en række sammenkoblede Enigma-maskiner, som ledte efter klartekst. Af ukendte årsager døbte polakkerne deres kodebrydningsmaskiner for ’Bomby’, hvilket de to andre nationer tog til sig med varianten ’Bomber’. I september 1939 flyttede det engelske kodebrydningshold ’Government Code and Cipher School’ til Bletchley Park. (Ibid) Stedet blev valgt ud fra flere faktorer: det var selvforsynende med vand og elektricitet; havde en jernbane blot få minutter fra hovedbygningen, hvilket gjorde transport til bl.a. London let; og derudover lå det cirka halvvejs mellem de to store universiteter i Cambridge og Oxford, hvor størstedelen af specialisterne blev fundet. (Showell, 2009) De to vigtigste matematikere i forceringsteamet var Alan Turing og Gordon Welchman, der skulle stå for at fremstille forbedrede udgaver af polakkernes ’Bomber’. I februar 1940 blev den tyske undervandsbåd U-33 sænket, og en del af lasten bjerget. Heriblandt var et antal rotorer til M4, der blev fundet i mandskabets lommer. Alle i den tyske marine havde fået streng besked på at destruere alt, som havde relation til Enigma-maskinen, og derfor havde de taget dele af maskinen og hoppet i det iskolde vand i håb om, at englænderne ikke ville finde deres lig. I april, kort efter modtagelsen af rotorerne blev den første engelske ’Bombe’ fremstillet, og i en periode havde englænderne indsigt i den tyske marines aktioner før de hændte. Uheldigvis for englænderne, blev indstillingerne for Enigma-maskinen skiftet ofte, og derfor mistede de deres momentum. For at kunne bryde den igen, krævede det mere og andet end blot matematik. Der var brug for kodebøger og materiel fra de tyske ubåde. Derfor indledte den engelske flåde en række angreb, som havde til formål at erobre tyske ubåde, før de kunne destruere materialet. Derudover var det ekstremt vigtigt, at tyskerne ikke fik mistanke til, at deres grej var blevet stjålet, for så ville de ændre deres procedurer og evt. bruge en anden kodemaskine – hvilket ville ødelægge alt det fortløbende arbejde i ULTRA. I 1942 skete det dog alligevel, at den tyske marine ændrede deres Enigma-maskine således, at den brugte fire rotorer i stedet for tre, hvilket efterlod holdet fra Bletchley Park i vildrede. Efterhånden som flere ubåde blev bjerget, i særhed U-559, blev forceringen af selv M4, Enigma-maskinen med fire rotorer, mulig på få timer. De tyske flyvevåben og militær brugte simplere udgaver af Enigma-maskinen, og beskeder fra disse blev nogenlunde brudt igennem hele 2. Verdenskrig. (Faurholt, 2009)

Hemmeligholdelse af forceringen

Det var en absolut nødvendig, at forceringen af den tyske kodemaskine blev holdt hemmelig, for at tyskerne ikke skulle ændre deres procedurer. Derfor opbyggede de allierede et system for overbringelse af dekrypteret information, der skulle vise sig at holde helt indtil midt i 1970’erne. Organisationen for hemmeligholdelsen og distribuering af dekrypteret materiale hed, som bekendt, ULTRA, og sørgede for at så få som muligt fik viden om forceringen. Ved næsten alle større stationer, der måtte få brug for materiale fra ULTRA, oprettede man små enheder på 4-5 personer, der var ekstra clearede i forhold til deres loyalitet og evner, disse hed SLU’s (Special Liason Units). Når en SLU modtog information fra hovedkvarteret i Bletchley Park var deres opgave at viderebringe informationen til den øverstbefalende i området, for at den derefter kunne bruge informationen. En anden vigtig forholdsregel var desuden, aldrig at udføre handlinger, der udelukkende var baseret på materiale fra ULTRA. Dette var blevet indskærpet på det strengeste fra toppen, muligvis fra Winston Churchill selv, der havde en stor interesse i arbejdet med forcering af Enigma-koden. Konsekvensen af den skræppe politik betød nødvendigvis, at både allierede soldater og civile indimellem måde lade livet, på trods af, at de allierede vidste besked om et specifikt angreb. (Ibid)

Enigmas betydning for Slaget om Atlanten

Storbritannien var i 1939 særdeles afhængig af leverancer med råvarer, fødevarer, krigsmateriel og brændstof fra den anden side af Atlanten. Tyskerne, som havde vished om Storbritanniens afhængighed, satte mange ressourcer af til bl.a. ubåde og overfladeskibe, der skulle forpurre konvojerne i at nå England. I løbet af krigens første måneder lykkedes det således tyskerne at sænke op i mod 500.000 tons tonnage, mens 16 mio. tons kom igennem til Storbritannien. Efter Nazi-Tysklands sejr over Frankrig i maj-juni 1940, kunne tyskerne benytte de franske havne i fx Brest og Lorient til ubåde. Af den grund fordobledes de tyske fartøjers rækkevidde i Atlanten. Sammen med en ændring af den tyske ubådstaktik til færdsel i grupper, blev dette begyndelsen på en sejrrig periode for Tyskland og til dels Italien, der kom med forstærkning i form af 20 ekstra ubåde. Tyskerne erobrede, ligesom de allierede, kodemaskiner og bøger fra modstanderens skibe. Deres ækvivalent til ULTRA lykkedes gennem en årrække at bryde de allieredes kodesystemer, hvilket havde stor indflydelse på Slaget om Atlanten, hvor de målrettet kunne gå efter Storbritanniens konvojer. Forceringen af koder var altså en flersidet krig, hvor man hele tiden skulle jonglere mellem at holde sit eget kodesystem sikkert og bryde modstanderens. Foråret i 1941 var en af højdepunkterne set fra tysk side i forhold til succes med sænkning af skibe. Der blev i perioden sænket omkring 650.000 tons tonnage, som blandt andet skulle have været brugt i Storbritannien til oprustning af invasionshæren. Endnu en gang spillede bjergningen af tysk kodemateriale en vigtig rolle i krigen, da U-110 blev tømt før den sank. Folkene i ULTRA benyttede det erobrede materiale til atter at komme med i forcering af Enigma. ULTRA var således ekstremt vigtig for sænkning af det tyske krigsskib ’Bismarck’.

Teknologiske fremskridt betød desuden indførelse af HF-pejlinger, nye RADAR-systemer, nye typer anti-ubådsmissiler og lignende. Derfor kan ULTRA ikke enehændigt tage æren for det øgede antal konvojer som undgik tyskernes ”ubådshegn”.

I oktober 1941 valgte Hitler at sende mange af Atlantens ubåde til Middelhavet, idet tyskernes konvojer med varer fra Afrika var under stort pres, takket være arbejdet i ULTRA. Året efter meldte USA sig ind i krigen, og den tyske øverstbefalende i marinen, Karl Dönitz, sendte et stort antal ubåde til USA’s østkyst, for at forhindre yderligere hjælp til de allierede i Europa.

Slaget om Atlanten kostede dyrt for begge parter, hvor de allierede mistede 3.500 skibe, 175 krigsskibe, tonnage på 14,5 millioner tons og ikke mindst 30.000 søfolk. Alle disse tal er cirkatal. Tyskerne mistede 783 ubåde og ca. 28.000 søfolk. Alt i alt nåede folkene i Bletchley Park fra 1941-1945 at bryde omkring 324.000 krypterede telegrammer.

Operation ULTRA gjorde uden tvivl en forskel på krigens forløb, men hvordan krigen var gået uden er uvist, og er svært at vurdere eller gætte sig frem til, da det er kontra faktuelt. Nogle historikere anslår, at krigen ville have varet 2-3 år længere end den gjorde og at det endelige udfald havde været det samme. (Ibid)

Kryptering i det moderne samfund

I vores moderne informationssamfund er udveksling af digitaliseret information blevet en del af hverdagen for de fleste. Millioner af e-mails bliver dagligt sendt, og internettet bruges i stadig stigende grad til handel med varer, såkaldt e-handel. For at det hele skal fungere, kræver det, at udvekslingerne sker sikkert. Derfor er kryptering blevet en afgørende del af det moderne informationssamfund.

Med krypteringsmetoder som RSA, har alle nu mulighed for at overføre information sikkert til hvem som helst. Dette har visse fordele og ulemper. For den almindelige borger, der bruger internettet til at tjekke sin netbank, sende e-mails og handle, er det en positiv ting. Man kan roligt og sikkert indtaste sine kortinformationer for at købe en vare online, fordi dataene bliver krypteret før de bliver sendt over netværket. Det er klart, at ikke alle forstår principperne, der ligger bag en teknik som RSA, men på trods af dette, har folk fået tiltro til metoden ud fra erfaring. Det lykkedes de sidste 20 gange, så hvorfor skulle det ikke virke denne gang? Virksomheder kan ligeledes benytte sig af den sikre kanal, som kryptering skaber til for eksempel at sende hemmelige arbejdstegninger til deres fabrikker i andre lande, uden at konkurrerende virksomheder kan opsnappe informationen.

Desværre har kriminelle også mulighed for at sende information sikkert, så de kan skjule sig fra politiet. Det er problemet bag metoden, at når alle kan udveksle information sikkert, så kan de, der ønsker at forårsage ondskab, gøre det samme.

En mulig løsning på det problem kunne være, at en uafhængig institution oprettedes, der skulle lagre alles hemmelige nøgler, for i tilfælde af brud på loven, at kunne udlevere en persons hemmelige nøgle til politiet. Dog ville det aldrig kunne lade sig gøre i praksis på grund af reglerne om menneskerettigheder og retten til privatliv.

Ingen kan dog længere være i tvivl om, at kryptologi er blevet en fasttømret del af samfundet, selvom ikke alle er bekendt med dette faktum.

Konklusion

Kryptologiens historie er lang og finurlig, hvilket grunder i menneskets gennemgående behov for at beskytte information. Selvom, der hele tiden kommer nye metoder frem, så beror de sig alle på samme grundlæggende principper. Under 2. Verdenskrig blev kodningsmaskinen Enigma brugt. Enigma-maskinens krypteringsmetode var en elektro-mekanisk variant over den polyalfabetiske kode. Teknologien gav mulighed et matematisk løft i sværhedsgraden af algoritmen, der gjorde den meget svær at forcere med datidens midler. Det lykkedes imidlertid de allierede at bryde den, ved brugen af de såkaldte ’Bomber’, som var maskiner, der ledte efter klartekst i ciffertekster. Fremstillingen af ’Bomberne’ krævede meget viden om Enigmas indre funktioner samt tidligere brugte indstillinger af maskinen. Forceringen af Enigma-koden fik stor betydning for krigens forløb, og mange historikere diskuterer stadig spørgsmålet om, hvad der var sket, hvis man ikke havde brudt koden. Efterhånden som teknologien udvikledes og computerne kom frem, blev der skabt nye metoder til kryptering. I 1977 satte RSA-kryptering en ny standard inden for kryptosystemer. Metoden er i dag særdeles udbredt og bruges af stort set alle, uanset om de ved det eller ej.

Litteraturliste

Faurholt, N. O. (2009). Hvor stor en betydning havde de allieredes brydning af Enigma-telegrammerne for 2. Verdenskrigs forløb? Krigshistorisk tidsskrift (2), s. 18-32.

Ibid. (u.d.).

Riber, P. (2008). Primtal. I Kryptering (s. 24-28). Systime.

Riber, P. (2008). Regning med rester. I Kryptering (s. 29-38). Systime.

Riber, P. (2008). RSA-kryptering. I Kryptering (s. 39-46). Systime.

Showell, J. P. (2009). Enigma – The Impenetrable Puzzle. I Enigma U-Boats: Breaking the Code (s. 7-20). Ian Allan Publishing.

Vestergaard, E. (u.d.). Matematiksider. Hentede 19. 12 2012 fra Enigma: http://www.matematiksider.dk/enigma.html

Wikipedia. (u.d.). Hentede 10. 12 2012 fra Caesar Cipher: http://en.wikipedia.org/wiki/Caesar_cipher

Wikipedia. (u.d.). Hentede 19. 12 2012 fra Vigenère cipher: http://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher

[1] Bilag: euklids_algoritme.xlsx