Koder og ciffre

Det er ikke kun kærestebreve, man ønsker skjult for trediemands øjne. Hvis f.eks. et datterselskab i London skal forhandle en kontrakt og får instruks fra hovedkontoret i København via e-mail, er det afgørende, at indholdet er skjult for modparten. Behovet for sikre koder og ciffre har aldrig været større end nu.

Emner

Begreber

Vi skelner mellem koder, der håndterer klartsprogs teksten ord for ord og ciffre, der håndterer klartsprogs teksten tegn for tegn.
En kodebog har to afsnit. Hver linie i det første indeholder ét ord og dets koder, som kan være vilkårlige kombinationer af tal og bogstaver. Andet afsnit er en sorteret liste af koder og deres tilhørende ord. Indkodningen består i at erstatte klartsprogs teksten ord for ord med koder. Afkodningen foregår den modsatte vej. Systemet forudsætter, at både afsender og modtager (men ingen uvedkommende) har et eksemplar af kodebogen.
Et ciffersystem hviler på en hemmelig nøgle, der ofte er let at huske f.eks. et ord eller en sætning. Med nøglens hjælp kan klartsprogs teksten oversættes til en ciffertekst og tilbage igen.

Ciffersystemer underdeles i transpositionssystemer og substitutionssystemer. I et transpositionssystem er cifferteksten en omordning af klartsprogs tekstens tegn. I et substitutionssystem erstattes klartssprogs tekstens tegn med andre. Ofte har man anvendt en kombination.

Koder kan ofte brydes, hvis man indsamler store mængder kodede meddelelser og især, hvis man har en ide om, hvad meddelelsen handler om. Under anden verdenskrig brød amerikanerne en japansk kode ved at sende en meddelelse om et (fingeret) angreb på en ø i en kode, man vidste, at japanerne havde brudt. Da der snart efter optrådte et hyppigt kodeord i japansk korrespondance, havde man en god ide om, hvad kodeordet stod for.

Ciffrer bryder man (hvis det er muligt) med overvejende matematiske metoder. Især talteorien har givet gode resultater.

[ Hovedmenu ] [ Ordliste ]

Transpositionssystemer

Mange transpositionssystemer bygger på skemaer. Klartsprogs tekstens bogstaver fyldes i et skema med s søjler, idet skemaet udfyldes rækkevis. Går s ikke op i antallet af tegn t, fyldes sidste række op med dummyer (meningsløse tegn f.eks. tilfældige bogstaver).
Cifferteksten består af skemaets søjler læst i en på forhånd aftalt rækkefølge. Nøglen 31542 betyder, at skemaet indeholder 5 søjler, der under cifreringen læses i rækkefølgen 3 - 1 - 5 - 4 - 2.
Decifreringen begynder med at bestemme rækketallet r af r = t / s. Derefter udfyldes skemaet og klartsprogs teksten kan læses.

Med 5 søjler kan der ciffreres på 5! = 120 måder, men med 9 søjler kan der ciffreres på 9! = 362880 måder.

[ Hovedmenu ] [ Ordliste ]

Substitutionssystemer

De enkleste substitutionssystemer består i at erstatte klartsprogs tekstens bogstaver med deres koder, som kan være tegn eller (kombinationer af) bogstaver. Har man en nogentlunde lang ciffertekst, kan systemet brydes v.h.a. statistik. Man finder frekvenserne af ciffertekstens tegn og sammenligner med frekvensfordelingen af alfabetets bogstaver i (lange) tekster på det sprog, meddelelsen antages at være skrevet i.

Er ciffertekstens bogstavers frekvensfordeling ca. den samme som en klarteksts, er der grund til at tro, at systemet er en transposition.

[ Hovedmenu ] [ Ordliste ]

Cæsar systemet

er et enkelt substitutionssystem, der bygger på modulo regning. Alfabetets bogstaver tildeles numre f.eks. a = 0, b = 1, c = 2, ... , å = 29. Er nøglen f. eks. bogstavet c, består krypteringen i, at klartsprogs tekstens bogstav med nummer nr erstattes af bogstav (nr + 2) mod 30.
Afkodningen sker ved at erstatte ciffertekstens bogstav med nummer nr med (nr – 2) mod 29.

Systemet giver naturligvis ingen sikkerhed. Man skal blot tjekke, hvilken af de 29 mulige nøgler, der giver et læseligt resultat.

[ Hovedmenu ] [ Ordliste ]

Vigenere systemet

Blaise de Vigenere I 1581 offentliggjorde den franske diplomat Blaise de Vigenere et kryptosystem, som i flere hundrede år blev anset for ubrydeligt. Vigenere - systemet bygger videre på Cæsar systemet, idet nøglen er et ord (eller sætning). Ciffreringen forgår ved at klartsprogs tekstens første bogstav "Cæsar - krypteres" med nøglens første bogstav. Andet bogstav med nøglens andet o.s.v. Når nøglen slipper op, begyndes forfra.
Er nøglens længde L, er

Med kendt nøgle findes klartsprogs teksten af

Beaufort systemet

er en variant af vigenere. Beaufort - systemet er enklere, idet man benytter samme algoritme ved ciffrering og deciffrering

Kasiskis metode

Charles Babbage I 1854 knækkede Charles Babbage vigenere - koder med en metode, der ofte kaldes Kasiskis metode efter den prøjsiske officer Friederich Kasiski, der (uafhængigt af Babbage) opfandt metoden i 1860-erne. Metoden går ud på at bestemme nøglelængden L af ciffersystemer af vigenere familien. Ideen er, at hvis en bogstavtrippel optræder flere gange i klartsprogs teksten med afstande, der er multipla af nøglelængden, vil dens bogstaver cifreres ens, så der også efter cifreringen optræder bogstavtripler. Metoden består altså i at finde ciffertekstens gentagne bogstavtripler, tælle afstandene mellem triplerne. Nøglelængden er største fælles divisor af afstandene, idet man frasorterer "mistænkelige" gentagelser som tilfældige. Giver triplerne ikke gevinst, prøver man med bogstav par.

Når først nøglelængden L er kendt, kan systemet brydes. Ideen er, at alle ciffertekstens bogstaver med positioner, der er kongruente modulo L er cifrerede med samme bogstav. En frekvensanalyse af cifferbogstaver fra samme kongruensklasse fortæller, hvilket bogstav, klassen er ciffreret med.

[ Hovedmenu ] [ Ordliste ]

Enigma

Enigma Enigma er en krypteringsmaskine, der blev opfundet i 1918 af Arthur Scherbius i Berlin. Maskinen var i forskellige udgaver rygraden i de tyske krypteringssystemer under anden verdenskrig. Den mest sofistikerede type anvendte den tyske ubådsflåde under storadmiral Karl Dönitz. Den tyske strategi gik ud på at udsulte England ved at torpedere de konvojer, der bragte forsyninger fra USA. Englænderne indrettede på Bletchley Park et kodebrydningscenter under ledelse af Alan Turing, som havde held og begavelse til at bryde koden. Derved kunne konvojerne omdirigeres og mange tab undgås.

Maskinen består af et skrivemaskinetastatur, der via et "omstillingsbord" leder elektrisk strøm gennem et system af fra 3 til 5 rotorer til at panel af el-pærer bemalede med alfabetets bogstaver. Ved hver indtastning drejer rotorerne én position, og en lampe lyser op med ciffertekstens bogstav.

Indstillingen af maskinen sker dels ved at forbinde omstillingsbordet, dels ved at sætte rotorernes udgangsstillinger. Der er således fra 264 = ½ million til 266 = 300 millioner forskellige indstillinger, der hver svarer til nøglelængder af samme størrelse.

[ Hovedmenu ] [ Ordliste ]

The one time pad

Vigenere familiens kryptosystemers svaghed ligger i den begrænsede nøglelængde. En nærliggende forstærkning er at anvende "uendelig" lange nøgler. F.eks. har man brugt en bestemt udgave af Shakespeares samlede værker eller Biblen som nøgle. Når det heller ikke giver tilstrækkelig sikkerhed, skyldes det, at f.eks. e krypteret med e forekommer hyppigt. En frekvensanalyse kan altså afsløre, at nøglen er klart sprog.
Problemet blev forsøgt løst i den kolde krigs tid af the one time pad.

One time pad Gordon Lonsdale og hans arbejdesgiver i Moskva havde hver et eksemplar af et lille hæfte med "tilfældige" bogstaver til kryptering/dekryptering af radio - korrepondancen. Navnet "the one time pad" skyldes, at man kun bruger en bogstavsekvens én gang, hvorefter siden destrueres.
Hvis nøglen består af virkelig tilfældige bogstaver, vil cifferteksten også bestå af tilfældige bogstavsekvenser. Ingen analysemetode kan afsløre nogen systematik.
Men her ligger netop svagheden. Maskingenererede "tilfældige" bogstaver er ikke absolut tilfældige. Computere er i dag så stærke, at de kan afsløre, hvilken algoritme, der er brugt til at danne den "tilfældige" nøgle. Og så er systemet brudt.

[ Hovedmenu ] [ Ordliste ]

Moderne kryptosystemer

I 1976 foreslog Diffie og Hellman et krypteringssystem med 2 nøgler - én hemmelig (kun kendt at afsender og modtager), og én offentlig. Ideen er, at det i praksis er umuligt at opløse et produkt af to store primtal a og h i faktorer. (Ved "store" forstår vi tal med 100 ciffre eller flere). Kender modtageren den hemmelige nøgle h, kan vi sende produktet a · h som åben nøgle. Kun modtageren er nemlig i stand til at finde a (ved at dividere). Alle andre må forsøge at faktorisere a · h.

RSA - systemet

Det følgende er oversat fra Francis Litterios artikel.

RSA algorithmen blev opfundet i 1978 af Ron Rivest, Adi Shamir, og Leonard Adleman.
Her er den relativt letforståelige matematik bag RSA public key kodning.

  1. Find to store primtal P og Q.
  2. Vælg E så
    1. E er større end 1
    2. E er mindre end PQ
    3. E og (P – 1)(Q – 1) er indbyrdes primiske (de har ingen fælles primfaktor).
    E behøver ikke være et primtal; men skal være ulige. (P – 1)(Q – 1) er lige (og altså ikke et primtal).
  3. Beregn D så (P – 1)(Q – 1) gå op i (DE – 1). Matemtikere skriver DE = 1 (mod (P – 1)(Q – 1)) og kalder D reciprok til E. Det er let gjort -- man skal blot finde et heltal X, så D = (X(P – 1)(Q – 1) + 1)/E er et helt tal og benytte den tilsvarende D-værdi.
  4. Krypteringsfunktionen er C = (TE) mod PQ, hvor C er cifferteksten (et positivt tal), T er klartsprogsteksten (et positivt tal). Klartsprogsteksten T skal være mindre end PQ.
  5. Afkodningsfunktionen T = (CD) mod PQ, hvor C er cifferteksten (et positivt tal), T er klartsprogsteksten (et positivt tal).
    Den offentlige nøgle er talparret (PQ, E). Den private nøgle er tallet D (vis det ikke til nogen). Produktet PQ er modulen (i litteraturen benyttes ofte N). E er den offentlige eksponent. D er den hemmelige eksponent.
  6. Man kan offentliggøre den offentlige nøgle, fordi der ikke kendes nogen let måde at beregne D, P eller Q ud fra kun PQ og E (den offentlige nøgle). Hvis P og Q er nogle hundrede ciffre lange, vil solen være brændt ud længe før selv den stærkeste computer kan faktorisere PQ i P og Q.

[ Hovedmenu ] [ Ordliste ]

Links

Generelt

Engelsksprogede sider om vigenere systemet

One time pad

Enigma

[ Hovedmenu ] [ Ordliste ] [ Tilbage til hovedsiden ]