RSA-systemet

La oss si at du ønsker å sende meg en superhemmelig melding (eller en stor seddelbunke for den saks skyld – tusen takk). Anta videre at

• vi har hver vår hengelås (forskjellige sådanne) og tilhørende nøkkel,
• hengelåsene våre er uhyre vanskelig å kopiere, og at det derfor ikke fins noen andre slike hengelåser og
• vi bor så langt fra hverandre slik til at den eneste muligheten du har for å sende meldingen til meg er å sende den i et lite skrin som er sikret mot alle typer innbrudd så lenge det er låst.

Hvordan skal du klare å sende meldingen til meg uten å kommunisere med meg, og uten at noen andre får tak i den?

Stopp og tenk litt på dette før du leser videre, for her kommer løsningen:

Du låser skrinet med din hengelås, beholder nøkkelen din og sender skrinet til meg. Når jeg får skrinet, låser jeg også skrinet med min hengelås og sender skrinet som nå er låst med to låser tilbake til deg. Du låser opp låsen din og sender skrinet til meg igjen, og dermed kan jeg endelig åpne skrinet med min nøkkel!

Vi kunne ha gjort løsningen litt enklere hvis du kunne kommunisere med meg og si at du ønsket å sende meg en melding. Da kunne jeg ha sendt deg hengelåsen min (som måtte ha vært låst opp slik at du bare kunne smekke den på skrinet). Dermed hadde vi spart litt tid. Tid og penger er alltid de viktigste faktorene når hemmelige meldinger sendes verden over i dag, og tid er penger.

For å gjøre ting enda enklere og tidsbesparende, hadde det ikke vært greit om den åpne hengelåsen min hadde vært allemannseie, slik at alle som ønsket å sende meg en melding kunne få tak i den og smekke den på et sikkert skrin med meldingen i ? Det gjør jo ikke noe om alle kan få tak i hengelåsen så lenge bare jeg kan åpne den. Dette er tankegangen bak det som kalles et "public key cryptosystem" ("kjent-nøkkel-kryptosystem"). Ideen kom på 1970-tallet. Et kryptosystem er for øvrig en algoritme som kan omgjøre en melding slik at den blir ugjenkjennelig (koding), og som kan omgjøre det ugjenkjennelige slik at vi får tilbake originalmeldingen (dekoding).

Hovedfordelene med kjent-nøkkel-systemer er økt sikkerhet og enklere bruk: Jeg trenger ikke å gi nøkkelen min til noen, siden den ikke brukes til å kode meldingen, men bare til å dekode den. Dette er i motsetning til å bruke et hemmelig-nøkkel-system: her brukes nøkkelen både til koding og dekoding, og dermed må både du og jeg på en eller annen måte utveksle en hemmelig nøkkel, med fare for at andre får tak i den og dermed kan knekke koden. Det er imidlertid ulemper ved å bruke kjent-nøkkel-systemer, så i dag kombinerer man begge systemene, både for å øke sikkerheten og for å minske tidsbruken.

RSA-systemet er det mest populære og brukte kjent-nøkkel-kryptosystemet i dag. RSA-algoritmen er blant annet bygd inn i operativsystemene til Microsoft, Apple, Sun og Novell, den fins i sikre telefoner og i smart-kort, den sikrer Internett-kommunikasjonen og brukes internt av mange institusjoner som departementer, selskaper, laboratorier og universiteter.

R, S og A er forbokstavene i etternavnene på matematikerne som fant opp algoritmen i 1977: Ronald Rivest, Adi Shamir og Leonard Adleman. Algoritmen er som følger:

1. Jeg velger to STORE primtall p og q. La oss bruke p = 11 og q = 13 som eksempel, selv om de ikke regnes som store.
2. Jeg regner ut produktene n = p·q og φ = (p-1)(q-1). For oss blir n = 143 og φ = 120. Nå trenger jeg ikke primtallene p og q lenger, så de må jeg sørge for å tilintetgjøre.
3. Jeg velger to tall d og e slik at e < n, e og φ ikke har noen felles faktorer bortsett fra 1, og slik at produktet d·e gir rest 1 nå vi deler det med φ (vi sier at d·e er kongruent med 1 modulo φ). I vårt eksempel kan vi for eksempel bruke d=37 og e=13 siden 13 er et primtall mindre enn 143 og 13•37=4•120 + 1 (det er vanlig å velge e<d).
4. Jeg offentliggjør n og e i en slags telefonkatalog, og beholder d som min private nøkkel.

Når du skal sende en melding, kall den M, til meg, gjør du den først om til tall. Dette kan gjøres enklest mulig ved å erstatte a med 1, b med 2 osv. Deretter deler du tallene inn i blokker på vanligvis 8 tall (for ikke å få så store tall å regne med). Så leter du opp meg i katalogen, og finner min kjente nøkkel, n og e. Så må du ved hjelp av en datamaskin regne litt: Du opphøyer alle tallene i e (13), og deler hvert av dem på n (143). Resttallene du får i divisjonene er den kodete meldingen, som du sender til meg.

Jeg mottar den kodete meldingen, og opphøyer alle tallene i d-te (37, så jeg får vanligvis en større jobb enn deg). Jeg deler også alle disse tallene på n (143), og resttallene i disse divisjonene gir meg originalmeldingen som du ønsket å sende til meg! Det hele virker på grunn av litt tallteori, og vanskeligheten med å knekke systemet ligger i at man ikke kan finne d fra n og e så lenge man ikke kjenner primtallene jeg valgte til å begynne med, hvis primtallene var STORE. Hva som menes med et STORT primtall i denne sammenhengen forandres så å si fra dag til dag, men vi snakker om over 50 siffer...

Høres dette interessant ut? For mer stoff om kryptologi og RSA-systemet anbefales følgende litteratur:

1) Johnsen, Ben: "Kryptografi, primtall og Riemanns hypotese", Normat nr. 1 1986.
2) Kahn, David: "The Codebreakers : the story of secret writing", Macmillan 1967.