[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]

3.2. RSA kriptosustav

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 P = C = Zn, te

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

Za K = (n, p, q, d, e) ∈ K definiramo

eK(x) = xe mod n   i   dK(y) = yd mod n,   x, yZn.

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 . xx (mod n)

ako je (n, x) = 1 (prema Eulerovom teoremu).
Ako je (n, x) = n, onda je xdex ≡ 0 (mod n); ako je (n, x) = p, onda je xdex ≡ 0 (mod p) i xde = [xq-1](p-1)t . xx (mod q), pa je xdex (mod n); slučaj (n, x) = q je potpuno analogan. Prema tome, zaista je xdex (mod n), što znači da je dK(eK(x)) = x.

Primjer 3.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.

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

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

  3. 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.

  4. 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.


[Prethodno poglavlje]   [Sljedeće poglavlje]   [Sadržaj]
Web stranica kolegija Kriptografija Andrej Dujella - osobna stranica