Kryptering.

En introduksjon til «hemmelig skrift»,
beregnet på elever ved Oslo By Steinerskole,
datalinjen, 2. klasse.

(Kilder: www.PGPi.org, www.pgp.com, Simon Singh: Koder; Aschehoug 2000,
www.ugrad.cs.jhu.edu/~russell/classes/enigma; http://frode.home.cern.ch/frode/crypto/
http://micro.magnet.fsu.edu; http://eve.physics.ox.ac.uk/NewWeb/Research/communication/communication.html)

Introduksjon:

Mennesker har i uminnelige tider hatt et behov for å kunne holde enkelte ting hemmelig. I tusener av år har konger, dronninger, statsledere og ikke minst krigsherrer hatt behov for å kunne gi beskjeder til andre, uten at en tredjepart kan forstå hva som blir sagt. Det er mange måter å gjøre dette, man kan gjemme selve meldingen, et eksempel er Herodot («historieskrivningens far» i følge Cicero) som forteller om konfliktene mellom Hellas og Persia i femte århundre f. Kr. Som han oppfattet som en krig mellom frihet og slaveri. Han så dette som en konfrontasjon mellom de uavhengige greske statene og og persisk undertrykkelse. I følge Herodot var det hemmelig skrift som reddet Hellas fra å bli hærtatt av Xerxes, persernes diktator. Xerxes var forbannet på Athen og Sparta fordi de, i motsetning til alle andre naboland ikke kom med gaver til ham i forbindelse med anleggingen av Persepolis, hans nye hovedstad. Xerxes var fast bestemt på å hevne denne blodige fornærmelsen og i 5 år samlet han en stor hær og i år 480 f.Kr. Var han klar til å angripe. Det var meningen at dette skulle være et overraskelsesangrep, men under veis var det en som hadde lagt merke til denne opprustningen, nemlig Demaratos, en greker som var utvist fra sitt hjemland. Til tross for at han var utvist var han lojal mot Hellas. Han bestemte seg for å advare spartanerne mot angrepet som var på vei. Problemet var hvordan han kunne sende en beskjed uten at de persiske vaktene fikk snusen i det, for da ville han umiddelbart blitt henrettet. På denne tiden var det vanlig å skrive på tretavler som var dekket med bivoks. Efter bruk kunne voksen skrapes av og legges på igjen og tavlen var klar til bruk igjen. Demaratos fant på å skrive rett på tretavlene og så legge voks utenpå skriften så det så ut som om tretavlene var ubrukte. Han skrev sin melding og sendte tavlene til Hellas. Det tok litt tid før Kleomenes datter Gorgo, som som var gift med Leonidas gjettet at det var skrift under voksen, men fremdeles var det nok tid til at hellenerne kunne forberede seg på angrep. De begynte å ruste opp, blandt annet ble overskuddet fra statens sølvgruver, som tidligere hadde blitt fordelt mellom borgerne, gitt til marinen og det ble bygget 200 krigsskip. For å gjøre en lang og meget interessant historie kort; Xerxes led et ydmykende nederlag.

Herodot forteller også en annen morsom historie i samme sjanger. Det dreier seg om historien om Hisitaios som ville oppmuntre Aristagoras fra Milet til opprør mot perserkongen. For å kunne sende sine oppfordringer på en trygg måte barberte Hisitaios hodet til budbringere og skrev meldingen på skallen deres, og ventet så til håret hadde vokst ut igjen før de reiste av gårde med hemmelige meldinger. Ting gikk ikke like fort den gang som det gjør nå...

Dette er eksempler på hemmelige meldinger som er skjult slik at kontrollører ikke oppdager dem. Dette kalles, med et faguttrykk, steganografi fra det greske ordet steganos som betyr skjult og grafein som betyr å skrive. Dette er en metode som har vært brukt i tusener av år i en rekke kulturer. For eksempel skrev kineserne sine hemmelige meldinger på tynne silkebånd som ble rullet sammen, dekket med voks og så spiste budbringeren vokskulen. Vi trenger ikke gå inn på hva som skjedde i den andre enden :-)

Steganografi omhandler også bruken av «usynlig» blekk. På 1400 tallet beskriver den italienske vitenskapsmannen hvordan man kan lave en spesiell type blekk av 25 gram alun og en halv liter eddik. Når man skriver med dette blekket på et hårdkokt egg vil blekket trenge gjennom skallet og skriften finnes igjen på hviten inne i egget. Det kan siden leses hvis du skreller egget. Enklere former for usynlig blekk brukes ofte av barn, de skriver med melk på papir og lar det tørke. Hvis du nå varmer arket forsiktig vil melkeskriften bli brun og lesbar. (Dette kan for så vidt også gjøres med urin, og det finnes eksempler fra det tyvende århundre hvor spioner har gjort dette.)

Steganografi er greit og det gir en viss beskyttelse. Imidlertid er det slik at dersom budet blir oppdaget og ransaket kan meldingen bli funnet og lest. Dette er en alvorlig begrensning.

Kryptografi:

Parallelt med steganografien ble det derfor utviklet en annen kunst; kryptografien fra gresk kryfos som betyr «skjult». Målet er ikke lenger å gjemme brevet, men å sørge for at innholdet ikke kan tydes. Denne prosessen med å skjule innholdet, ikke selve meldingen kalles kryptografi.

For å gjøre en melding uleselig for andre enn avsender og den rette mottageren må innholdet «stokkes om» efter en bestemt regel som bare de som skal ha lov til å lese meldingen vet hvordan virker. Slik kan mottageren reversere prosessen og gjøre meldingen lesbar. Man følger en kjent, men hemmelig protokoll. Selv om en fiende snapper opp en melding kjenner hun ikke protokollen som må brukes for å dekryptere meldingen.

Kryptografien deles gjerne i to hoveddeler; transposisjon og substitusjon. I transposisjon blir bokstavene ganske enkelt byttet om slik at det dannes et anagram. Hvis meldingen er kort, slik som enkeltord, er dette en usikker metode. Dette er fordi et begrenset antall bokstaver bare kan stokkes om på et begrenset antall måter. For eksempel kan et ord på tre bokstaver bare ordnes på 6 måter. La oss ta et eksempel: HUS, HSU, USH, UHS, SUH og SHU. Efterhvert som antall bokstaver øker, vil antall kombinasjoner øke dramatisk. Det øker så mye at det ikke er mulig å komme tilbake til den opprinnelige meldingen hvis du ikke kjenner protokollen. Se bare på denne korte setningen. Den består av bare 35 bokstaver, men likevel er det mer enn 50 000 000 000 000 000 000 000 000 000 000 (50 kvintillioner) forskjellige måter å stokke dem om. Hvis en person kan kontrollere et arrangement per sekund, og alle mennesker i verden arbeidet dag og natt ville det likevel ta mer enn tusen ganger den tiden universet har eksistert å kontrollere alle arrangementene. Vi bytter altså bare om på bokstavene. Dette kalles også scrambling.

Alternativet til transposisjon er substitusjon. En av de eldste beskrivelsene av kryptering ved substitusjon finnes i Kamasutra, den kjente teksten fra det fjerde århundre e.Kr.. Kamasutra anbefaler at kvinner skal studere 64 ferdigheter. Nummer 45 på listen er mlecchita-vikalpa eller hemmelig skrift. Dette ble anbefalt for at kvinnene skulle kunne skjule detaljer ved sine hemmelige forhold. En av teknikkene som anbefales er å lave tilfeldige par av bokstavene i alfabetet og så bytte ut bokstavene, parvis, med hverandre. La oss se på et eksempel. Vi danner par av bokstaver (engelsk alfabet) og krypterer en kort melding.

A

D

H

I

K

M

O

R

S

U

W

Y

Z

↕

↕

↕

↕

↕

↕

↕

↕

↕

↕

↕

↕

↕

V

X

B

G

J

C

Q

L

N

E

F

P

T

Hvis vi nå hadde skrevet for eksempel: KOM VED MIDNATT og kryptert det ved hjelp av nøkkelen over ville vi skrevet: JQC AUX CGXSVZZ. Ser du systemet?

Denne formen for hemmelig skrift kalles et substitusjonschiffer, siden hver bokstav blir substituert det vil si byttet ut med en annen. Ved transposisjon beholder hver bokstav sin identitet, men de bytter plass. Ved substitusjon endrer hver enkelt bokstav identitet, men beholder sin posisjon.

Litt historisk; den første dokumenterte bruk av substitusjonschiffer finner vi i Julius Cæsars Gallerkrigen. Cæsar beskriver hvordan han sendte en hemmelig melding til Cicero, som var beleiret på dette tidspunktet. Cæsar byttet ut de latinske bokstavene med greske og gjorde dermed teksten uleselig for fienden.
Likeledes har man en detaljert beskrivelse i Svetons Keiserens liv LVI, som ble skrevet i andre århundre e.Kr. Over andre chiffre som Cæsar brukte. I en av disse erstatter Cæsar ganske enkelt hver bokstav i meldingen med bokstaven som befinner seg tre plasser lenger ut i alfabetet.
Kryptografer (de som krypterer meldinger) bruker ofte to begreper som det er viktig å få med seg. Det første er klartekstalfabet som er det alfabetet som teksten opprinnelig er skrevet i. Chifferalfabetet er det alfabetet som brukes til å kryptere meldingen, altså de bokstavene som brukes til å skrive den hemmelige meldingen, jevnfør alfabetet over.
I Cæsars chiffer ville vi sagt at nøkkelen er 3, og vi kunne lavet følgende krypteringsalfabet (nøkkel) for å gjøre en klartekst om til chiffertekst:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z Æ Ø Å

D E F G H I J K L M N O P Q R S T U V W X Y Z Æ Ø Å A B C

Her er en kort, chifferert tekst med et kjent utsagn fra Julius Cæsar himself: se om du klarer å finne ut hva som står:

MDNWD DOHD HVW!

Husker du i hvilken anledning han sa dette? Riktig! Det var da han skulle krysse elven Rubicon. For øvrig betyr setningen, som er på latin: «terningen er kastet».

Selv om det her er brukt tre bokstaver i forskyvningen kunne det være et annet antall. I det norske alfabetet kunne det være inntil 28 plasser (25 i det engelske alfabetet). På den måten kan det laves 28 forskjellige chiffre. Nå er de5t ikke slik at forskyvningen må være et bestemt antall plasser; man kunne godt blande bokstavene i en tilfeldig rekkefølge og sette opp en nøkkel efterpå. Det ville gi oss et dramatisk større antall mulige chiffer (nøkler). Faktisk ville det bli mer enn 400 000 000 000 000 000 000 000 000 (eller 400 kvadrillioner).

Vi kan se på hver enkelt nøkkel som en generell krypteringsmetode som kalles algoritmen, og en nøkkel som gir detaljene ved krypteringen. Her er det viktig å forsøke å forstå en ting; i de fleste tilfelle vil en fiende ofte ha en sterk mistanke om hvilken algoritme som er brukt, men ikke hvilken nøkkel. Så sant nøkkelen er sterk nok (tilstrekkelig komplisert) vil ikke fienden klare å lese meldingen, selv om hun vet at det er brukt bokstavsubstitusjon som algoritme.

Avsender Mottager

klartekst + nøkkel → algoritme → Chiffertekst → algoritme → nøkkel + klartekst.

Det er et fast prinsipp i kryptografi at det ikke skal være nødvendig å holde algoritmen hemmelig, det skal være nok at nøkkelen er fullstendig konfidensiell. Dette kalles også Kerckhoffs prinsipp.

Det er også vanlig å bestemme omstokkingen i alfabetet ut fra et kodeord. La oss se på et eksempel: Vi velger kodeordet skole og setter opp et substitusjonsalfabet:

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

Æ

Ø

Å

s

k

o

l

e

a

b

c

d

f

g

h

i

j

m

n

p

q

r

t

u

v

w

x

y

z

æ

ø

å

Vi kunne valgt et bedre kodeord, et som sørger for at ingen bokstaver havner i par med seg selv, jfr. E T U V W X Y Z Æ Ø og Å, men vi tar ikke det så tungt nå.
Poenget er at vi bare trenger å overføre (holde hemmelig) et kort kodeord, ikke hele alfabetet. Det er lett å huske et kodeord, et scramblet alfabet er vanskelig å huske og hvis vi skriver ned koden er det alltid en mulighet for at den faller i fiendens hender.
Hva står det her?

Låqhdk vshbt gmlemql

Uten å kjenne kodeordet er det ikke helt lett å se hva som står her. Allikevel er det mulig å knekke en slik kode. Kampen mellom kodemakere (kryptografer) og kodeknekkere (chifferknekkere) er på mange måter som kampen mellom leger og bakterier. Jo bedre antibiotika legene skaffer seg, jo mer muterer bakteriene og blir resistente (motstandsdyktige) mot antibiotikaen legene har utviklet.

En metode for å knekke en slik kode som over er kryptanalyse. Dette er en metode som brukes for å knekke et substitusjonschiffer uten å kjenne nøkkelen.
Det skulle bli araberne som fant ut hvordan man knekker et monoalfabetisk substitusjonschiffer (et chiffer som består av bokstaver og eventuelt tegn; man kunne jo tenke seg å erstatte A med # for eksempel). Det de gjorde, i meget korte drag, var å forsøke å sette deler av koranen sammen i riktig, kronologisk rekkefølge. De fant ut at enkelte ord bare dukket opp i noen av de 114 tekstene som til sammen utgjør koranen. Hvert av disse 114 kapitlene beskriver en av Muhammeds åpenbaringer. De forsto at de tekstene som hadde høy frekvens av enkelte ord måtte tilhøre den senere delen av koranen fordi det var relativt sett, sent utviklede ord. Forskerne så også på bokstaver og oppdaget at noen bokstaver er vanligere enn andre. For eksempel er a og l de vanligste bokstavene i arabisk. Dette er delvis fordi den bestemte artikkelen «al», mens bokstaven j bare forekommer en tiendedel så ofte. Det var den arabiske vitenskapsmannen Ismail al-Kindi fra det 9. århundret som først beskrev teknikken: frekvensanalyse. Prinsippet hans gikk ut på at dersom vi vet hvilket sprog chifferteksten er skrevet på kan vi finne en del sider (ofte trengs det mange sider) med klartekst i det aktuelle sproget. Derefter teller vi antall av hver eneste bokstav og finner derved frekvensen som hver bokstav opptrer med. Vi kaller den som opptrer hyppigst for den første, den nest hyppigste den andre også videre. Så ser vi på den kodete teksten og teller opp bokstavene og finner deres frekvens. Derefter bytter vi ut den første i chifferteksten med den første i klarteksten, den andre i chifferteksten med den andre i klarteksten også videre til vi har løst koden.
På norsk er den vanligste bokstaven e efterfulgt av t og a. Jo kortere teksten er, jo vanskeligere blir det å dechiffrere den. Det er fordi grunnlaget for frekvensanalyse ikke blir godt nok. Se på dette eksemplet:

«From Zanzibar to Zaire and Zambia ozone zones make zebras run zany zig-zags»

På engelsk har bokstaven Z en frekvens på 0,1%, men i denne setningen er den sterkt overrepresentert.

De fleste som har vært i Speideren har lavet koder flere ganger. Det er ikke uvanlig for barn heller å lave koder. Man kan tenke seg at barn laver sitt eget «alfabet» av små tegninger som representerer bokstavene i alfabetet. Det finnes utallige eksempler på slike systemer, og det verste er at de virker! I alle fall overfor barn...

Det ubrytelige chiffer.

I mange hundre år ble det monoalfabetiske substitusjonschiffer ansett som tilstrekkelig for å ivareta sikkerheten. Det skulle gå hundrevis av år fra Cæsar begynte å bruke chiffer, til den neste store utviklingen i chifferkunsten. Italieneren Leon Battista Alberti som er mest kjent som arkitekt kom på en god ide. Han foreslo å bruke to chifferalfabetet, og veksle mellom dem. La oss ta et eksempel:

Nå krypterer vi annenhver bokstav i vår hemmelige melding med henholdsvis Chiffer1 og Chiffer2. Hvis vi vil kryptere hallo ville vi kryptere den første bokstaven (h) med chiffer1 og den neste (a) med chiffer to, den tredje (l) med chiffer1, den fjerde (l) med chiffer2 og den siste (o) med chiffer1.
Vi får: xgmll. Det store med denne metoden er at en og samme bokstav kan opptre på forskjellig måte i chifferteksten. Den første «l-en» blir kryptert som m og den andre «l-en» blir kryptert som l. På samme måte ser vi at bokstaven l i chifferteksten blir kodet på to forskjellige måter. Den første betyr «l» og den andre betyr «o». Dette er et alvorlig problem for en som ønsker å bruke frekvensanalyse på denne chifferteksten.

Allikevel var det ikke før senere, da franskmannen Blaise de Vigenère videreutviklet dette til et virkelig sterkt kryptografisk system. Styrken i Vigenères chiffer ligger i at det ikke bruker to, men 26 forskjellige alfabet til chiffreringen. Det første du gjør er å sette opp et såkalt Vigenèrekvadrat, et alfabet i klartekst efterfulgt av 26 chifferalfabeter. Disse chifferalfabetene føler systemet i en Cæsarforskyvning, det første forskjøvet én plass, det neste 2 plasser, det tredje 3 plasser også videre.

Vigenères chifferalfabet.

Den øverste raden i tabellen (den med små bokstaver) representerer det vanlige alfabetet som vi har brukt i klartekst og nå skal vi kryptere meldingen. Vi kan enciffrere (kode) hver enkelt bokstav efter et hvilket som helst av de forskjøvne alfabetene. Hvis vi bruker chiffer nummer 3 vil g bli kodet som J, men hvis vi bruker chiffer nummer 14 blir g chifferert som U. Det å bruke bare et tilfeldig alfabet til chiffrering ville ikke gi noen sterk kode, det er bare en Cæsarforskyvning med ukjent nøkkel, det ville bare være 26 mulige nøkler og en smal sak å dechiffrere meldingen. Styrken i chifferet ligger i at man bruker forskjellig chifferalfabet for hver bokstav i klarteksten som skal kodes. Dette betyr at vi kunne kode en melding ved å chiffrere første bokstav med chifferalfabet nummer 12, andre bokstav i klarteksten med chifferalfabet nummer 23, tredje bokstav med chifferalfabet nummer 3 også videre. For at mottager skal kunne dekryptere meldingen må han vite hvilken rekke i Vigenère kvadratet som er brukt på hver bokstav.
Mon tro hvordan vi skal få til det?
Vi kan bruke et nøkkelord. La oss ta et eksempel:

Vi velger å enchiffrere følgende korte melding:

advar troppene om at fienden kommer

Vi bruker nøkkelordet: PILS

Det første vi gjør er å skrive meldingen uten mellomrom mellom ordene og så skriver vi nøkkelordet over setningen i gjentagelser slik at alle bokstaver i meldingen korresponderer med en bokstav i nøkkelordet.

Nå begynner den egentlige krypteringen. Vi gjør som følger: for å kryptere den første bokstaven (a) begynner vi med å finne nøkkelbokstaven over den, i dette tilfellet er det P, og dette gir oss svar på hvilken rekke i Vigenèrekvadratet som er brukt. Den rekken som begynner med P, rekke nummer 15, er den som er brukt for å kryptere den første bokstaven. Vi ser nå på hvilken bokstav som ligger i krysningspunktet mellom rad 15 og den aktuelle bokstaven i klartekst. I dette tilfellet bli det P. Nå tar vi neste bokstav i klarteksten og finner den matchende bokstaven i nøkkelordet og finner frem til krysningspunktet i Vigenèrekvadratet. Slik blir den: d matcher I som gir rad 8. I krysningspunktet mellom rad 8 og den kolonnen som har d finner vi L. Slik fortsetter vi til vi har en chiffertekst.

Chifferteksten blir PLGSGBCGEXPFTWXSINTXCLPFZWXETZ. Denne er det meget vanskelig å knekke ved hjelp av frekvensanalyse. Allikevel har vi valgt et veldig dårlig nøkkelord her. Det er bare 4 bokstaver og det er veldig lite. Det er faktisk ugjennomtrengelig ved frekvensanalyse. Hvis vi nå hadde valgt et lengre nøkkelord, eller en nøkkelsetning for den saks skyld ville vi øke styrken i chifferet meget betraktelig. Det som gjør det så vanskelig er at for eksempel blir bokstavene pp i ordet troppene enchiffrert som EX. I tillegg til dette gir Vigenère chifferet mulighet for et meget stort antall nøkler. Man kan velge et eller flere tilfeldige ord, en setning eller bare en bokstavrekke som ikke betyr noe i seg selv. Mulighetene er legio. Det er altså ikke mulig å bryte chifferet ved å prøve alle mulige kodeord, antallet mulige kodeord er rett og slett for stort.

Dette chifferet ble regnet som ubrytelig i flere hundre år, og det skulle en engelskmann til for å danke ut denne franske oppfinnelsen ( Vigenère var ikke alene, men han fikk æren). Denne engelskmannen het Charles Babbage. Han er også tilkjent æren for å ha hatt ideen til konstruksjonen av verdens første programmerbare datamaskin (the analytical engine #2), et arbeid som ikke ble avsluttet i hans levetid. Dette på grunn av manglende økonomiske midler. Babbage klarte å knekke Vigenèrechifferet, en bragd som bare kan måles mot arabernes oppfinnelse av frekvensanalyse og knekkingen av det monoalfabetiske substitusjonschiffer.
Babbage krevde ikke hverken avansert matematikk eller programmerbare regnemaskiner, det var basert på ren list.
Babbage var interessert i chiffre helt fra barndommen. Han hadde nok en spesiell begavelse for akkurat dette og han sa selv at dette skaffet ham problemer som barn. « De store guttene laget chifre, men hvis jeg fikk tak i noen få ord, fant jeg vanligvis nøkkelen. Det hendte at eierne av det avslørte chifferet banket meg opp, enda de hadde bare sin egen dumhet å skylde på». I sin selvbiografi skrev han: « Dechiffrering er efter min oppfatning en av de mest fascinerende kunster».
Babbage begynte også å skrive en bok: «The philosophy of Decyphering». Denne boken skulle inneholde eksempler på kryptering og dekryptering med et eksempel og en oppgave til leseren for hver kjente krypteringsmåte. Dessverre ble den, som mye annet Babbage drev med, aldri ferdig.

Babbage bestemte seg for å forsøke å løse Vigenèrechifferet. I frekvensanalyse bruker man bokstavenes frekvens til å knekke koden. I et Vigenèrechiffer er dette mye vanskeligere fordi chifferet sørger for at frekvensen «glattes ut» på grunn av skifting mellom alfabeter. Vigenèrechifferets store styrke ligger i at samme bokstav kan bli kryptert på forskjellige måter. Hvis nøkkelordet er PILS kan hver enkelt bokstav i klarteksten chiffreres på 4 forskjellige måter.
La oss se på tabellen over Vigenère kvadratet ovenfor og se hva som skjer med bokstaven f når den krypteres med nøkkelordet PILS.

• Hvis vi bruker P til å enchiffrere f blir det U

• Hvis vi bruker I til å enchiffrere f blir det N

• Hvis vi bruker L til å enchiffrere f blir det Q

• Hvis vi bruker S til å enchiffrere f blir det X

Dette skaper en del gjentagelser i en chiffrert tekst og hvis teksten er lang nok vil det være mulig for en kryptanalytiker å finne et mønster. Mønsteret er matematisk og baserer seg på at frekvensanalyse ikke bare kan brukes på bokstaver, men også på hele ord. For eksempel er det mest brukte ordet på engelsk: «the». dette kan da krypteres på 4 måter ved hjelp av Vigenèrekvadratet og kodeordet PILS. Problemet for de som laver koden er at når det gjentas vil det være en matematisk beregnbar forskyvning. Det lar seg altså finne mønstre i Vigenèrechifferet. Å gå gjennom en slik dekryptering vil være langt utenfor det som er meningen med dette kompendiet.

Den mekaniserte krypteringen dukker opp.

Det som sannsynligvis gjorde at arbeidet med å finne et nytt og sikkert chiffer, efter at Vigenèrechifferet var knekket var at radioen ble oppfunnet. Telegrafen hadde eksistert i over femti år og ble flittig brukt av mange. Også mennesker som hadde hemmeligheter. Det kunne være alt fra «ulovlig» kjærlighet til forretningshemmeligheter. Disse menneskene ville også bruke telegrafen, men de stolte ikke alltid på at telegrafisten holdt helt tett...
Det ble sendt mange telegrammer som var ren kode, vanligvis bare grupper av tall. Det var nok ikke så spennende og interessant å være telegrafist som vi ofte får inntrykk av i filmer. For det meste satt de og mottok og videresendte meldinger som de ikke forsto innholdet av. En melding kunne se slik ut:

824 497 114 620 772 004 924 066 127 587 902 401,

og kunne representere en hemmelig kode som betyr «Jeg elsker deg», sagt i konfidensialitet mellom to ekteskapsbrytere :-) Koden kunne være avtalt pr. brev og benyttes lenge, så sant ingen fikk tak i nøkkelen. Det var mye av den slags telegrammer. ikke minst av de forretningsmessige og de som gikk mellom diplomater, militære enheter og myndigheter.

Hva hadde så dette med radio å gjøre? Jo det var nok mest militært. Under den første verdenskrig begynte man å bruke radio i felten. Dette var både et fantastisk fremskritt og en kilde til alvorlige bekymringer. Fordelen var jo at man kunne kommunisere med hvem som helst uten å måtte trekke telefon / telegrafledninger. På den annen side, og dette var alvorlig, kunne man ikke lenger være sikker på at ingen lyttet. Radiosignaler har den styrken at de når frem til alle (vel, noen begrensninger er det jo), men du har ingen kontroll over hvem, eller hvor mange som lytter. Det er umulig å sende et radiosignal til bare noen få, uten at det er tilgjengelig for flere, og du kan aldri vite hvem som lytter i øyeblikket.
En av de gruppene som først grep muligheten til å bruke radio var de som tidligere hadde hatt størst problemer med å kommunisere med egne avdelinger; nemlig marinen som tidligere ikke hadde hatt mulighet for beskjedformidling med krigsskip til havs.

Under den første verdenskrig var det en stadig pågående kamp mellom kodemakere og kodeknekkere. Allikevel lå, stort sett hele tiden, kodemakerne et hakk foran kodeknekkerne. Dette var delvis fordi det er mye lettere å lave nye nøkler enn det er å knekke dem. Husk at dette foregikk manuelt på denne tiden. Man fant mange kodenøkler og nye ble lavet, men et problem var hele tiden altoverskyggende. Nøklene måtte hemmeligholdes. Mottageren av en kryptert melding måtte ha nøkkelen. Ellers kunne han ikke dekryptere den. Det måtte altså, på en eller annen måte, være mulig å gi mottageren nøkkelen uten at noen kunne snappe den opp. I tilfellet marinen, kunne en tenke seg at dersom skipet skal være ute i 30 dager på tokt laver vi en liten bok med «dagens kode» 30 ganger. Kanskje vi legger til en god del flere nøkler også, i tilfelle vi trenger å sende mer enn en melding per dag, eller om skipet skulle bli forsinket i havn. Hver gang vi har sendt en melding, eller mottatt en melding river både avsender og mottager av den første siden i kodeboken og kaster den. Det er ikke så viktig om noen finner den, den er brukt og skal aldri brukes igjen. På denne måten kunne vi få til god sikkerhet med et Vigenèrechiffer.
Hva nå om dette skipet blir angrepet? Dersom kapteinen vurderer at de holder på å tape vil hans viktigste oppgave være å sørge for at kodeboken, de ubrukte arkene, blir ødelagt slik at de ikke faller i fiendens hender. Det er de ubrukte arkene som er viktige fordi de kan brukes både til å dechiffrere meldinger man avlytter og de kan brukes til å sende falske meldinger som fremstår som ekte! Man kan lure motstanderen på den alvorligste måte!
Systemet er greit nok det, så lenge nøklene er tilstrekkelig sterke (dvs. lange nok) og nøklene ikke faller i fiendens hender så går dette bra. Systemet kalles engangsblokker. Dette fordi hvert ark bare brukes én gang. Dette er svært viktig. Skulle man gjøre feil ved å glemme å rive av, eller rive av flere ark vill den andre parten i samtalen få et alvorlig problem. Han må begynne å gå gjennom de andre nøklene og finne ut hvilken feil du har gjort, og det kan ta tid.
Allikevel regnes systemer med engangsblokker som helt sikre, med unntak av at de kan stjeles, eller brukes feil. Det andre kravet er at nøkkelen må være lang nok. Man kan godt lave en nøkkel som er like lang som teksten, en slik nøkkel vil, i praksis være umulig å knekke.

Allikevel er det noen problemer. I felten, i Frankrike under andre verdenskrig, ble det meste av kryptert telegrafi overvåket og avlyttet. Dette betyr ikke at det ble forstått, det var komplisert og tidkrevende å dekryptere. Allikevel oppdaget noen av de som satt og lyttet at de kjente igjen enkelte av de som sendte morsesignaler, ved at de husket «rytmen» eller «takten» de sendte med. Dette kan, for en telegrafist, være like identifiserende som en signatur i håndskrift. Man kunne kjenne igjen telegrafistens pitch. Dette, sammen med peiling av sendere, kunne gi gode antydninger om hvor en bestemt telegrafist befant seg og hvordan han (og avdelingen hans) flyttet seg i geografien. Skulle man også greie å dekryptere en melding eller to kunne man kanskje også identifisere hvilken avdeling det dreide seg om. Dette var umåtelig viktig.

Kryptanalytikerne, de som knekket koder, vant mange seire under første verdenskrig. Helt siden Vigenèrechifferet ble knekket på nittenhundretallet hadde egentlig kodeknekkerne overtaket. Vigenèrechifferet har en grunnleggende svakhet som amerikanske forskere fant en metode for å utnytte, og samtidig fant de frem til en sterkere kryptering enn noen gang før. Problemet lå i at Vigenèrechifferet er syklisk, det vil komme gjentagelser. Hvis vi tenker oss en klartekstmelding på 1000 bokstaver som er kryptert med en nøkkel på 5 bokstaver må vi til slutt i kryptanalysen foreta en frekvensanalyse på fem sett meldinger, hver på 200 tegn. Dette er overkommelig. Hadde kodeordet (nøkkelen) vært på 20 bokstaver ville vi måtte foreta frekvensanalyse på 20 sett med 50 bokstaver hver. Det er betydelig vanskeligere. Hvis nøkkelordet hadde vært på 1000 bokstaver også, ville det bety at vi måtte frekvensanalysere 1000 sett på én bokstav hver. Det er umulig. Dette betyr at dersom nøkkelordet, eller setningen, er like lang som meldingen vil ikke Babbages frekvensanalyse virke.

Engangsblokkene, dersom nøkkelen var lang nok, ble regnet som helt sikre. Det er viktig at nøklene består av bokstaver (og eventuelt tall og spesialtegn) som kommer i en tilfeldig rekkefølge. Det høres lett ut, men det er ikke egentlig det. Vi skal imidlertid ikke ta den diskusjonen her.

Selv om engangsblokkene, i teorien, er helt sikre er det fremdeles et alvorlig problem. Det gjelder distribusjonen av blokkene / bøkene. Selv om man kunne generere et tilstrekkelig antall nøkler har man et grunnleggende problem og det er et alvorlig problem. Se for deg en slagmark under første verdenskrig med hundrevis av radiooperatører spredt over en betydelig avstand. Alle må ha identiske utgaver av kodebøkene, ellers kan de ikke delta i samarbeidet. Alle må også få nye blokker samtidig, efterhvert som kodebøkene går tomme for ark. Dette må synkroniseres og det er meget vanskelig. Det ville kreve flere kurerer enn soldater og om bare en eneste blokk falt i fiendens hender var alt usikkert. Engangsblokkene har to svakheter; distribusjon og det at de aldri kan brukes to ganger. Da er det mulig å dechiffrere meldingene på grunnlag av hverandre. Man må bruke en ny nøkkel hver gang.
I praksis er nok ikke engangsblokker i bruk så mange steder, og i krig ville det ikke ha nyttet uansett. Bare noen få, som har behov for helt spesiell sikkerhet bruker dette. For eksempel er den «røde linjen», den direkte telefonkontakten mellom presidenten i USA og i Russland kryptert ved hjelp av engangsblokker. En kan nok si at de praktiske svakhetene ved den teoretisk fullkomne engangsblokken betyr at den ikke kan brukes i praksis.

Det neste store spranget i utvikling av kryptografien var utviklingen av de mekaniske chiffermaskinene. Den aller første ble utviklet av den italienske arkitekten Leon Alberti så tidlig som på 1600-tallet. Han lavet to kobberskiver, den ene litt større enn den andre. Så graverte han alfabetet langs kanten på begge og festet dem sammen over hverandre med en nål som virket som en akse. Ved å vri disse i forhold til hverandre fikk han en cæsarforskyvning.
Slike har senere blitt brukt både i krig (den amerikanske borgerkrigen) og av barn som hadde moro med dem. Et typisk eksempel er den amerikanske radioserien om Captain Midnight, en serie som gikk fra ca. 1939 og flere år fremover. Her brukte helten en Code-o-Grapf, i prinsippet akkurat som Albertis cæsarforskyvningsmaskin.

Captain Midnights Code-o-Graph

Captain Midnights programmer sluttet ofte med at helten ga en beskjed til trofaste lyttere, og denne var kodet og kunne bare løses hvis du hadde en Code-o-Graph. Dette var meget populært blandt barn og ungdom og tilsvarende har speidere i alle land drevet med koding av «hemmelige» beskjeder.

Imidlertid var alle disse systemene meget enkle å finne ut av for en profesjonell krypanalytiker.
Det var ikke før utviklingen av Enigma. Det var den tyske oppfinneren Arthur Scherbius som lavet denne. I prinsippet er den det samme som Albertis apparat, men med den store forskjellen at selve krypteringen, forskyvningen, endres fra bokstav til bokstav. Endringene var av en slik art at det ble meget vanskelig å dekryptere meldinger som var kodet med Enigma.
Vi skal ikke gå i detaljer om Enigmas virkemåte, det blir litt mye, men det finnes hundrevis av hjemmesider på Internett som beskriver den i detalj og flere steder hvor det er lavet emulatorer som kan brukes til å kryptere en melding.
Et eksempel er: http://www.ugrad.cs.jhu.edu/~russell/classes/enigma/
Enigma ble knekket til slutt, først av tyskeren Hans-Thilo Schmidt som var en bitter mann hvis bror hadde en fremragende militær karrière. Hans-Thilo ble ikke funnet verdig en stilling i det militære en gang. Broren hadde ansvaret for at Enigma ble tatt i bruk av de tyske styrkene og Hans-Thilo stjal hemmelige dokumenter og solgte dem til en fransk agent med kodenavnet «Rex» i 1931. Han fikk en sum som ville tilsvare ca. 250000 kroner i dag.

Det tok likevel lang tid før noen greide å dechiffrere meldinger kodet med Enigma. De første var polske matematikere, men Enigma ble forbedret og det fantes minst tre utgaver; en kommersiell og en militær pluss den utgaven som ble brukt av den tyske marine. Den siste var den mest avanserte av alle Enigmautgavene.
Det ble til slutt engelskmennene som fikk æren for å knekke Enigma efter et meget stort og langt arbeid i Blechley Park i Buckinghamshire. Blechley Park var et superhemmelig sted hvor matematikere, lingvister, kryssordfanatikere, sjakkmestre og filologer arbeidet tett under andre verdenskrig. Mye av arbeidet som ble utført der er dessverre gått tapt fordi hemmeligholdet var så strengt at mye ble makulert eller brent underveis. Man var paranoide og tanken på at tyskerne skulle invadere England og få tak i hemmeligheter var overveldende.

Det var til slutt Alan Turing som fikk det store gjennombruddet. Han konstruerte «bomben», en maskin som kunne dechiffrere Enigmas koder.

Senere utviklet de tyske myndighetene sterkere chiffer, et av dem var Lorenz-chifferet. Dette var lavet efter samme prinsipp som Enigma, men betydelig mer komplisert. Forskerne i Blechley Park, under ledelse av Max Newman utviklet efterhvert en maskin som kunne tilpasses forskjellige situasjoner, altså en programmerbar kodeknekkermaskin. Denne besto av 1500 vakuumrør. Maskinen fikk navnet Colossus. Den var mye raskere enn «bomben», men det viktigste var at den kunne programmeres. Dette er grunnen til at Colossus regnes som den moderne datamaskinens forløper. Colossus ble dessverre, som det meste i Blechley Park, ødelagt efter krigen. Også konstruksjonstegningene ble brent. Dette ekstreme hemmelighetskremmeriet er årsaken til at andre forskere fikk æren for å ha funnet opp den første datamaskinen, ENIAC (Electronic Numerical Integrator And calculator). Denne ble bygget ved University of Pennsylvania i 1945 og besto av 18000 vakuumrør. Den kunne foreta 5000 beregninger i sekundet.

Nå begynte den nye æra i krypteringen for alvor. Man begynte å ta i bruk elektroniske, fremfor mekaniske krypteringsmaskiner.
Det er tre store forskjeller på mekaniske og elektroniske krypteringsmaskiner.

Den første forskjellen ligger i de praktiske begrensningene i hva som kan bygges med mekaniske releer. En datamaskin kan utføre det samme gjennom emuleringer og modelleringer som de mekaniske. Man kan godt se for seg at en datamaskin kunne gjøre det samme som hundrevis av scramblere, mens det ville være tidkrevende og vanskelig både å bygge og vedlikeholde de mekaniske maskinene.

Den andre forskjellen handler om hastighet. En datamaskin er mye, mye raskere enn en mekanisk maskin.

Den tredje forskjellen er den viktigste. Det er at mens de mekaniske maskinene bytter om på bokstaver, bruker de elektroniske alltid tall. Datamaskiner bruker ikke bokstaver, de bruker binære tall. Dette betyr at bokstavene i en melding som skal krypteres må konverteres til binære tall, lange rekker med bare 1 og 0. det kan brukes ASCII, eller andre kodesystemer, men ASCII er nok mest brukt, sammen med Unicode. Ascii bruker 7 bit i kodingen. Du finner koden på www.asciitable.com.

La oss se på et eksempel: hvis vi vil kode ordet HALLO må vi først gjøre det om til ASCII.
HALLO blir (desimalt) 72 65 76 76 79. Nå gjør vi dette binært. Da får vi:
1001000 1000001 1001100 1001100 1001111. Nå skriver vi dette uten mellomrom mellom bokstavene (vi vet at de har 7 bit hver så det er ikke noe problem).

Nå kan vi stokke om for eksempel ved at første og andre bit bytter plass, og så tredje og fjerde bytter, derefter femte og sjette også videre. Vi ville få følgende:

Klartekst: 10010001000001100110010011001001111

Chiffer: 01100010000010011001100011000110111

Her skjer det noe som er meget interessant. Flyttingen av bit betyr at det ikke bare er bokstavene som bytter plass, men flyttingen skjer også inne i bokstavene. For eksempel kan du se at i syvende og åttende bit bytter den siste 0-en i H plass med den første eneren i A. Dette er et helt nytt konsept. Vi har nå fått en streng av 35 bits som kan sendes til mottageren. Hun kan senere reversere prosessen og få tilbake den egentlige meldingen, konvertere til bokstaver ved hjelp av ASCII tabellen og lese meldingen. Hvis noen avlytter og snapper opp den krypterte (transposisjonerte) meldingen vil det være meget vanskelig å finne ut av den hvis du ikke vet hvilket mønster, eller system, som ble brukt for å stokke om på bitsene.

La oss tenke oss at vi vil kryptere den samme meldingen; HALLO, med et dataprogram. Vi begynner også denne gangen med å konvertere til ASCII. Denne gangen skal vi basere krypteringen på et nøkkelord som er avtalt på forhånd mellom avsender og mottager. Nøkkelordet er DAVID.

Vi konverterer også DAVID til ASCII og bruker nøkkelordet slik (her gjelder det å følge med):
Hvert element (hver enkelt bit) i klarteksten blir addert til til den tilsvarende biten i i nøkkelordet. Det å addere binære tall er ikke vanskelig, det kan beskrives med to enkle regler. Det som er virkelig viktig å «se» her er at dersom addisjonen gir en mente så blir menten forkastet, ikke transportert til neste bit. Det betyr at 1 + 1 = 0 og 0 + 0 = 0, mens 1 + 0 = 1 og 0 + 1 = 1. Altså, hvis biten i klartekst og tilsvarende bit i nøkkelen er like, blir svaret 0, hvis de er ulike blir svaret 1. Det kan fort se ut som om dette er en logisk operasjon av typen AND, OR eller XOR, men se nøyere efter, så ser du at det ikke stemmer. det er addisjon, men som sagt, uten å ta hensyn til mente.

La oss se i praksis:

Melding: HALLO

Melding i ASCII: 10010001000001100110010011001001111

Nøkkel = DAVID 10001001000001101011010010011000100

Kryptert melding: 00011000000000001101000001010001011

Mottageren av meldingen reverserer nå prosessen og får en ny streng med 1 og 0 som deles opp i blokker av 7 og 7 bits før disse konverteres tilbake til ASCII tegn. Prøv selv å følge det samme systemet, men start nedenfra og adder chifferteksten med nøkkelen og se selv at du får klarteksten tilbake. Her sier det seg selv at du må vite hva nøkkelordet er for å få dette til. Husk; du får bare den krypterte strengen, ikke alle tre!

Verdens største snushaner.

Verdens største snushane er den amerikanske organisasjonen National Security Agency (NSA). De har ansvaret for å opprettholde sikkerheten i kommunikasjon i forsvaret og regjeringen, samt å avlytte og dechiffrere meldinger fra andre stater. Det er ingen i verden som har ansatt så mange matematikere, ingen kjøper mer og kraftigere datautstyr, ingen avlytter og snapper opp så mange meldinger både pr. radio og Internett enn NSA. De ligger også fremst i verden med hensyn til krypteringsteknikk og kryptanalyse. Kort sagt; verdens største og mest paranoide snushane!

Eftersom datamaskiner ble kraftigere, billigere og mer tilgjengelige ble NSA mer og mer paranoide. Det utviklet seg mange forskjellige systemer for kryptering, og NSA var redde for å miste kontrollen, samtidig som de så problemet med at disse systemene ikke var kompatible.
Det ble efterhvert tydelig at man hadde behov for en standardisering av krypteringssystemene. Det er ikke noe poeng i å ha hemmelige, sære systemer, det eneste som er viktig er at krypteringen er sterk nok, les tilstrekkelig mange mulige nøkler, og at nøklene holdes hemmelige. I 1973 kom det et forslag fra National Bureau of Standards om å finne en standard krypteringsmetode. Det var mange systemer i bruk og et av de som var mye brukt var et system utviklet av IBM, kalt Lucifer. dette systemet krypterer meldinger slik: først blir meldingen konvertert til en lang streng med bits, slik vi gjorde ovenfor. Derefter blir denne strengen delt opp i blokker på 64 bit slik at disse kan krypteres hver for seg. Hver slik blokk blir stokket om, og delt i to nye blokker på 32 bit hver. Hver av disse blir utsatt for en substitusjonsformel, igjen som over, men mer komplisert. Efterpå blir de to blokkene på 32 bit addert. dette gjøres flere ganger, til sammen 16 ganger. Detaljene i prosessen styres av en nøkkel som avsender og mottager avtaler.
NSA likte tanken bak Lucifer, men var oppriktig redde for at de ikke skulle kunne dekryptere meldinger de snappet opp selv og derved miste masse informasjon. Skal man forsøke å dekryptere en slik melding kan man gjøre det ved å gå gjennom alle mulige nøkler. Dersom det er for eksempel en million mulige nøkler ville det ta lang tid å gjøre det manuelt, men med en datamaskin ville det kunne gjøres på noen minutter. Dette er selvfølgelig ikke bra nok og antall nøkler må derfor være betydelig større. NSA mente at antall mulige nøkler ble begrenset til 100 000 000 000 000 000 eller 100 billiarder. Dette kaller man en 56-bits kryptering fordi 100 billiarder er 56 bit dersom du skriver det binært. De trodde nok at dette ville være sterkt nok for næringslivet, men så for seg at de selv, og ingen andre enn dem kunne dekryptere dette allikevel. De hadde tross alt verdens sterkeste datamaskiner.

Denne krypteringen kalles Data Encryption Standard (DES) og er i bruk fremdeles.

Et problem besto fremdeles. Nøklene måtte holdes hemmelige og de måtte sendes til den andre parten i «samtalen» før meldingene kunne dekrypteres. Det var vanlig å bruke kurerer til dette og bankene hadde spesielt betrodde medarbeidere som reiste verden rundt med nøkler de skulle levere til andre banker eller viktige kunder.
Når man ser på agentfilmer ser vi av og til en person med en låst koffert som er lenket til håndleddet med håndjern. Vanligvis var det ikke hemmelige dokumenter, men krypteringsnøkler som lå i disse koffertene. Dette er ikke bare film, det var og er helt reelt, selv om det ikke er mye brukt lenger. Systemet var sårbart, og ikke minst svært dyrt og tildels farlig.
Noen måtte finne en måte å distribuere nøkler som ikke var så tungvindt, farlig og dyrt.
Det kom en løsning efterhvert, og denne løsningen skulle vise seg å bli det største kryptografiske gjennombrudd på på to tusen år.

Whitfield Diffie

Whitfield Diffie (født i 1944) er en av vår tids mest fremragende kryptografer. Han er en underlig person med langt hår og skjegg, en tydelig efterlevning fra hippietiden, men samtidig går han nesten alltid i dress og slips. Litt selvmotsigende kanskje? Han arbeider i dag for Sun Microsystems og har tittel Distinguished Engineer. Whitfield tenkte mye på distribusjon av nøkler og en av årsakene var at han var fremsynt nok til å forstå at ARPANET som dengang var ganske nytt ville komme til å skape en informasjonsteknologisk motorvei og han så for seg elektronisk handel. Han forsto raskt at for å kunne kryptere handel (det er nødvendig for at kredittkortnumre ikke skal kunne avlyttes) måtte man finne en løsning på nøkkeldistribusjonen. Det ville være umulig å sende en kurer med nøkkelen til enhver kunde. Han tenkte og tenkte, men heller ikke han fant på noe før han en dag fikk en aldeles genial ide. Han fant en teoretisk måte å gjøre dette på. Hvis man tenker seg at Alice vil sende Bob et kjærlighetsbrev som hun ikke vil at noen skal se, spesielt ikke postbudet Eve. Eve er nemlig sjalu på Alice og Bob. Whitfield tenkte at Alice kunne låse brevet inn i en stålboks med en hengelås som holder lokket igjen. Så kan gjerne Eve få overbringe boksen, men hun får ikke sett inneholde fordi hun ikke har nøkkelen. Det var imidlertid et problem. Bob hadde heller ikke nøkkel til skrinet. Hvis nå Alice gir Bob en kopi av nøkkelen er alt greit, men hvis Bob bor langt unna er det vanskelig. Kanskje hun må sende nøkkelen i posten også. Da kan hun risikere at postbudet Eve får tak i den, laver en kopi og senere kan lese meldinger Alice sender til Bob i det låste skrinet, uten at noen oppdager dette. Heller ikke Bob vil kunne oppdage at skrinet har vært åpnet og så låst igjen. Hvordan skulle Alice få sendt nøkkelen til Bob? Det var her det geniale dukket opp. Hvis nå Alice ikke sender nøkkelen, men beholder den selv, er den trygg bortsett fra at Bob ikke får åpnet skrinet og lest meldingen. Men, hva om Bob, når han får skrinet henger på en hengelås til? En som bare han har nøkkelen til? Så sender Bob skrinet tilbake til Alice som nå låser opp og fjerner sin egen hengelås før hun sender skrinet tilbake til Bob. Nå kan Bob åpne skrinet når det kommer fem, uten at Eve har hatt mulighet til å få tak i hverken nøkkel eller innhold. Dette høres egentlig både enkelt og lett ut, men det var ingen som hadde tenkt på dette før. Allikevel hadde Whitfield nå bevist at det var teoretisk mulig å sende en melding uten at du behøvde å distribuere nøkler. Voilà! Et fantastisk gjennombrudd. Diffie ble kjent med en annen kryptograf, Martin Hellman som var professor ved Stanford University i California. Han tente på ideen og deres samarbeid skulle komme til å bli et av de viktigste i kryptografiens historie. Alle forsto jo at dette med skrinet bare var en analogi, det var jo tross alt binære tall som ble sendt. Situasjonen var en klassisk Catch-22 situasjon. I kryptografisk litteratur er det vanlig å lave eksempler og det er vanlig å bruke Alice og Bob som vil kommunisere og Eve som er en ondskapsfull person som forsøker å avlytte. Personlig antar jeg at valget av Alice og Bob er for å ha en A og en B, mens Eve kan komme av evil, eller evesdropping som betyr å lytte, men jeg vet ikke sikkert. I alle fall er det svært vanlig å bruke disse navnene i eksempler og jeg har valgt å følge tradisjonen her. Problemet er at hvis Alice og Bob skal utveksle en hemmelig melding over telefonen må Alice kryptere meldingen. For at Bob skal forstå den må han ha en nøkkel. Nøkkelen må være hemmelig og kan derfor ikke sendes over telefon, ingen vet hvor Eve er eller hva hun holder på med. Kort sagt, før Alice og Bob kan utveksle en hemmelighet må de allerede ha utvekslet en hemmelighet, nemlig nøkkelen. De var nødt til å finne en matematisk modell, en algoritme isteden for det låste skrinet, men hvordan? Hvis vi tenker oss at Alice krypterer en melding, sender den til Bob som så krypterer den med sin egen nøkkel og sender den så tilbake til Alice. Alice dekrypterer med sin egen nøkkel og sender meldingen til Bob som nå kan dekryptere den med sin nøkkel ville dette gå greit, men dessverre slik er det ikke. Det er en fundamental forskjell mellom krypteringsnøkler og hengelåser. I det siste tilfellet spiller det ingen rolle hvor mange hengelåser det er på skrinet. Det kan godt være 100, og så snart du har låst opp alle sammen kan du åpne skrinet. Slik er det ikke med den matematiske krypteringen. Man er avhengig av rekkefølgen. hvis Bob krypterer en melding fra Alice som allerede er kryptert vil ikke Alice greie å fjerne «sin egen kryptering», hun vil sitte igjen med bare tøv. Vi er altså 100 % avhengig at disse krypteringene gjøres i motsatt rekkefølge for å dekryptere, vi kan ikke endre rekkefølgen. Regelen er enkel, men det er påbudt å følge den: siste kryptering må dekrypteres først også videre.
Selv om dette tankeeksperimentet med hengelåsene ikke ville virke i den egentlige verden var det likevel en inspirasjon for Hellman og Diffie. De begynte å undersøke forskjellige matematiske metoder for å få til noe som kunne ligne på hengelåssystemet. I matematikken er en funksjon noe som endrer et tall slik at det blir et annet tall. Det å fordoble (multiplisere med 2) er et eksempel på en enkel funksjon. Vi kan gjøre 5 om til 10, eller 8 om til 16. I begge tilfellene har vi doblet tallet. Dette er en funksjon. På samme måte vil man kunne si at alle typer kryptering med binære tall og datamaskiner er en funksjon, de gjør et tall (klarteksten) om til et annet tall (chifferteksten), og det er egentlig ikke mer enn det som skjer, selv om disse funksjonene er mye mer kompliserte enn en fordobling. Allikevel er det funksjoner.

De fleste matematiske funksjoner kalles to-veis funksjoner fordi de kan regnes «baklengs» også. Hvis vi fordobler et tall, kan vi finne tilbake til det opprinnelige tallet ved å halvere det tallet som er resultatet av fordoblingsfunksjonen. Funksjonen kan reverseres, sier vi.

Det finnes også en type funksjoner som ikke kan (eller er meget vanskelig) reverseres. Slike funksjoner kaller vi en-veis funksjoner. Det var slike funksjoner Diffie og Hellman var på jakt efter. Hvis vi tenker på en toveisfunksjon som noe som kan reverseres kan vi ta et eksempel fra det daglige liv. Hvis vi skrur på lyset er det en toveisfunksjon, det er lett å skru på bryteren og forvandle en mørk pære til en lysende pære. Hvis du skrur av strømmen har du reversert funksjonen og gjort pæren mørk igjen.
I en enveisfunksjon er dette ikke mulig. For å ta et nytt eksempel fra det daglige liv kan vi tenke oss at vi blander gul og blå oljemaling og får grønn maling. Det er relativt enkelt, men prøv å reversere den funksjonen! Du klarer ikke å skille ut blå maling fra den grønne og så sitte igjen med gul maling. Det går ganske enkelt ikke. Dette er en enveisfunksjon. Slike funksjoner, enveisfunksjoner kalles ofte for Humpty Dumpty funksjoner. Humpty Dumpty er det engelske navnet på Lille Trille, og vi vet alle hvordan det gikk med ham...

Det finnes en spesiell form for matematikk som kalles modulær matematikk. Denne formen for matematikk har en rekke eksempler på enveisfunksjoner. (se appendixet Modulær matematikk, som er et tillegg til dette kompendiet for de som ikke har vært borti dette før.)

Vi skal, kort, se på hvordan og hvorfor vi kan få til matematiske enveisfunksjoner ved bruk av modulærmatematikk. Det er nok noen av dere som ikke er veldig godt kjent med denne typen matematikk, men vi bruker den hver dag alle sammen. Vi bruker dette når vi snakker om tid. Det er vel ikke helt uvanlig at vi begynner på jobb klokken 9og går hjem efter 8 timer og da er kokken 5. Det vil jo egentlig si at vi regner at 9 + 8 = 5. matematisk kan vi si at 9 + 8 = 5 (mod 12) fordi vi regner med en klokke som har tolv timer. Vi kunne regnet med en 24 timers klokke også, isåfall ville 9 + 8 = 17 eller 9 + 8 = 17 (mod 24). I dette tilfeller «ser» vi ikke noe rart og forholder oss ikke til mod i det hele tatt, men la oss si at vi arbeider på nattklubb og møter på arbeid klokken 21. Derefter arbeider vi i 8 timer og går hjem klokken 5 om morgenen. Da er 21 + 8 = 5 (mod 24).

I matematikken er det en litt enklere måte å regne på enn å sitte og telle på urskiver. Man kan først bruke vanlig aritmetikk og hvis du vil ha dette i en eller annen mod (mod x) dividerer vi det «vanlige» resultatet med x og ser på hva som blir til rest i divisjonen. Ikke vær for rask og bruk kalkulatoren din ukritisk, desimalen i et divisjonstykke er ikke det samme som en rest. La oss si at vi regner ut: 9 x 11 (mod 13). Da kan vi gjøre som følger: 9 x 11 = 99. 99 / 13 = 7 (rest 8). Det vil si at 99 x 11 = 8 (mod 13). Hvis du bruker kalkulatoren ukritisk vil du få feil svar. (99/13 vil bli 7,6). Se appendixet modulær matematikk for flere eksempler og en nøyere gjennomgang av dette konseptet.

Tilbake til saken...

Våren 1976 fikk Hellman endelig et skikkelig gjennombrudd. Han fant endelig en metode hvor Alice og Bob kunne utveksle nøkler uten å møtes. Han satte opp en funksjon (lik den vi har sett på i appendixet om modulær matematikk) hvor han velger: Y^x (mod P), en fin enveisfunksjon. Alice og Bob blir enige om verdier for Y og P, og de kan bruke omtrent hva som helst, men noen få krav må oppfylles. Y må være mindre enn P. Disse verdiene trenger ikke å være hemmelige så Alice kan ringe til Bob og si hva de skal være, eller for den saks skyld annonsere dem i avisen. Alice kan for eksempel foreslå at Y = 7 og P = 11. Selv om Eve skulle få vite disse verdiene skal vi se at det går an å lave en hemmelig nøkkel uten at Eve klarer å gjette den. Alice og Bob har faktisk avtalt en enveisfunksjon, nemlig 7^x (mod 11). Nå kan de begynne å tenke på en hemmelig nøkkel og vi skal se på hvordan de gjør dette, trinn for trinn. Ved å følge disse trinnene nøye vil du også kunne se dette. Allikevel er det viktig å huske på at dette eksemplet er forenklet, i virkeligheten ville Alice og Bob brukt betydelig større tall. Jo større tall, jo bedre kryptering. Dette er enveisfunksjoner og så lenge tallene er relativt små lar de seg løse, men hvis tallene blir enorme er det, i praksis, umulig å løse dem.

Hva nå med Eve? Hvorfor klarer ikke Eve å regne seg frem til nøkkelen? Hun har jo funksjonen 7^X(mod11), og verdiene av α og β. Hun mangler en essensiell del, hun mangler verdiene av A og B. Disse verdiene har Alice og Bob holdt hemmelige. Dermed står hun fast. Man kan tenke seg at hun kan finne A på grunnlag av α fordi α er resultatet av at A er satt inn i en funksjon hun kjenner, eller gjøre det samme med B på grunnlag av β. Problemet hennes er at dette er modulære enveisfunksjoner. Det er lett for Alice å gjøre A om til α og det er lett for Bob å gjøre B om til β, men det er så godt som helt umulig for Eve å gjøre dette baklengs, spesielt hvis tallene er virkelig store.

Alice og Bob har sagt akkurat nok til hverandre til at de kan etablere en nøkkel, men ikke nok til at Eve kan regne seg frem til denne nøkkelen.

Hvis vi skulle forsøke å trekke en parallell til noe fra dagliglivet igjen, kan vi bruke farver enda en gang. Vi går ut fra at alle, det vil si Alice, Bob og Eve har en tre liters boks med en liter gul maling. Hvis Alice og Bob skal finne frem til en nøkkel, tilsetter de begge en liter av en egen, hemmelig blanding som har en annen farve enn gul. La oss si at Alice tilsetter purpur og Bob tilsetter karmosinrødt. Nå sender de boksene til hverandre. Til slutt tilsetter Alice en liter av sin egen hemmelige farve og Bob tilsetter en liter av sin hemmelige farve i boksen han fikk av Alice. Nå vil begge disse boksene inneholde samme farveblanding selv om hverken Alice eller Bob vet hva den andre tilsatte. Det er denne farven som er en blanding av tre farver som brukes som brukes som nøkkel. Hva med Eve? Hun kan godt få lov til å se i boksene som blir sendt mellom Alice og Bob, det hjelper ikke for hun vet ikke hva som er tilsatt av hemmelig farve. Selv om hun tar en liten prøve av hver av disse boksene kommer hun ikke lenger, fordi det å blande maling er en enveisfunksjon og hun har ingen mulighet for å skille dem fra hverandre igjen.

Det eneste som er litt guffent med denne metoden er at Alice og Bob må utveksle α og β, og det kan ta litt tid hvis de ikke har tilgang til telefon eller et annet raskt kommunikasjonssystem. Det ville være ønskelig å finne en raskere måte. Det skulle bli Whitfield Diffie som fikk det neste store gjennombruddet. Han klekket ut en genial ide, en helt ny chiffertype, en såkalt asymmetrisk nøkkel. Hittil har det vi har sett på vært symmetrisk kryptering. Det vil si at vi har en funksjon som krypterer og vi kjører den samme funksjonen baklengs når vi dekrypterer. Dekryptering er altså det motsatte av krypteringen. Man bruker altså samme nøkkel for kryptering og dekryptering. Det er symmetrisk. I et asymmetrisk system er det anderledes. Man bruker en nøkkel for å kryptere og en annen nøkkel for å dekryptere. I et asymmetrisk krypteringsystem kan Alice kryptere en melding hvis hun kjenner krypteringsnøkkelen, men hun kan ikke dekryptere meldingen igjen. Da må hun ha en annen nøkkel. En dekrypteringsnøkkel som er anderledes enn krypteringsnøkkelen. Dette er meget spesielt. I praksis vil det være slik at man bruker datamaskiner til krypteringen og da blir det slik at krypteringsnøkkelen egentlig er et tall og dekrypteringsnøkkelen er et annet tall. Det vil være helt nødvendig for Alice å holde dekrypteringsnøkkelen hemmelig. Vi kaller den hennes private nøkkel. Imidlertid kan hun uten videre gi fra seg krypteringsnøkkelen. Den kan hun gjerne avertere i avisen eller legge ut på Internett. Hvis Bob vil sende en hemmelig melding til Alice bruker han hennes offentlige nøkkel, og kryptere meldingen med den. Nå kan bare Alice dekryptere fordi hun er den eneste som kjenner dekrypteringsnøkkelen, hennes private nøkkel. Han kan finne denne i et offentlig register over offentlige nøkler, slike registre finner man på Internett. Et eksempel på et slikt register er http://keys.pgp.com. Slå opp adressen selv!
Den store fordelen her er at man ikke trenger å utveksle noen informasjon før man kan kryptere og sende meldingen. Man kan bare slå den opp i en katalogtjeneste. Det snåle her er at selv Bob som har kryptert meldingen kan ikke dekryptere den igjen, det er det bare Alice som kan fordi hun er den eneste som har dekrypteringsnøkkelen, den private nøkkelen. Nå har vi kommet meget langt, det er ikke lenger nødvendig å bruke enorme ressurser på å utveksle nøkler og ingen fare for at noen skal greie å plukke opp nøkkelen ved å bestikke en kurer, eller avlytte en telefonsamtale, kopiere e-post fra Internett eller lignende. For å sammenligne med boksen med hengelåser som vi så på tidligere kan man tenke seg at den som krypterer setter på en hengelås som bare mottageren har nøkkelen til, og smekker den bare i lås. Nå er det bare eieren, som har nøkkelen, som kan åpne låsen.

Diffie hadde denne geniale ideen og han offentliggjorde den i 1975. Problemet hans var at han hadde ingen matematisk funksjon som virket slik at man kunne kryptere og dekryptere med forskjellige nøkler. Dette problemet var det mange matematikere som kastet seg over og man begynte forskningen for å finne frem til en slik funksjon.

Det skulle bli en forskertrio fra den amerikanske østkysten som fant løsningen. Disse herrene het Ronald Rivest, Adi Shamir og Leonard Adleman. Systemet de lavet ble kjent som RSA, og er uten tvil det viktigste chiffer i moderne kryptografi. Chifferets virkemåte er beskrevet i siste del av dette dokumentet. Vi skal derfor ikke gå i detalj her, men en liten del skal vi se på, nemlig den delen man vanligvis kaller N, og det er hvordan Alice kan skaffe seg en offentlig nøkkel.

N er en verdi alle kan velge selv og den er fleksibel i så måte. Ved at man kan velge den selv, skaper man sin egen private enveisfunksjon. Når Alice vil skape sin N velger hun to primtall, p og q. Et primtall er et tall som bare kan deles på seg selv og på 1. For eksempel er 5 og 7 primtall, de kan bare deles på seg selv hvis svaret skal gå opp og det kan ikke være noen rest. 8 og 9 er ikke primtall, 8 kan deles på 1, 2, 4 og 8, og 9 kan deles på 1, 3 og 9. Alice bør velge to veldig store primtall for p og q. La oss si at hun velger p = 17159 og q = 10247.
Når hun multipliserer disse får hun N = 175828273. Dette er Alices offentlige nøkkel og den kan settes inn i en kjent krypteringsfunksjon. Dette kan hvem som helst gjøre og dermed kryptere en melding de ønsker å sende til Alice. Tallet kan hun offentliggjøre på flere måter, det vanligste er å bruke en såkalt key-server. Se link ovenfor.

Dette betyr at Alice nå har en offentlig nøkkel og hvem som helst kan lave en sikker kryptert melding. Enveisfunksjonen som brukes (hvor man setter inn N) er per definisjon meget vanskelig å finne ut av. Allikevel er det et problem. Hvordan kan Alice dekryptere denne meldingen når ikke engang den som krypterte den kan dekryptere ved å reversere prosessen? Svaret ligger i at bare Alice vet verdiene av p og q. En skulle tro at alle kunne regne seg frem til hva p og q er, det er jo slik at hvis du ganger dem med hverandre får du N. Det viser seg at dersom N er tilstrekkelig stor er det helt umulig å finne p og q. Her er det det faktum at p og q er primtall som gjør det vanskelig eller umulig. Hvis jeg multipliserer to relativt små primtall, for eksempel 9419 og 1933 med hverandre får jeg 18206927. Det tok noen få sekunder å gjøre det med en kalkulator. På den annen side; hvis jeg hadde sagt at jeg har multiplisert to tall og fått 18206927 og så gitt deg kalkulatoren og bedt deg finne hvilke tall jeg har multiplisert for å få dette resultatet ville du bli sittende resten av dagen før du finner svaret.

La oss tenke oss at Alice vil sende en melding til Bob og slår opp Bobs offentlige nøkkel og den er 408508091. For å finne dette tallet har Bob valgt seg sin egen p og sin egen q. Hvis Alice krypterer med denne nøkkelen og sender meldingen over telefon eller Internett kan vi tenke oss at Eve snapper den opp. Hvis Eve vil dekryptere må hun klare å finne ut Bobs p og q. Altså hvilke tall som multiplisert med hverandre gir 408508091. Dette kalles faktorisering i matematikken. Faktorisering er ikke voldsomt vanskelig, men det er meget tidkrevende. Spørsmålet nå blir hvor lang tid det vil ta for Eve å finne frem til de to faktorene som utgjør 408508091. Det finnes flere metoder for å faktorisere, noen er litt raskere enn andre, men alle er tidkrevende så det holder. Alle metodene må i bunn og grunn teste alle primtall for å se om de går opp i 408508091. For eksempel er 3 et primtall, men det er ikke en faktor i 408508091. Det går ikke opp. Derfor må Eve teste neste primtall i rekken og det er 5. Det går heller ikke opp og Eve må fortsette. Efter en god stund kommer Eve til primtallet 18313 som er primtall nummer 2000 i rekken. Dette er faktisk en faktor i 408508091. Så snart hun har det ene tallet er det enkelt å finne det andre og det viser seg å være 22307. Hvis Eve hadde brukt en vanlig kalkulator og klart å kontrollere 4 primtall i minuttet ville det tatt 500 minutter, eller mer enn 8 timer. Det er greit og overkommelig og Eve kan dekryptere og lese meldingen. Hvis Bob hadde valgt et mye større tall ville det tatt mye lenger tid. Det er ganske innlysende. La oss si at han velger et tall i størrelsesorden 10⁶⁵ for p og det samme for q, altså 1 med 65 nuller efter seg. Det er et hundre tusen millioner millioner millioner millioner millioner millioner millioner millioner millioner millioner millioner. Det vil gi Bob en N som er i størrelsesorden 10¹³⁰. Med en enkel datamaskin ville det fort ta 50 år å faktorisere et tall så stort som 10¹³⁰. For å ha skikkelig sikkerhet må tallene være mye større enn dette. Til banktransaksjoner i våre dager brukes det en N i størrelsesorden 10³⁰⁸. Det er ti millioner milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder milliarder ganger større enn 10¹³⁰. Om du kunne bruke alle datamaskiner i hele verden ville det ta mer enn 1000 år å finne faktorene. Nå begynner det å bli svært tøft, eller i praksis umulig for Eve å dekryptere. Det eneste som kan true sikkerheten i et RSA chiffer er derfor at noen en gang vil finne en rask metode for å faktorisere. Det er tenkelig, men matematikere har forsøkt å finne en slik metode i over 2000 år, og ikke kommet noen vei. Det kan hende det finnes en hittil ukjent metode, men det kan også hende at det ikke gjør det. Skulle noen finne den er RSA chifferet ubrukelig. Foreløbig er det sikkert.

Er alt helt greit nå?

Dette med sikker kryptering utført ved hjelp av datamaskiner er et fantastisk system for myndigheter, militære, banker og andre forretninger akkurat som det er for vanlige mennesker som ønsker å ha privatlivet i fred. Dessverre er det slik at dette også gjelder forbrytere og terrorister såvel som fiender i en krig. Dette er ikke bare ukomplisert, det er farlig. Det kan være så trivielt som at man kryptere bilder (bilder er også tall når de er lagret på en harddisk), og derved kunne spre barneporno fritt og uforstyrret til å avtale et nytt 11. september angrep, eller terroranslaget i Madrid i mars 2004. Myndigheter i mange land har sett dette som et alvorlig problem og lavet restriksjoner slik at sterk kryptering ikke skal være tilgjengelig for menigmann. Det har vært mange gode grunner til dette, noen er virkelig gode, andre er paranoide. Under den kalde krigen gikk mange lands myndigheter nesten amok og det ble lagt strenge restriksjoner på distribusjon av programvare som kan benyttes til sterk kryptering. Eksempelvis bruker politiet telefonavlytting for å avsløre terrorister og narkotikasmuglere. Hvis disse hadde brukt sterk kryptering ville telefonavlytting vært verdiløst for myndigheter. Derfor har sterk kryptering i mange år vært ulovlig for vanlige mennesker og forbeholdt myndigheter og militære. Om dette er riktig eller galt er et politisk spørsmål.

I dag er det tilgjengelig for alle, takket være amerikaneren Phil Zimmerman. Han var fysiker ved Florida Atlantic University og senere ingeniør i dataindustrien. På 80-tallet ble han opptatt av faren for atomkrig i verden og han fikk blod på tann da USA invaderte Afganistan. Han var politisk aktiv og ble arrestert i testområdene i Nevada sammen med Carl Sagan og hundrevis av andre demonstranter. Det han efterhvert ble klar over og opptatt av var at overvåkning av kommunikasjon var blitt betydelig lettere i dataalderen enn tidligere. For eksempel måtte myndighetene tidligere dampe opp konvolutter, kopiere innholdet, lime dem igjen og sende dem til adressaten for å skaffe seg informasjon. Det var også problematisk å avlytte telefoner, man måtte ut på sentralene og koble til avlyttingsutstyr, skifte bånd i båndopptager også videre. I datakommunikasjon er dette mye enklere. Man kan bruke maskiner som scanner all e-post og leter efter bestemte stikkord som «bombe», «hellig krig» og lignende og de facto avlytte tusenvis av e-post kontinuerlig. Man kan sammenligne dette med forskjellen på å fiske med fiskestang og en moderne trålfisker. Det er enorme forskjeller. Zimmermann likte ikke trålfiskernes digitale motpart. Han bestemte seg for å lave et program for kryptering og i 1991 fikk han en venn til å legge det ut på Usenet. Usenet er den delen av Internett hvor newsgrupper holder til. Programmet hans het Pretty Good Privacy (PGP). Den direkte foranledningen til at han valgte å legge debut i 1991 var et lovforslag fra amerikanske myndigheter hvor det blandt annet het: «Det er kongressens mening at leverandører av elektroniske kommunikasjonstjenester og produsenter av utstyr for elektronisk kommunikasjon skal sikre at kommunikasjonssystemene tillater myndighetene å skaffe seg klartekstinnholdet i stemme-, data- og annen kommunikasjon når loven krever det.» Zimmerman fikk mange problemer og ble efterforsket av amerikanske myndigheter (FBI). Allikevel var Pandoras eske nå åpnet og det var i praksis ingen vei tilbake. På grunn av patentrettigheter og amerikansk lovgivning finnes PGP i to varianter: PGP for det amerikanske markedet og PGPI (I for international) for andre land. Du kan selv laste ned PGP og PGPI fra Internett. Et søk på disse ordene vil raskt gi deg link til www.pgp.com og
www.pgpi.org. Du kan selv laste ned og prøve programmene. Husk at hvis du velger å kryptere data på en harddisk, og glemmer hva den private nøkkelen din er, vel da får ikke hverken du eller noen andre tak i det igjen...

Hva vil fremtiden bringe?

Det er vanskelig å spå, spesielt hvis man må spå om fremtiden. Ingen vet hva som kommer, men vi kan gjøre oss noen tanker.

Kappløpet mellom kodemakere og kodeknekkere har vart lenge og det er fullt mulig at kodeskrivernes forsprang vil bli tatt igjen av kodeknekkerne. Det avhenger, som sagt, av om hvorvidt noen greier å finne en metode for å faktorisere tall raskere og enklere enn i dag. Per i dag, er det mulig å lave kryptografiske systemer ved hjelp av PGP som er så sterke at om du bruker alle datamaskiner i verden (anslått til 260 millioner i år 2000) ville det ta omtrent 1,2 millioner ganger universets alder å knekke dem. Erfaringen tilsier at alle tidligere, såkalte uknekkelige koder, er blitt knekket. Vigenèrechifferet ble kalt « le chiffre indéchiffreable», men Babbage knakk det. Enigma ble regnet som usårbar, til polske forskere såret den. Det kan se umulig ut å lave et fullstendig ubrytelig chiffer. Allikevel er det kodemakere som arbeider for å finne bedre systemer. I alle fall i teorien er et slik system funnet. Det kalles: kvantekryptografi. Dette er et teoretisk system (foreløbig), som har en iboende egenskap som gjør det absolutt 100 % sikkert og ubrytelig.

Dette er et meget stort tema og vi skal la fremtiden ligge for nå.

Det er ikke umulig at det kommer et kompendium om kvantekryptografi og kvantedatamaskiner, men som sagt det er vanskelig å spå, særlig om fremtiden. ;-)

Modulær matematikk.

Svar på oppgavene finner du mot slutten av dokumentet.

Hva er modulærmatematikk?

Modulær matematikk ligner mye på divisjon (deling). Tenk på divisjon. Kan alle tall deles likt? Nei, det kan de ikke. Hva skjer hvis to tall ikke kan deles likt? Det blir igjen en rest. For eksempel, 9 delt på 4 blir 2 med 1 til rest. Modulær matematikk bruker denne resten. Se på regnestykket èn gang til. Tallet vi skal dele er 9 og 4-tallet kan vi kalle mod. Mod er det tallet vi deler på (divisor). Hva blir så 9 mod 4? Svaret er resten vi sitter igjen med, i dette tilfellet1.

9 / 4 = 2 r1 (betyr: 9 delt på 4 = 2 rest 1)

Her er det meget viktig å være klar over ar rest ikke er det samme som desimal. Hvis du tar en kalkulator (eller bruker hodet) og fortsetter regnestykket slik at du får desimaler blir svaret på
9 / 4 = 2.25 og det er jo et annet svar. Ikke gå i fellen og tro at rest og desimal er det samme, da får du ikke til noe av dette. Hold tungen rett i munnen :-).

Finnes det en enklere metode?

Det finnes faktisk en noe lettere måte å tenke på modulær matematikk. Modulær matematikk er som å se på klokken og beregne tiden. Hva er klokken tre timer efter at den er 11? Den er 2! Hvorfor er det vanlig å si 2 isteden for 14? (Begge deler er korrekt). De fleste sier 2 fordi de er vant til å telle rundt en urskive som har tolv timer og gå fra 11 til 12 til 1 til 2. Dermed har vi telt 3 timer inn i fremtiden. Dette er nokså likt modulær matematikk. Ta et stykke papir og tegn en sirkel. Tegn inn tidene på urskiven, men erstatt 12 med 0. Urskiven går da fra 0 til 11 og har totalt 12 inndelinger. Sett fingeren din på 0 og tell med klokken 14 tall fremover. Hvor stanset du? Du burde ha endt opp på 2. Hvilken mod er denne klokken? Mod er antall siffer på urskiven, det vil si 12 i dette tilfellet (husk å telle med 0). Hva blir 14 i mod 12? Det blir 14 / 12 = 1 r 2 (fjorten delt på 12 = 1 rest 2).

14 mod 12 = 2

Hvorfor bruker vi 0 isteden for 12?

Tenk på hva som skjer hvis vi deler på 12. Hvilke rest er mulige når vi deler på 12? 12 delt på 12 gir en rest på 0. 13 delt på 12 gir en rest på 1. 14 delt på 12 gir en rest på 2. Finnes det noen tall som vil gi en rest på 12? Nei, det finnes ikke. Hvorfor ikke? Fordi 12 delt på 12 er 1 med rest 0. Dette er årsaken til at vi bruker 0 isteden for 12.

12 / 12 = 1 r 0
13 / 12 = 1 r 1
14 / 12 = 1 r 2
15 / 12 = 1 r 3
16 / 12 = 1 r 4
17 / 12 = 1 r 5
18 / 12 = 1 r 6
19 / 12 = 1 r 7
20 / 12 = 1 r 8
21 / 12 = 1 r 9
22 / 12 = 1 r 10
23 / 12 = 1 r 11
24 / 12 = 2 r 0

Klokken...

Hvor mange er klokken når det er gått 4 timer efter klokken 9? Den er 1. Hvordan kom vi frem til det? Se på en urskive (tegn en om du vil). Start på 9 og tell 4 timer fremover. Hvor endte du opp? Du burde endt på 1. Dette kan vi kalle å telle på klokken, eller å telle i modus. Din modus eller mod er hvor mange tall du har på urskiven. Hvis du spør deg selv hvilken mod en vanlig klokke er vil svaret helt sikkert bli at de er mod 12. Her er det en forskjell mellom en klokke og mod. Når vi regner i mod og bruker mod 12, bruker vi aldri tallet 12. Isteden for 12 bruker vi 0. 12 og 0 er det samme i mod 12.

La oss lave våre egne urskiver / klokker. Ta et stykke papir og en blyant og tegn en sirkel med diameter ca. 5 cm. Skriv inn tall rundt urskiven som om det var en vanlig klokke, men erstatt 12 med 0. Prøv å regne ut, ved at du rett og slett teller med klokken, disse oppgavene:

1) 20 (mod 12) = ?
2) 5 (mod 12) = ?
3) 16 (mod 12) = ?

Skriv både problemet og svarene på oppgavene på arket ditt.

La oss forsøke med urskiver som har andre tall enn 12:

Tegn en ny sirkel og lav en klokke som har 7 siffer. Sifrene skal være 0 – 6 og 0 skal stå på «toppen» det 12 normalt ville stått på en vanlig klokke. 1 til 6 fordeles jevnt og i rekkefølge med klokken.

4) Hva er din nye mod? Hvorfor?
5) 9 (mod 7) = ?
6) 12 (mod 7) = ?

Prøv å løse disse problemene ved å tegne opp nye klokker i andre mod:

7) 5 (mod 3) = ?
8) 10 (mod 9) = ?
9) 7 (mod 2) = ?

Positive tall:

Det er to andre måter å «telle» positive tall i modulær matematikk også.

Du kan subtrahere mod om igjen og om igjen helt til du står igjen med et tall som er større enn 0, men samtidig mindre enn tallverdien av mod. For eksempel: hva blir 12 (mod 5)? Vi starter med 12 og trekker fra 5 ( som er tallverdien av mod) og får 7. Er 7 > 0? Ja. Er 7 < 5? Nei. Vi må trekke fra èn gang til. 7 – 5 = 2. Er 2 > 0? Ja. Er 2 < 5? Ja. 12 (mod 5) = 2.

Forsøk å løse disse problemene ved å subtrahere (trekke fra). Skriv ned både problemet og svaret på arket ditt.

10) 8 (mod 3) = ?
11) 17 (mod 4) = ?
12) 25 (mod 9) = ?

Negative tall:

Hittil har vi bare sett på negative tall. For å telle positive tall har vi beveget oss «et hakk til høyre på urskiven for hver verdi vi har lagt til». Det er to måter å telle negative tall på. Den første er rett og slett å telle baklengs altså mot venstre på urskiven. Vi kan tenke på en vanlig klokke igjen. Klokken er 1. Hva var den for 3 timer siden. Svaret er 10.

Prøv noen enkle oppgaver du skal løse med sirkler du tegner opp:

13) -2 (mod 9) = ?
14) -9 (mod 3) = ?
15) -5 (mod 21) = ?

Hva er den andre metoden? Du kan telle negative tall ved å endre dem til positive tall! Hvordan vi gjør det? For å få et negativt tall til å bli positivt må du addere (legge til) mod til tallet helt til du får et positivt tall. For eksempel -5 (mod 8), start med -5 og legg til 8. Du får 3 (-5 + 8 = 3). Er 3 et positivt tall? Ja. Og det var det; -5 (mod 8) = 3.

La oss ta et annet eksempel.

Hva blir -9 (mod 4)? Start med tallet som er -9, adder mod som er 4. -9 + 4 = -5. Er -5 et positivt tall? Nei. Vi adderer igjen; -5 + 4 = -1. Er -1 positivt? Nei. Vi adderer igjen; -1 + 4 = 3. Er 3 et positivt tall? Ja. Og det var det. -9 (mod 4) = 3.

Du kan også bruke modulus til å multiplisere og dividere. Det finnes til og med enkelte typer matematiske problemer som ikke lar seg løse ved hjelp av vanlig matematikk, men som kan løses i modulær matematikk.

Det finnes en rekke funksjoner i modulærmatematikk som man kan kalle uforutsigelige og noen som blir enveisfunksjoner. Vi ser dette veldig lett hvis vi sammenligner en funksjon i vanlig matematikk med en tilsvarende funksjon i modulærmatematikk. Vanlige toveisfunksjoner er lette å reversere, i modulærmatematikk kan den samme funksjonen være så vanskelig å reversere at den i praksis blir en enveisfunksjon. La oss se på et greit eksempel på dette også. Hvis vi har funksjonen 3^x er x et tall og 3 multipliseres med seg selv x antall ganger. For eksempel kan vi gi x verdien 2 og vi får 3^x = 3² = 3x3 = 9. Verdien av funksjonen vil øke hvis verdien av x øker. Hvis vi vet verdien av funksjonen (og formelen) er det lett å regne tilbake. La oss si at formelen er den samme og verdien av funksjonen er 81. Vi kan da lett regne ut at x = 4 fordi 3⁴ = 81. Hadde vi gjettet på at X 0 5 ville det gitt verdien 243 og vi vet at vi skal frem til 81, altså har vi valgt feil verdi for x. Prøver vi igjen med x = 3 vil vi få at verdien av funksjonen er 27 og det er for lavt. Prøver vi litt til finner vi fort ut at x = 4. Hvis dette hadde vært i modulærmatematikk ville problemet blitt mye, mye vanskeligere å løse. La oss tenke oss at funksjonen fremdeles er 3^x og vi får opplyst at verdien av funksjonen er 3^x (mod 7) = 1 og så skal vi forsøke å regne oss tilbake til x. Vi kan begynne med å gjette på at x = 5 og regne ut 3⁵ (mod 7). Svaret på dette blir 5 og vi vet at det er feil vi skal ha et svar som er 1. Vi reduserer x til 4 og prøver igjen. Det blir feil, vi går i gal retning, svaret skal bli at x = 6. Dette betyr at i den vanlige matematikken kan vi prøve oss frem og se om «tampen brenner», den muligheten har vi ikke i modulærmatematikk. Det kan hende vi kan forsøke om igjen og om igjen til vi ved ren flaks finner riktig svar, men dersom det er snakk om store tall vil det være meget vanskelig. Tenk deg en funksjon som for eksempel 453^x (mod 21997). Det ville være nesten uoverkommelig selv med datamaskin. Svaret blir 5787 og det tok noen sekunder å regne ut på en kalkulator. (Windowskalkulatoren har en funksjon for å regne modulus).

For å vise hvor uberegnelig dette kan være setter vi opp en tabell over noen muligheter for funksjonen 3^x i forskjellige potenser og 3^x (mod 7) i de samme potensene.

Som du ser er rad 2 lineær, men rad 3 er uten system.

Matematikken bak RSA

(Ronald Rivest, Adi Shamir og Leonard Adleman)

(Kilde: Simon Singh: Koder. Aschehoug 2000)

Her følger en enkel, matematisk beskrivelse av hvordan kryptering
og dekryptering med RSA fungerer.

1. Alice velger to kjempestore primtall, p og q. Primtallene bør være enorme, men for enkelhets skyld lar vi Alice velge p = 17 og q = 11. Disse tallene MÅ hun holde strengt hemmelig.

2. Alice multipliserer disse tallene med hverandre og får et nytt tall N. I dette tilfellet blir N = 187. Så velger hun et nytt tall, e, og i dette eksemplet velger hun at e = 7.
   
   [e og (p - 1) _* (q - 1) bør ikke ha felles faktorer, men dette er en teknisk detalj].

3. Nå kan Alice offentliggjøre e og N i noe som tilsvarer en telefonkatalog, eller avertere dem i avisen. Siden disse to tallene er nødvendige for krypteringen må de være tilgjengelige for alle som kunne ha lyst til å sende en kryptert melding til Alice. Sammen kalles disse to tallene den offentlige nøkkelen. Det er for så vidt ingenting i veien for at e kunne være en del av alles offentlige nøkkel, det ville ikke spille noen rolle. Alle må imidlertid ha forskjellig verdi for N, eftersom dette tallet er avhengig av hvilken p og q du har valgt.

4. For at en melding skal kunne krypteres må den først gjøres om til et tall, M. For eksempel kan man bruke ASCII koden, som er binær, og det binære tallet kan gjøres om til et desimaltall. Derefter kan vi kryptere M og få ut en chiffertekst som vi kan kalle C i følge formelen:
   
   C = M^e (mod N)

5. Vi tenker oss nå at Bob er litt forelsket i Alice og vil sende henne et kyss, kyss i kjærlighetsbrev blir ofte representert av bokstaven X. I ASCII blir X representert av det binære tallet 1011000, som i det desimale tallsystemet tilsvarer 88. M (meldingen) er altså lik 88.

6. For å kryptere meldingen til Alice må Bob begynne med å finne Alices offentlige nøkkel. Han kan slå opp i en katalogtjeneste (et eksempel er ldap://keyserver.pgp.com) eller han kan spørre henne. Han finner at N = 187 og e = 7. Dette gir ham all informasjon han trenger for å kunne kryptere meldingen til Alice. Med M = 88 blir formelen:
   
   C = 88⁷ (mod 187)

7. Dette er det slett ikke lett å regne ut med en kalkulator, fordi displayet ikke vil kunne håndtere så store tall. I vårt tilfelle har vi valgt veldig små tall (88⁷ = 40867559636992). Det finnes imidlertid et smart trick for å beregne slike eksponentialfunksjoner i modulær matematikk. Vi vet fra før at 7 = 4 + 2 + 1 og dermed blir:
   
   88⁷(mod 187) = [88⁴ (mod 187) _* 88² (mod 187) _* 88¹ (mod 187)] (mod 187)
   
   88¹ = 88 = 88 (mod 187)
   
   88² = 7 744 = 77 (mod 187)
   
   88⁴ = 59 969 536 = 132 (mod 187)
   
   88⁷ = 88¹ _* 88² _* 88⁴ = 88 _* 77 _* 132 = 894 432 = 11 (mod 187)
   
   Nå kan Bob sende chifferteksten (den krypterte meldingen) C = 11 til Alice.

8. Vi har sett at eksponentialfunksjoner i modulær matematikk (i praksis) er enveisfunksjoner, slik at det er svært vanskelig å regne seg bakover fra C = 11 og finne M, den opprinnelige meldingen. Derfor kan heller ikke Eve regne seg bakover og dechiffrere meldingen.

9. Alice, derimot kan dekryptere meldingen fordi hun har spesiell informasjon som hverken Bob eller den sleipe Eve har... Hun vet nemlig verdiene av p og q. Ved hjelp av disse regner hun ut et spesielt tall, d, som er dekrypteringsnøkkelen, eller hennes private nøkkel.
   Tallet d regnes ut efter følgende formel:
   
   e _* d = 1 (mod (p-1) _* (q-1))
   
   7 _* d = 1 (mod 16 _* 10) (Husk at vi hadde p = 17 og q = 11 i utgangspunktet.)
   
   7 _* d = 1 (mod 160)
   
   d = 23
   
   Det er ikke så opplagt hvordan man finner verdien av d, men en spesiell teknikk som kalles Euklids Algoritme 1) setter Alice i stand til å finne d fort og greit.

10. For å dekryptere meldingen bruker Alice følgende formel:
    
    M = C^d (mod 187)
    
    M = 11²³ (mod 187)
    
    M = [11¹ (mod 187) * 11² (mod 187) * 11⁴ (mod 187) * 11¹⁶ (mod 187)] (mod 187)
    
    M = 11 * 121 * 55 * 154 ( mod 187)
    
    M = 88 = 1011000b = X i ASCII

Rivest, Shamir og Adelman har skapt en spesiell enveisfunksjon som bare kan reverseres av den som har adgang til fortrolig informasjon, nemlig verdiene av p og q. Hver eneste funksjon kan gjøres personlig ved at man velger sine egne verdier for p og q, som igjen når de multipliseres med hverandre gir en unik og personlig N. Denne funksjonen gjør det mulig for hvem som helst å sende en kryptert melding til noen ved å bruke vedkommendes selvvalgte N. Imidlertid er det bare adressaten som kan dekryptere meldingen fordi det er bare hun som kjenner verdiene av p og q og dermed den eneste som kan beregne dekrypteringsnøkkelen d.

Svar på oppgavene:

1. 20 (mod 12) = 8
   2) 5 (mod 12) = 5
   3) 16 (mod 12) = 4
   4) 7 fordi sifrene går fra 0 til 6, totalt 7 tall.
   5) 9 (mod 7) = 2
   6) 12 (mod 7) = 5
   7) 5 (mod 3) = 2
   8) 10 (mod 9) = 1
   9) 7 (mod 2) = 1
   10) 8 (mod 3) = 2
   11) 17 (mod 4) = 17 – 4 = 9 ( 9>0? ja, 9<mod? nei) 9 - 4 = 5 (5>=? ja, 5<mod? nei) 5 – 4 = 1 ( 1>0? ja, 1 < mod? ja.) 17 (mod 4) = 1.
   12) 25 (mod 9) = 25 -9 = 16 -9 = 7; 25 (mod 9) = 7 fordi 7 > 0 og 7 < mod. (mod var 9).
   13) -2 (mod 9) = 7
   14) -9 (mod 3) = 0
   15) -5 (mod 21) = 16

Fotnoter:

1) Euklids Algoritme slik FOLDOC beskriver den:

Euclid's Algorithm

<algorithm> (Or "Euclidean Algorithm") An algorithm for finding the greatest common divisor (GCD) of two numbers. It relies on the identity

        gcd(a, b) = gcd(a-b, b)

To find the GCD of two numbers by this algorithm, repeatedly replace the larger by subtracting the smaller from it until the two numbers are equal. E.g. 132, 168 -> 132, 36 -> 96, 36 -> 60, 36 -> 24, 36 -> 24, 12 -> 12, 12 so the GCD of 132 and 168 is 12.

This algorithm requires only subtraction and comparison operations but can take a number of steps proportional to the difference between the initial numbers (e.g. gcd(1, 1001) will take 1000 steps).

2) ressurser for å forså modulær matematikk:

• http://www.mathsnet.net/asa2/modules/index.html

• http://mrtc.uark.edu/IMME

• http://www.shodor.org/succeedhi/succeedhi/modularmath/introduction.html

Mer om kvantemekanikk:

http://eve.physics.ox.ac.uk/NewWeb/Research/communication/communication.html

Tilbake til begynnelsen av dokumentet