Ditt privatliv beskyttes av primtall


På Internett skjules din private informasjon ved hjelp av store primtall, og det eneste du trenger for å skjønne det er å kunne klokka.

Når du overfører penger på Internett er det viktig at du beskytter informasjonen for å forhindre at andre kan overvåke og endre kommunikasjonen mellom deg og banken. Dette er noe vi gjør hver eneste dag, og alt er basert på primtall. Vi har alle lært om primtall på skolen, og du husker kanskje at dette er tall som kun er delelige med seg selv og tallet 1. Du husker kanskje også at alle andre tall kan deles opp slik at vi står igjen med et produkt av primtall. Men hva har disse spesielle tallene med sikkerhet på Internett å gjøre?

 

Symmetrisk kryptografi

Mennesker har alltid utvekslet hemmelig informasjon, og de eldste krypterte meldingene vi har funnet er fra over 2000 år før Kristus. Siden den tid har vi stadig utviklet mer avanserte metoder for å holde meldinger hemmelige for hverandre. Fra år 2000 f.kr. og helt frem til midten av 1970-tallet kjente vi bare til det vi kaller for symmetrisk kryptografi, hvor nøklene vi bruker for å kryptere og dekryptere meldingene er like. Et klassisk eksempel på dette er det vi kaller for Cæsar-chiper, som går ut på å flytte alle bokstavene i den hemmelige meldingen tre plasser til høyre i alfabetet før beskjeden sendes avgårde. Da vil for eksempel meldingen “abc” bli til “def”. For å dekryptere meldingen må mottakeren da flytte alle bokstavene tre plasser til venstre i alfabetet. Nøkkelen her er antall plasser bokstavene skal flyttes, og vi ser helt tydelig at nøklene er knyttet til hverandre. Ved bruk av symmetrisk kryptografi er de to partene avhengig av å møtes fysisk for å avtale nøkkel. Med dagens systemer er ikke dette nødvendig.

 

Asymmetrisk kryptografi

Under andre verdenskrig ble de første moderne datamaskinene utviklet, og dette ble starten på en helt ny epoke. Med datamaskinenes inntog utviklet kryptografien seg fra omstokking av bokstaver med bestemte nøkler, til å bli erstattet av større maskinbaserte beregninger. Dette gjorde informasjonsutveksling enda vanskeligere å dekryptere, hvis meldingen skulle havne i feil hender. I takt med teknologiens utvikling ble også krypteringsmetodene bedre og bedre, og parallelt med den kalde krigen oppdaget sikkerhetsforskere flere de av krypteringssystemene som har lagt grunnlaget for all kryptert informasjon på Internett i dag. Vi skal se litt nærmere på krypteringssystemet RSA fra 1977, oppkalt etter Ron Rivest, Adi Shamir og Leonard Adleman, og som er et av de mest brukte systemene.

RSA-systemet er et eksempel på det vi kaller asymmetrisk kryptografi. Her bruker vi én nøkkel for å kryptere meldingen og en helt annen nøkkel for å dekryptere meldingen, og det er ikke noen åpenbar eller synlig sammenheng mellom nøklene, i alle fall ikke så lenge du bare kjenner krypteringsnøkkelen. Systemet gjør operasjoner på heltall, og det er her de spesielle egenskapene til primtall spiller en stor rolle. Men før vi skal begynne å kryptere og dekryptere meldinger så må vi oppfriske hvordan vi regner på tid, også kalt klokkearitmetikk.

 

Klokkearitmetikk

Alle vet at dersom klokka er 22, og det går 5 timer, så er klokka 3, ikke 27. Dette er fordi vi har 24 timer i døgnet, og dersom vi får et tall som er større enn 24 så bryr vi oss kun om de timene som gjenstår når vi har trukket fra 24. På samme måte vil klokka være 10 dersom vi lar det gå 36 timer fra klokka er 22, eller 1 dersom vi lar det gå 3*3*3 = 33 = 27 timer.

Matematikere kaller dette for klokkearitmentikk, eller moduloregning. Rent matematisk ville vi skrevet dette som 22 + 5 ≡ 27 ≡ 3 (mod 24), hvor trippelerlik (leses “kongruent med”) betyr at vi kun ser på resten etter å ha trukket fra 24. Tallet vi skal stå igjen med må alltid være mindre enn 24, og vi bryr oss ikke om hvor mange dager det har gått, kun hva klokka er akkurat den dagen vi har kommet til.

 

RSA-kryptosystemet

Nå skal vi bygge opp RSA-systemet. Noen har lyst å sende et hemmelig tall x til oss, og vi har delt prosessen opp i syv følgende steg:

 

1. Velg to av dine favorittprimtall, la oss kalle dem p og q.

2. Multipliserer primtallene sammen, p*q, og få et nytt tall som vi kaller n.

3. Trekk tallet én fra begge primtallene, og multipliser dem sammen til tallet m, dvs (p-1)*(q-1) = m.

4. Så velger vi et tall e, som ikke har noen felles faktorer med m. En felles faktor mellom to tall betyr at det finnes et tall som både e og m kan deles på. Ofte er det enkleste å velge e som et primtall, og sjekke at dersom vi deler me så får vi ikke et heltall.

5. Så må vi finne et siste tall d, slik at dersom vi multipliserer d med e, så får vi 1 som rest når vi trekker fra m. Se eksempel under. Med små tall så kan vi bare prøve oss frem, men for store tall så må datamaskinen følge noen spesielle instruksjoner for å gjøre dette på en effektiv måte.

 

Tallene n og e deler vi med hele verden, mens vi holder tallene p, q og d helt for oss selv.

 

6. For å finne den kryptere meldingen y regner vi ut x opphøyd i e modulo n, dvs. y ≡ xy  (mod n). Dette er beskjeden som sendes til oss.

7. For å dekryptere meldingen tilbake til x tar vi y opphøyd i d modulo n, dvs. x  ≡ yd (mod n). Da kan vi lese beskjeden som noen har sendt til oss.

 

Da er vi klare til å sende en hemmelig melding. Det er viktig at meldingen vår er et heltall, og at dette heltallet er mindre enn produktet av primtallene, n. Det finnes mange måter å gjøre om en beskjed til et tall, for eksempel ved å bytte ut “a” med “0”, “b” med “1” osv. La oss si at noen har lyst å sende oss en hemmelige beskjed x, som er et tall mellom 0 og 29. Det kan for eksempel representere en enkelt bokstav i det norske alfabetet. Da kan vi følge algoritmen beskrevet over, hvor vi har valgt tall selv:

 

1. Vi velger primtallene p = 5 og q = 11, de er fine og små nok til å regne på. Det er viktig at produktet av disse tallene er større enn 29, fordi det er en av verdiene som den hemmelige meldingen kan ha.

2. Regner ut 5 * 11 = 55 = n. Nå får 55 samme rolle som tallet 24 fikk da vi regnet med klokka.

3. Regner ut m = (5-1) * (11-1) = 4 * 10 = 40.

4. Velger e = 23, som er et primtall, og som ikke har noen felles faktorer med 40.

5. Om vi tester litt kan vi finne ut at 23 * 7 ≡ 161  ≡ 1 (mod 40). Da setter vi d = 7.

 

Nå er tallene n = 55 og e = 23 offentlige tall som alle kan kjenne til. Det er de tallene som brukes når noen ønsker å kryptere en melding og sende til oss. De andre tallene er hemmelige, og det er kun vi som kjenner dem.

 

6. Noen krypterer en melding: yxe ≡ 2 (mod 55). Da er y = 2 den hemmelige meldingen som noen sender til oss, og som vi må dekryptere.

7. Vi mottar tallet y = 2, og dekrypterer meldingen: xyd ≡ 27 ≡ 128 ≡ 18 (mod 55). Da har vi funnet tilbake til hva beskjeden var opprinnelig, nemlig bokstaven “s”, den attende bokstaven i alfabetet (når “a” settes til 0).

 

Primtallenes betydning

Nå vet vi altså hvordan vi kan sende hemmelige beskjeder, men hva er egentlig primtallenes rolle? Kan vi nå hacke en nettbank? Vi bruker primtall, men vi har ikke forklart hvorfor de er viktige. Kunne vi valgt noen andre tall istedenfor?

Det viser seg at vi faktisk må velge primtall for at dette skal kunne brukes. Grunnen til det er at vi vil at alle krypterte meldinger skal kunne dekrypteres tilbake til den opprinnelige beskjeden. Dersom vi bruker andre tall så kan vi fort ende opp med at beskjeden dekrypteres til noe helt annet eller at den ikke kan dekrypteres i det hele tatt.

Primtallene spiller også en stor rolle når det gjelder sikkerhet. På den ene siden er det viktig at systemet fungerer og alltid gir korrekt svar. På den andre siden er det like viktig at fremmede ikke klarer å dekryptere og lese beskjedene vi sender. Den hemmelige nøkkelen er som nevnt tallene p, q og d, hvor vi bruker d til å dekryptere meldingen vi mottar. d er avhengig av p og q, og det er derfor vi klarer å finne det tallet, mens for alle andre som ikke kjenner p og q så er det vanskelig å beregne.

Sikkerheten er i bunn og grunn avhengig av at selv om hele verden kjenner til tallet n, så klarer de ikke å finne p og q. Forklart med andre ord: selv om alle vet at et tall er et produkt av to primtall, så klarer ingen å finne de to faktorene. Primtallene som brukes nå er på størrelse med 1024 bit, eller i overkant av 300 sifre, og fortsatt er ingen datamaskin i verden kraftig nok til å faktorisere dette produktet – men siden datamaskinene stadig blir kraftigere, må vi også bruke større og større primtall. Noen bruker allerede primtall med over 4000 bit, eller 1230 sifre.

 

Privatlivet ditt blir bevart

Når vi sender informasjon over Internett som vi ikke ønsker at andre skal lese, er det altså primtall som gjør dette mulig. De sørger for at meldingene kan krypteres på en sikker måte, og kan dekrypteres til den opprinnelige meldingen. Du er nå i stand til å sende dine egne hemmelige meldinger, men det er kanskje litt tidlig å starte din egen nettbank allerede i dag.