RSA

krypteringsalgoritme

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

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

Generering av nøkkeltall

rediger
  • 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

rediger
  • 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

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

Eksempel

rediger

Generering av nøkkeltall

rediger

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

rediger

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

rediger

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

rediger

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.[1]

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

rediger
  1. ^ SIAM News, Volume 36, Number 5, June 2003 Arkivert 16. januar 2017 hos Wayback Machine.,"Still Guarding Secrets after Years of Attacks, RSA Earns Accolades for its Founders", by Sara Robinson