Ideer

Den om generalen, noen røtter og et talltriks

Kryptering med offentlige nøkler fra A til p.

Om du mottar en konvolutt fra meg, hvordan kan du være sikker på at jeg har sendt den? Hvordan kan du være sikker på at innholdet i konvolutten er det samme som da jeg postla den? Hvordan kan jeg være sikker på at bare du, og ikke noen andre, åpner den og leser innholdet?

Disse spørsmålene har, for å si det forsiktig, vært av interesse for folk med statshemmeligheter og militære hemmeligheter til alle tider. Nå som vi driver fjernbank, fjernhandel, fjernhelse og fjern-alt-mulig over internett, har det brått blitt relevant for alle.

Første forsøk: passord. En mulighet for kongen som vil sende hemmeligheter til en general er å forkaste konvolutten og heller sende en låst boks, smidd slik at bare en nøkkel generalen har fått utdelt kan åpne den. I datavirkeligheten kunne et slikt system lages med passord. Om vi først blir enige om et passord, kunne jeg kryptere informasjonen med dette passordet som en nøkkel. De som ikke har passordet, kan ikke se.

Det kan være en løsning å utstede slike passord til alle du kunne tenke deg å sende noe til, men det vil bli uhyre komplisert om alle i et nettverk skal kunne sende hemmeligheter til hverandre: Da må alle holde seg med hver sitt unike sett av passord for alle personene i nettverket.

Det vil også være usikkert: Passordet må på et eller annet vis kommuniseres før kryptering kan skje. Om man ikke kan møtes ansikt til ansikt, vil dette være en akilleshæl for systemet.

Offentlige passord. Tenk om du kunne ha en oppskrift som forteller hvordan man låser boksen, og en annen oppskrift som forteller hvordan man skal låse den opp. Og tenk også at kjennskap til låse-oppskriften er helt uten verdi for å gjette seg til opplåsings-oppskriften! Da kunne du spre oppskriften på å låse noe inn slik at bare du kan åpne det, uten at noen dermed kommer noe nærmere å låse den opp.

---

Er det egentlig umulig?

I de krypteringsløsningene vi bruker i dag, er nøklene uavhengig av hverandre hvis – og bare hvis – et bestemt teorem i informatikk er sant. Teoremet sier, litt omtrentlig, at det er umulig å beregne såkalte diskrete logaritmer på noen effektiv måte med en datamaskin.

Dette teoremet anses ikke som bevist. Om noen skulle komme opp med en algoritme som knuser det, vil det raskt gjøre kryptografien på internett verdiløs.

---

Dette går an, i tallenes verden. Disse oppskriftene, eller nøklene, utgjør et nøkkelpar. Paret har én privat og én offentlig nøkkel. Med den offentlige nøkkelen kan man låse en tekst på en måte som bare den private nøkkelen kan låse opp.

Da er det bedre jo flere som kjenner den offentlige nøkkelen din.

Fellesnøkkel. Tilbake til boksene, er det som om generalen først lager en boks og en nøkkel hun beholder selv, og så sender boksen åpen til kongen. Deretter kan kongen – eller noen andre – smekke igjen låsen og sende boksen tilbake, men bare generalen kan åpne. Metaforen til den virkelige verden halter imidlertid fortsatt på ett punkt: I virkeligheten vår på internett lærer du ingenting nyttig om nøkkelen ved å undersøke låsen – altså, du kan ikke vite noe om den private nøkkelen ved å studere den offentlige. Vår general ville kunne publisere hvordan man lager en lås som passer til hans nøkkel, slik at alle kan sende ham sikre bokser. I den fysiske virkeligheten ville det naturligvis avsløre nøkkelen. I den digitale kryptoverdenen hjelper det ikke spionen det spøtt.

Sertifikater. Og slik er det vi havner på dagens krypteringsteknologi. Morgenbladet har for eksempel et offentlig sertifikat alle kan laste ned og studere. Når du besøker morgenbladet.no, sendes først dette offentlige sertifikatet til deg. Med det i hende, kan din nettleser sende en ny forespørsel til vår tjener, men kryptert slik at den bare kan låses opp med vår nøkkel. I denne forespørselen sender din nettleser med en nøkkel som vår tjener bruker til å låse informasjonen slik at bare du kan åpne den, ikke helt ulikt et passord.

Alt en utenforstående kan se, er at du sender en forespørsel, at vår tjener svarer med en offentlig kjent nøkkel, og derfra er alt bare uforståelige, tilfeldig fordelte tegn uten noe system – med mindre man kjenner hemmeligheten som din nettleser og vår tjener nettopp ble enig om.

Har du kommet såpass langt som dette, kan du klappe deg på skulderen. Du forstår nå mye om kryptografi via offentlige nøkler. Men det er også mye spennende matte vi ikke har fått rørt ved ennå. Heng på!

Men hvordan? Så langt har du bare blitt fortalt at det går an med disse låsene som ikke avslører nøkkelen sin. Her skal du få forklaringen på hvordan, omtrent slik den ble lagt fra av Diffie og Hellmann, som først beskrev metoden i 1976. En advarsel: Matematikken bak er ikke like enkel som fortellingen om nøkler og generaler.

Du har kanskje vært borti sånne tankelesertriks i barndommen, der man ber en annen person om å tenke på et tall, legge til 20, trekke fra atten, gange med 3 og så videre og så videre – og til slutt kan man triumferende annonsere hvilket tall tilhøreren tenkte på? Dette ligner.

Modul. Først må vi gjenoppfriske et matematisk begrep: modulo. Modulo, ofte forkortet mod, er en operasjon i matematikken, på samme måte som for eksempel multiplikasjon. Vi kan skrive 5 × 3, og vi kan skrive 5 mod 3. Modulo er resten når du deler det første tallet på det andre. 5 mod 3 er 2, fordi 5 delt på tre er 1 pluss en rest på 2. Mens 6 mod 3 = 0 – det blir ingen rest når 6 deles på 3.

---

Diffie-Hellmann

Whitfield Diffie og Martin Hellmann skrev om denne algoritmen i  1976.

I ettertid har det blitt kjent at den britiske etterretningstjenesten GCHQ hadde kommet opp med samme idé ett år tidligere, men da holdt den hemmelig.

Ralph Merkle beskrev først konseptet med offentlige og private nøkler. Diffie og Hellmann var først ute med implementeringen, altså detaljene om primtallsdivisjon, primærrøtter osv.

---

Tenk deg at Anders har en hemmelighet han vil fortelle Bent, uten at Carl skal få vite hva som står. Han må ha et passord å kryptere informasjonen med, og han må få sendt dette passordet til Bent. Det Diffie og Hellmann oppdaget, var at de kan gå frem med litt tallmagi for å stå igjen med en delt hemmelighet uten å noen gang nevne den direkte.

Metoden, som kalles Diffie-Hellmanns nøkkelutvekslingsalgoritme, kan gjennomføres slik:

  1. Anders må først velge et primtall som han skal kalle p. Han velger 7. Primtall er tall som bare er delelige på seg selv og 1, for eksempel 7 og 13 (men ikke 9, som er delelig på 3).
  2. Anders velger et tall som står i et helt spesielt forhold til 7, nemlig et tall som er en primitivrot modulo 7.

    Siden du har bedt om den avanserte forklaringen, skal du få den også her. Disse primitivrøttene er tall som passer til et helt bestemt mønster. La oss for eksempel ta 3, som er en primitivrot til 7. Det er den fordi, om vi regner ut 3 opphøyd i første potens og tar modulus 7, og så (3 opphøyd i andre potens) mod 7, og så videre, helt opp til 3 opphøyd i sjette mod 7, så vil vi se noe pussig: Alle svarene er ulike, slik at alle de ulike tallene fra 1 til og med 6 er representert nøyaktig en gang hver. Derfor er ikke 2 primitivrot for sju: For den får vi verdiene 2, 4, 1, 2, 4, 1 – altså mangler halvparten av tallene.

    For hvert eneste primtall finnes det flere slike primitivrøtter. For sju finnes både 3 og 5. Anders velger 3 som sin rot. Den heter fra nå av g.
  3. Anders sender p og g til Bent. Han trenger ikke å bry seg om at noen lytter på linjen. Det gjør ingenting om noen får vite hva disse tallene er.
  4. Nå må Anders velge et tilfeldig, hemmelig tall som han skal kalle a. La oss si han velger 6, men det kan i prinsippet være et hvilket som helst heltall. Så henter han en formel, A = ga mod p, og fyller inn sine tall: A = 36 mod 7 = 1. Han sender dette resultatet, altså tallet 1, til Bent.
  5. Bent må gjøre det samme, bare med b. Han velger 22. Han regner ut B = gb mod p, som er 4. Han  sender tallet 4 til Anders.
  6. Anders fyller inn og regner ut formelen s = Ba mod p = 46 mod 7 = 1.
  7. Bent fyller inn og regner ut formelen s = Ab mod p = 122 mod 7 = 1. s er nå lik for begge to. Vi kan se hvorfor om vi utvider Anders' formel: B er lik gb mod p, og dermed er det hele lik gab mod p. Det samme gjelder for Bent.

Hemmelig. Dermed har de kunnet regne ut den samme hemmeligheten – s, uten å avsløre noe som kan sette en angriper på sporet. Det eneste angriperen Carl kan se, er at p er 7, g er 3, A er 4 og B er 1. Uten å vite hva a eller b er, altså de hemmelige tallene Anders og Bent valgte seg, kommer Carl ingen vei med den siste formelen: Han mangler akkurat én bit.

Hvis Anders eller Bent hadde valgt et annet tall, ville s blitt noe annet. Men det ville fortsatt vært likt hos både Anders og Bent. Og nå som de har en hemmelighet kan de bruke den som passord for meldingene de deretter sender mellom hverandre.

I dette eksemplet har selvsagt Carl en enkel jobb likevel: Det er bare sju mulige hemmeligheter, tallene fra 0 til 6. Han kunne bare prøve alle etter tur. I virkelighetens kryptering brukes derfor gigantiske primtall med hundrevis av sifre, og da er det ikke lenger praktisk mulig å prøve alle mulighetene.

Låst. Tilbake til forklaringen uten matematikk over, er altså a den hemmelige nøkkelen og A den offentlige nøkkelen. De henger sammen via en helt bestemt algoritme, men men kan ikke gå fra A til a, bare fra a til A. Årsaken er moduloen:  a kan være et hvilket som helst tall, enormt eller bitte lite. Uansett hvilket gjør moduloen at A blir presset inn mellom 0 og p. Det er en enveisport.

For å komme fra dette prinsippet til hvordan det faktisk foregår på internett er det også mange, mange forvanskninger, protokoller og prosedyrer. Det finnes også mange andre algoritmer enn denne. Andre matematiske enveisgater, slik denne modulofunksjonen tilbyr, har blitt tatt i bruk i stedet for primtall-og-røtter, for eksempel visse egenskaper ved elliptiske kurver. Men hovedtrekkene består.

Mer fra Ideer