RSA

RSA je algoritem, ki spada v družino algoritmov za šifriranje z javnim ključem. Je prvi algoritem praktično primeren za podpisovanje in šifriranje z javnim ključem. RSA se na široko uporablja v protokolih, namenjenim komercialnim komunikacijam in velja kot varen, če je le dolžina ključev dovolj velika.

Zgodovina

Algoritem so leta 1977 opisali Ron Rivest, Adi Shamir in Len Adleman na MIT (Massachusetts Institute of Technology). Črke RSA so začetnice njihovih imen.

Clifford Cocks, britanski matematik zaposlen pri GCHQ (Government Communications Headquarters), je predstavil ekvivalenten sistem v notranjem dokumentu leta 1973. Predstavljen sistem bi potreboval relativno drage računalniške komponente, kar je povzročalo pomisleke in, kot je znano, se sistem ni razširil. Ponovno je bil sistem obravnavan leta 1997 in je bil razvrščen v razred stroge tajnosti.

MIT je algoritem patentiral leta 1983 v ZDA kot »U.S. Patent 4,4050,829«. Prenehal je veljati 21.9.2000. Do tega časa je bilo treba v ZDA plačevati licenčnino, zato algoritem ni bil vključen v nekatere produkte.

Postopek

• Predstavitev

RSA vsebuje dva ključa: javnega in zasebnega (ključ je konstantno število, ki ga kasneje uporabljamo v formuli za šifriranje). Javni ključ poznajo vsi in se uporablja za šifriranje sporočil. Sporočila lahko dešifriramo samo z zasebnim ključem. Z drugimi besedami: vsi lahko sporočilo zašifrirajo, prebere pa ga lahko samo lastnik zasebnega ključa.

Praktičen primer: oseba A pošlje osebi B škatlo z odprto ključavnico, za katero ima ključ samo oseba A. Oseba B prejme škatlo in vanjo položi sporočilo, napisano v preprostem jeziku. Škatlo zaklene s ključavnico osebe A in ji jo pošlje. Oseba B pošlje škatlo osebi A, kjer jo ta odpre s svojim ključem. V tem primeru je škatla s ključavnico javni ključ osebe A in ključ za to ključavnico je njen zasebni ključ.

• Kreiranje ključev

Predvidevamo, da osebi A in B komunicirata preko nezaščitenega prenosnega medija in oseba A želi osebi B poslati zasebno ali tajno sporočilo. Z uporabo RSA bo oseba A izvedla naslednje korake za kreiranje javnega in zasebnega ključa:

1. Izbere dve praštevili, p in q tako da velja $p\neq q$. Izbere ju tako, da sta naključni in neodvisni druga od druge.
2. Izračuna $n=pq\,$.
3. Izračuna koeficient $\phi (n)=(p-1)(q-1)\,$.
4. Izbere celo število e, tako da velja $1<e<\phi (n)\,$, ki je tuje številu $\phi (n)\,$
5. Izračuna $d$, tako da je $de\equiv 1{\pmod {\phi (n)}}$ To je $de=1+k\varphi (n)$ za celoštevilčno vrednot $k$.

• praštevila lahko s preizkušanjem predhodno testiramo
• korake 4 in 5 lahko izvedemo z razširjenim Evklidovim algoritmom
• korak 5 lahko izvedemo tudi z iskanjem celega števila x, s pomočjo katerega dobimo celo število, ki ga potem uporabimo za $\phi =(p-1)(q-1)\,$

Javni ključ je sestavljen iz:

• n, generator
• e, javni eksponent (šifrirni eksponent)

Zasebni ključ je sestavljen iz:

• n, generatorja, ki je javen in se pojavlja v javnem ključu
• d, zasebni eksponent (dešifrirni eksponent), ki mora ostati skriven.

Po navadi shranimo različno obliko zasebnega ključa (z upoštevanjem CRT parametrov)

• p in q sta praštevili iz kreiranega ključa
• d mod(p-1) in d mod (q-1) pogosto poznana kot dmp1 in dmq1

(1/q) mod p največkrat poznan kot iqmp

Ta oblika dovoljuje hitrejše dešifriranje in podpisovanje z uporabo kitajskega izreka o ostankih (CRT). V tej obliki morajo biti skriti vsi deli privatnega ključa.

Oseba A pošlje javni ključ osebi B , pri tem pa skrbi za tajnost zasebnega ključa. Vrednosti p in q sta občutljivi, ker sta faktorja n in omogočata izračun d s podanim e. Če p in q nista spravljena v CRT obliki zasebnega ključa, ju je potrebno varno izbrisati, prav tako, kot je potrebno izbrisati tudi ostale vrednosti, ki so bile ustvarjene pri računanju para javnega in skrivnega ključa.