RSA

Izvor: Vidipedija
Skoči na: orijentacija, traži

Prvi, a ujedno i najpopularniji i najšire korišteni kriptosustav s javnim ključem je RSA kriptosustav koji su izumili Ron Rivest, Adi Shamir i Len Adleman 1977. godine. Njegova sigurnost je zasnovana na teškoći faktorizacije velikih prirodnih brojeva. Slijedi precizna definicija RSA kriptosustava. Neka je n = p . q, gdje su p i q prosti brojevi. Neka je = = , te

= { (n, p, q, d, e) : n = pq, p, q prosti, de  1 (mod (n)) }. 

Za K = (n, p, q, d, e) definiramo eK(x) = xe mod n i dK(y) = yd mod n, x, y .

Vrijednosti n i e su javne, a vrijednosti p, q i d su tajne.


Ovdje je (n) Eulerova funkcija, tj. broj brojeva u nizu 1, 2, ... , n koji su relativno prosti s n. U našem konkretnom slučaju je (n) = (pq) = (p - 1)(q - 1).

Uvjerimo se da su funkcije eK i dK jedna drugoj inverzne.

Imamo: dK(eK(x)) xde (mod n). Iz de 1 (mod (n)) slijedi da postoji prirodan broj t takav da je de = t (n) + 1. Sada je

xde = xt (n)+1 = [x(n)]t . x x (mod n)

ako je (n, x) = 1 (prema Eulerovom teoremu). Ako je (n, x) = n, onda je xde x 0 (mod n); ako je (n, x) = p, onda je xde x 0 (mod p) i xde = [xq-1](p-1)t . x x (mod q), pa je xde x (mod n); slučaj (n, x) = q je potpuno analogan. Prema tome, zaista je xde x (mod n), što znači da je dK(eK(x)) = x. Primjer 1: Uzmimo p = 3 i q = 11. Tada je n = 33 i (n) = 20. Eksponent e mora biti relativno prost s 20, pa recimo da je e = 7. Tada je d = 3. Sada je (n, e) = (33, 7) naš javni ključ. Pretpostavimo da nam netko želi poslati poruku x = 17. To znači da treba izračunati eK(x) = 177 mod 33:

177 = 17 . 172 . 174 17 . 25 . (-2) -25 8 (mod 33).

Dakle, šifrat je y = eK(x) = 8. Kad primimo ovaj šifrat, dešifriramo ga pomoću tajnog ključa d: x = dK(y) = 83 = 8 . 82 8 . (-2) 17 (mod 33).

Dakle, x = 17.

Sigurnost RSA leži u pretpostavci da je funkcija eK(x) = xe mod n jednosmjerna. Dodatni podatak (trapdoor) koji omogućava dešifriranje je poznavanje faktorizacije n = pq, jer je tada lako izračunati (n) = (pq) = (p - 1)(q - 1), te dobiti eksponent d iz de 1 (mod (n)), pomoću Euklidovog algoritma.

Opišimo sada postupak kojim korisnik izabire parametre u RSA kriptosustavu malo detaljnije.

Izabiremo tajno dva velika prosta broja p i q od oko 100 znamenaka, tako da q ima nekoliko znamenaka više od p. To radimo tako da pomoću nekog generatora slučajnih brojeva generiramo prirodan broj m s traženim brojem znamenaka, a zatim korištenjem nekog testa za testiranje prostosti (opisat ćemo ih u sljedećem poglavlju) tražimo prvi prosti broj veći ili jednak m. Po teoremu o distribuciji prostih brojeva, možemo očekivati da ćemo trebati testirati O(log m) brojeva dok ne nađemo prvi prosti broj.

Izračunamo n = pq i (n) = (p - 1)(q - 1) = n + 1 - p - q. (Za to nam treba O(log2 n) operacija.)

Izaberemo na slučajan način broj e takav da je e < (n) i ((n), e) = 1. To se može napraviti slično kao pod 1. Nakon toga tajno izračunamo d tako da je de 1 (mod (n)), tj. d e-1 (mod (n)). To se radi pomoću Euklidovog algoritma i za to nam treba O(log3 n) operacija.

Stavimo ključ za šifriranje (n, e) u javni direktorij. Za efikasnost RSA kriptosustava, važna je činjenica da se modularno potenciranje može izvesti vrlo efikasno. Podsjetimo se kako se efikasno računa eK(x) = xe mod n. To se radi tzv. metodom "kvadriraj i množi". Najprije e prikažemo u bazi 2:

e = e0 + 2 . e1 + ... + 2s -1 . es -1,

a potom primijenimo sljedeći algoritam:

   y = 1 
   za i = s -1, ... , 1, 0 
           y = y2 mod n 
           ako je ei = 1, onda y = y . x mod n  


Očito je ukupan broj množenja 2s, pa je ukupan broj operacija O(log e . log2 n). To znači da je ovaj algoritam polinomijalan.

Općenito, za algoritam koji kao ulazne podatke ima prirodne brojeve x1, ... , xm s redom k1, ... , km bitova kažemo da je polinomijalan ako mu je broj operacija O(k1d1, ... , kmdm), tj. O((log x1)d1, ... , log(xm)dm) za neke cijele brojeve d1, ... , dm.