[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 300 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 aed ≡ a (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, i to iz klase Las Vegas algoritama. To su algoritmi koji ne daju uvijek odgovor, ali kada ga daju, onda je odgovor sigurno točan. U slučaju da algoritam ne da odgovor, možemo mu dati novu nezavisnu šansu za nalaženje odgovora. Na taj se način vjerojatnost uspjeha algoritma povećava s količinom raspoloživog vremena. Druga klasa vjerojatnosnih algoritma su Monte Carlo algoritmi koji uvijek daju odgovor, ali on može biti netočan. Primjer takvog algoritma je Miller-Rabinov test za testiranje prostosti.


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 k ≤ j 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 qk ≥ Fk, 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)d ≡ x (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)d ≡ x (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 (q - p)/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 d ≤ n0.292. Savjet je da se izbjegava slučaj kada je d < √n jer je poznato da su svi ovi gore spomenuti napadi sasvim neprimjenjivi ako je d > √n. Zaključujemo da ideja korištenja malog eksponenta d za ubrzavanje dešifriranja nije dobra.


Prikazat ćemo sada jednu drugu ideju za ubrzavanje dešifriranja koju su predložili Quisquater i Couvreur 1982. godine. Standardni način za dešifriranje x = yd mod n zanemaruje činjenicu da (za razliku od korisnika koji šifrira otvoreni tekst) korisnik koji dešifrira poruku koja mu je namijenjena poznaje proste faktore p i q modula n. Stoga on može najprije "parcijalno" dešifrirati šifrat modulo p i modulo q tako da izračuna

xp = yd mod p,     xq = yd mod q,

pa zatim kombinirati ta dva rezultata s pomoću Kineskog teorema o ostatcima da dobije otvoreni tekst modulo n.

Postupak dešifriranja se može ubrzati ako uočimo da smo se umjesto eksponentom d mogli koristiti eksponentima dp i dq definiranima s

dp = d mod (p - 1),     dq = d mod (q - 1).

Naime, iz Malog Fermatovog teorema slijedi da je

xp = ydp mod p,     xq = ydq mod q.

Eksponenti dp i dq se nazivaju CRT-eksponenti. Vidjeli smo da eksponent za dešifriranje d ne bi smio biti manji od n0.292. S druge strane, čini se da nema prepreka da CRT-eksponenti budu znatno manji, a da to ne naruši sigurnost kriptosustava. Stoga se u situacijama kad se želi minimizirati trošak dešifriranja preporueuje korištenje ove verzije kriptosustava RSA, koja se naziva rebalansirani RSA, u kojoj se najprije izaberu mali CRT-eksponenti dp i dq, a zatim, s pomoću Kineskog teorema o ostatcima, izračuna odgovarajući eksponent za šifriranje e.


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:

c1 ≡ m3 (mod n1),   c2 ≡ m3 (mod n2),   c3 ≡ m3 (mod n3).

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

x ≡ c1 (mod n1),   x ≡ c2 (mod n2),   x ≡ c3 (mod n3).

Na taj način, dobit će broj x sa svojstvom x ≡ m3 (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