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

3.3. Kriptoanaliza RSA kriptosustava

Jedan očit napad na RSA je faktorizacija od n. Ako napadač faktorizira n, onda može naći φ(n) i d. Metodama faktorizacije ćemo se detaljno pozabaviti u sljedećem poglavlju, a za sada recimo samo da trenutno najbrži algoritmi za faktorizaciju trebaju

exp(O((log n)1/3 (log log n)2/3))

operacija, tako da su brojevi od preko 200 znamenaka za sada sigurni od ovog napada. Dakle, nije poznat niti jedan polinomijalni algoritam za faktorizaciju. Ovdje ipak treba reći da je u nekim slučajevima n puno lakše faktorizirati, pa takve n-ove treba izbjegavati. Takav je slučaj npr. ako su p i q jako blizu jedan drugoga ili ako p -1 i q -1 imaju samo male proste faktore.

Važno je napomenuti da ako napadač otkrije tajni eksponent d, onda nije dovoljno promijeniti samo eksponent e, već moramo promijeniti i n.
Zaista, ako je poznat broj d takav da je aeda (mod n) za sve a, (a,n) = 1, onda za broj m = ed - 1 vrijedi am ≡ 1 (mod n) za sve a, (a,n) = 1. Kako je grupa svih reduciranih ostataka modulo p ciklička, ovo je ekvivalentno tome da je m zajednički višekratnik od p - 1 i q - 1. Dakle, poznavanje broja m je slabije od poznavanja broja φ(n) = (p - 1)(q - 1). Pokazat ćemo kako pomoću m možemo (s velikom vjerojatnošću) faktorizirati n.

Uvrštavanjem a = -1 vidimo da je m paran. Provjerimo da li m/2 zadovoljava isto svojstvo kao m. Ako postoji a za koji nije am/2 ≡ 1 (mod n), (a,n) = 1, onda takvih a-ova ima barem 50%. Zaista, svakom broju b koji zadovoljava kongruenciju bm/2 ≡ 1 (mod n), odgovara broj ab koji tu kongruenciju ne zadovoljava. Stoga, ako testiramo nekoliko desetaka a-ova i ako svi oni zadovoljavaju am/2 ≡ 1 (mod n), onda s velikom vjerojatnošću možemo m zamijeniti s m/2. Nastavljamo ovo dijeljenje s 2 dokle god je to moguće. Na kraju imamo dvije mogućnosti:

1) m/2 je višekratnik od p - 1, a nije od q - 1 (ili obrnuto). Tada je am/2 ≡ 1 (mod p) uvijek, ali je am/2 ≡ -1 (mod q) u 50% slučajeva (ako je c generator cikličke grupe Fq*, onda je am/2 ≡ 1 (mod q) za a = c2k, dok je am/2 ≡ -1 (mod q) za a = c2k+1);

2) m/2 nije višekratnik ni od p - 1 ni od q -1. Tada je am/2 ≡ ± 1 (mod p), am/2 ≡ ± 1 (mod q) i svaka od četiri mogućnosti nastupa u 25% slučajeva.

Dakle, za proizvoljan a s vjerojatnošću 50% imamo da je am/2 - 1 djeljiv s jednim od brojeva p i q, a nije djeljiv s drugim. Uzimajući slučajno nekoliko desetaka a-va, možemo s vrlo velikom vjerojatnošću očekivati da ćemo pronaći a s gornjim svojstvom. Recimo da je am/2 - 1 djeljiv s p, a nije s q. Tada je (n, am/2 - 1) = p i mi smo uspjeli faktorizirati n.

Upravo opisani algoritam za faktorizaciju je primjer tzv. vjerojatnosnog algoritma.


Na prvi pogled ne čini se lošom ideja da izbjegnemo generiranje različitih modula n = pq, već da izaberemo jedan "dobar" n jednom za svagda. Taj n bi koristili svi korisnici, a iz jednog povjerljivog centra bi se korisnicima distribuirali parovi eK, dK iz kojih bi oni onda formirali svoje javne (n,eK) i tajne (n, dK) ključeve. Međutim, ideja je loša jer bi rezultirala nesigurnim sustavom i to upravo zbog gore opisanog vjerojatnosnog algoritma. Naime, korisnik A bi pomoću tog algoritma te njegovih eksponenata eA i dA mogao faktorizirati n. Nakon toga bi A lako, poznavajući faktore od n i javni ključ eB, mogao izračunati tajni ključ dB bilo kojeg drugog korisnika.
Ova primjedba pokazuje da jedan RSA modul ne bi smjelo koristiti više korisnika.


Sljedeća, također samo na prvi pogled dobra, ideja je da pokušamo izabrati mali d. Budući da je broj operacija za modularno potenciranje linearan u log d, to bi moglo smanjiti vrijeme potrebno za dešifriranje. Međutim, sljedeći teorem M. Wienera iz 1990. godine pokazuje da izbor malog d dovodi do lakog razbijanja šifre.

Teorem 1: Neka je n = pq i p < q < 2p, te neka je d < 1/3 n0.25. Tada postoji polinomijalni algoritam koji iz poznavanja n i e izračunava d.

Dokaz: Iz ed ≡ 1 (mod φ(n)) slijedi da postoji prirodan broj k takav da je ed - kφ(n) = 1. Odavde je

           e          k         1
       | -----   -   --- | = ------- .
          φ(n)        d      d φ(n)  
Dakle, k/d je dobra aproksimacija od e/φ(n). Međutim, mi ne znamo φ(n). Stoga ćemo φ(n) zamijeniti s n. Iz φ(n) = n - p - q + 1 i p + q - 1 < 3 √n slijedi |n - φ(n)| < 3 √n. Zamijenimo φ(n) s n, pa dobivamo:
    e     k        ed-kφ(n)-kn+kφ(n)       1-k(n-φ(n))       3k√n      3k 
 | --- - --- | = | ------------------ | = | ----------- | ≤ ------ = ----- .
    n     d               nd                    nd            nd      d√n
Sada je kφ(n) = ed - 1 < ed, pa iz e < φ(n), što je zadovoljeno u standardnoj verziji RSA kriptosustava, slijedi k < d < 1/3 n0.25, te dobivamo

    e     k        1       1
 | --- - --- | ≤ ------ < --- .                   (1)
    n     d      d n0.25   2d2
Iz teorije diofantskih aproksimacija slijedi da relacija (1) povlači da je k/d neka konvergenta razvoja u verižni razlomak od e/n. Podsjetimo se da razvoj u verižni razlomak racionalnog broja b/c izgleda ovako
  b                 1 
 --- = a0 + ----------------- = [a0, a1, ... , aj],
  c          a1 + 
                  .
                    .
                      .    1
                        + --- 
                           aj
gdje su a0, ... , aj kvocijenti iz Euklidovog algoritma primijenjenog na b i c. Razlomke oblika pk/qk = [a0, a1, ... , ak] za kj nazivamo konvergente verižnog razlomka. Vrijedi

p0 = a0,   q0 = 1,   p1 = a0a1 + 1,   q1 = a1,
pk = akpk -1 + pk -2 ,   qk = akqk -1 + qk -2.

Odavde odmah slijedi da je qkFk, gdje je Fk k-ti Fibonaccijev broj. To znači da nazivnici konvergenti rastu eksponencijano.
U našem slučaju to povlači da ima O(log n) konvergenti od e/n. Jedna od njih je k/d. Dakle, izračunamo sve konvergente od e/n i testiramo koja od njih zadovoljava (xe)dx (mod n) za slučajno odabran broj x. To daje polinomijalni algoritam za otkrivanje tajnog ključa d.


Drugi način za testiranje pretpostavke da je neka konkretna konvergenta jednaka k/d, jest da se, uz tu pretpostavku, izračuna φ(n) = (p - 1)(q - 1) = (ed - 1)/k. Tada se može izračunati (p + q)/2 iz identiteta

(pq - (p - 1)(q - 1) + 1)/2 = (p + q)/2 ,

te (q - p)/2 iz identiteta ((p + q)/2)^2 - pq = ((q - p)/2)^2. Ako se na ovaj način dobije da su brojevi (p + q)/2 i (q - p)/2 cijeli, onda zaključujemo da je promatrana konvergenta stvarno jednaka k/d. Tada se iz (p + q)/2 i (q - p)/2 možemo lako dobiti i faktorizaciju modula n = pq.


Primjer 3.2: Pretpostavimo da je u RSA kriptosustavu modul n = 7978886869909, javni eksponent e = 3594320245477, te da je poznato da tajni eksponent d zadovoljava d < 1/3 n0.25 < 561. Da bi primijenili Wienerov napad, računamo razvoj broja e / n u verižni razlomak. Dobivamo:

[0, 2, 4, 1, 1, 4, 1, 2, 31, 21, 1, 3, 1, ... ].

Potom računamo pripadne konvergente:

0, 1/2, 4/9, 5/11, 9/20, 41/91, 50/111, 141/313, 4421/9814, ... .

Konačno, provjeravamo koji od nazivnika 2, 9, 11, 20, 91, 111, 313 zadovoljava kongruenciju (xe)dx (mod n) za npr. x = 2. Tako dobivamo da je tajni eksponent d = 313.

Drugom metodom provjere dobivamo najprije da je (p - 1)(q - 1) = (ed - 1)/k = 7978881112300, zatim (p + q)/2 = (n - (p - 1)(q - 1) + 1)/2 = 2878805, te (p - q)/2 = 555546. Ovime smo ponovno provjerili da je tajni eksponent d = 313, a dobili smo i faktore od n: to su p = 2878805 - 555546 = 2323259 i q = 2878805 + 555546 = 3434351.


Postoje i nešto jači rezultati od Teorema 1. Dujella je primjenom rezultata o karakterizaciji dobrih racionalnih aproksimacija pomoću vezižnih razlomaka Wienerov napad proširio do d ≤ 230n0.25, dok su Boneh i Durfee pomoću LLL-algoritma proširili Wienerov napad do slučaja kada je dn0.292. Čini se da bi trebalo izbjegavati slučaj kada je d < √n da bi bili sigurni od napada koji koriste rezultate i algoritme iz diofantskih aproksimacija.


Također postoje i napadi na RSA uz pretpostavku da je eksponent e mali, pa bi i to trebalo izbjegavati. U ranijim implementacijama RSA kriptosustava, često se uzimalo e = 3, da bi se minimiziralo vrijeme potrebno za šifriranje. Pokazat ćemo zašto taj izbor za e nije dobar.

Pretpostavimo da imamo tri korisnika s različitim vrijednostima javnog modula n1, n2, n3, te pretpostavimo da svi oni koriste isti javni eksponent e = 3. Nadalje, pretpostavimo da im netko želi poslati identičnu poruku m. Tada njihov protivnik može doznati sljedeće šifrate:

c1m3 (mod n1),   c2m3 (mod n2),   c3m3 (mod n3).

Nakon toga, on može, koristeći Kineski teorem o ostatcima, naći rješenje sustava linearnih kongruencija

xc1 (mod n1),   xc2 (mod n2),   xc3 (mod n3).

Na taj način, dobit će broj x sa svojstvom xm3 (mod n1n2n3). No, kako je m3 < n1n2n3, to zapravo vrijedi x = m3, pa protivnik može izračunati originalnu poruku m vadeći treći korijen iz x.


Primjer 3.3: Za ilustraciju ovog napada, pretpostavimo da je n1 = 329, n2 = 341, n3 = 377. Pretpostavimo da je protivnik saznao šifrate c1 = 43, c2 = 30, c3 = 372, te želi saznati zajednički otvoreni tekst m. Rješavanjem sustava

x ≡ 43 (mod 329),   x ≡ 30 (mod 341),   x ≡ 372 (mod 377),

pomoću Kineskog teorema o ostatcima, dobiva se da je

x ≡ 341 · 377 · 172 + 329 · 377 · 232 + 329 · 341 · 317 ≡ 86451373 ≡ 1860867 (mod 329 · 341 · 377).

To znači da je x = 1860867 i m = x1/3 = 123.


Upravo opisani napad može se izbjeći tako da se porukama prije šifriranja doda neki "slučajni dodatak". Na taj način, nikad nećemo različitim primateljima slati potpuno identične poruke. No, postoje napadi koji pokazuju da ni u tom slučaju RSA kriptosustav s vrlo malim eksponentom e nije siguran. Može se preporučiti uporaba eksponenta e = 65537, koji je dovoljno velik da bi onemogućio sve poznate napade na RSA s malim eksponentom, a ima prednost da je šifriranje s njim vrlo brzo jer ima malo "jedinica" u binarnom zapisu. Naime, 65537 = 216 + 1.


Možemo zaključiti da i nakon više od dva desetljeća intenzivnog proučavanja, još uvijek nije pronađena metoda koja bi razbila RSA kriptosustav. Svi poznati napadi na RSA zapravo samo pokazuju na što treba paziti i što treba izbjegavati kod izbora parametara i implementacije RSA. Za sada se uz korektnu implementaciju RSA može smatrati sigurnim kriptosustavom.


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