RSA

RSA er en krypteringsalgoritme basert på offentlig nøkkel (en.: public key).

Drift
For å bruke RSA-algoritmen må den gjennom tre steg; generering av nøkkeltall, kryptering og dekryptering.

Generering av nøkkeltall
 Mottaker finner fram to primtall som  og  og regner ut  og . For at dette skal bli tilstrekkelig sikkert må man velge to store primtall (over noen 100 siffer i hver).
 Nå velger mottaker et tall  slik at 
 Tallene  og  kan nå offentliggjøres for at sender kan begynne kryptering. Dette er den offentlige nøkkelen (en.: public key).
 Kongruensen  regnes nå ut, og det minste positive tallet velges til det hemmelige tallet . (= hemmelig dekrypteringsnøkkel).

Kryptering
 Meldingen som skal sendes gjøres om til tall. La  være ett av tallene.
 Vi finner nå det minste positive tallet for , slik at . Resten ved divisjonen  er altså den hemmelige meldingen.
 Nå kan avsender sende  til mottaker.

Dekryptering
 I dekrypteringsprosessen er  det minste positive tallet i . Ved å finne resten av  kan man finne meldingen, .

Eksempel

Generering av nøkkeltall
Vi velger to primtall som  og . 
  og 

Vi finner n og b.
 
 

Nå må vi finne en verdi for  slik at .
 Vi faktoriserer .
  
 Nå velger vi et tall for . Vi kan velge  siden  ikke finnes i 
 Vi ser at 

Vi offentliggjør nøklene n og e, (e = encryption key)
  og 

Nå må vi lage det hemmelige tallet .
 
 
 
 
 
 

 Det hemmelige tallet er dermed  (d=decryption key)

OBS:  og  er ikke alltid like. Det er bare en tilfeldighet at de er like i dette eksemplet.

Kryptering
Vi mottar de offentlige nøklene  og 
  og 

Meldingen  ønskes å bli sendt, men den må krypteres først.
For å finne , den krypterte meldingen, gjør vi slik:
 
 
 
 
 

 Den hemmelige meldingen er

Dekryptering
Vi mottar den krypterte meldingen .
 

Fra tidligere kjenner vi den hemmelige nøkkelen  og den offentlige nøkkelen 
  og 

Vi ser at det er en sammenheng mellom ,  og  slik at vi kan finne .
 
 

For å få lettere tall å regne med så bruker vi litt kreativ regning. Vi ser på eksponenter av 22 som er lavere enn 11.
 
 
 
 

Vi ser at 
 
 
 
 

Vi har nå funnet den krypterte meldingen

Historie
Algoritmen ble først beskrevet i 1977 av Ron Rivest, Adi Shamir og Leonard Adleman ved MIT; de tre bokstavene RSA er initialene i etternavnene deres i samme rekkefølge som de fremkommer på artikkelen deres.

Den Britiske matematikeren Clifford Cocks beskrev et lignende system i et internt dokument for den britiske etterretningstjenesten GCHQ. Hans oppdagelse ble ikke offentliggjort før i 1997, grunnet top-secret klassifisering av arbeidet.

MIT fikk et patent på "Cryptographic communications system and method" som benyttet algoritmen i 1983. Patentet ville vært gyldig til 2003, men ble offentliggjort av RSA 21. september 2000.

Referanser

Kryptografiske algoritmer