3.2. RSA kriptosustav

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, y ∈ Zn. 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 e_K i d_K jedna drugoj inverzne.

Imamo: d_K(e_K(x)) ≡ x^de (mod n). Iz de ≡ 1 (mod φ(n)) slijedi da postoji prirodan broj t takav da je de = t φ(n) + 1. Sada je

x^de = x^{t φ(n)+1} = [x^φ(n)]^{t .} x ≡ x (mod n)

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 e_K(x) = 17⁷ mod 33:

17⁷ = 17 ^. 17^{2 .} 17⁴ ≡ 17 ^. 25 ^. (-2) ≡ -25 ≡ 8 (mod 33).

x = d_K(y) = 8³ = 8 ^. 8² ≡ 8 ^. (-2) ≡ 17 (mod 33).

Sigurnost RSA leži u pretpostavci da je funkcija e_K(x) = x^e 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 150 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(log² 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(log³ 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 e_K(x) = x^e mod n. To se radi tzv. metodom "kvadriraj i množi". Najprije e prikažemo u bazi 2:

e = e₀ + 2 ^. e₁ + ... + 2^{s -1 .} e_{s -1},

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 · log² n). To znači da je ovaj algoritam polinomijalan.

Općenito, za algoritam koji kao ulazne podatke ima prirodne brojeve x₁, ... , x_m s redom k₁, ... , k_m bitova kažemo da je polinomijalan ako mu je broj operacija O(k₁^d1 · ... · k_m^dm), tj. O((log x₁)^d1 · ... · log(x_m)^dm) za neke nenegativne cijele brojeve d₁, ... , d_m.