RSA

Iz Wikipedije, proste enciklopedije

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 in ena prvih prednosti šifriranja 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.

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

[uredi] 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 . Izbere ju tako, da sta naključni in neodvisni druga od druge.
2. Izračuna .
3. Izračuna koeficient .
4. Izbere celo število e, tako da velja , ki je relativno praštevilo številu
5. Izračuna d, tako da je

• praštevila lahko s preizkušanjem predhodno testiramo
• korake 4 in 5 lahko izvedemo z razširjenim Euclidean-ovim algoritmom
• korak 5 lahko izvedemo tudi z iskanjem celega števila x, s pomočjo katerega dobimo celo število , ki ga potem uporabimo za

Javni ključ je sestavljen iz:

• n, generator
• e, zasebni eksponent (včasih eksponent šifriranja)

Zasebni ključ je sestavljen iz:

• n, generatorja, ki je javen in se pojavlja v javnem ključu
• d, zasebna komponenta (včasih komponenta dešifriranja), ki mora ostati tajna

Ponavadi 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 teorema kitajskih ostankov (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. p in q sta občutljiva, 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, sta varno izbrisana, prav tako, kot so izbrisane tudi ostale vrednosti, ki so bile ustvarjene pri računanju javnega ključa.