Algoritmul RSA

1. Introducere

Algoritmul RSA a fost publicat pentru prima oară în 1977 de R. Rivest, A. Shamir şi L. Adleman în revista “Scientific American” şi se compune din calcule numerice în inelul Sistemele de tipul RSA fac parte din categoria sistemelor criptografice cu cheie publică. Securitatea algoritmului se bazează pe problema factorizării numerelor foarte mari. Algoritmul poate fi utilizat atât pentru criptare, cât şi pentru autentificare (semnături digitale) şi este foarte larg răspândit la ora actuală. El este întâlnit în servere şi browsere de web, în clienţi şi servere de e-mail, reprezentând practic coloana vertebrală a sistemului de plăţi electronice prin card-uri de credit.

Algoritmul funcţionează după cum urmează:

- Se generează două numere prime p şi q, de lungime 2n biţi (de exemplu 512, 1024, 2048 biţi lungime). Deoarece mulţimea numerelor prime este suficient de densă, numerele prime pot fi generate alegând aleator numere întregi de 2 n biţi şi testându-le cu ajutorul unui test probabilistic. Apoi, fie N=p*q, de lungime n biţi.

- Numărul e trebuie ales astfel încât să îndeplinească următoarele condiţii: 1 < e < N iar e şi (p - 1) * (q - 1) să fie relativ prime, sau altfel spus, să nu aibă factori primi în comun.

- Se calculează d cu ajutorul algoritmului euclidian extins, astfel încât acesta să fie multiplul invers al lui e sau altfel spus d * e - 1 să fie divizibil cu (p-1) * (q-1). În practică, d se

poate obţine foarte simplu căutând rezolvarea ecuaţiei astfel încât d şi x să fie numere întregi. Valorile d şi e sunt numite exponentul privat, respectiv exponentul public al algoritmului.

- Funcţia de criptare/semnare arată astfel: , unde M reprezintă mesajul de criptat (un întreg pozitiv mai mic decât N).

- Funcţia de decriptare/verificare arată astfel: , unde C reprezintă textul criptat. Cheia publică este reprezentată de perechea (N, e), iar cheia privată de perechea (N, d). Numărul d mai este cunoscut şi sub numele de “trap door”, deoarece cunoaşterea sa permite inversarea rapidă a funcţiei RSA.

Viteza algoritmului RSA depinde în mare măsură de lungimea cheilor utilizate, de tipul de implementare, de procesorul pe care se rulează aplicaţia, dar şi de protocolul ce trebuie implementat. Deseori, pentru a obţine o viteză sporită în aplicaţiile practice, sunt utilizaţi exponenţi publici mici, acest fapt implicând însă şi riscuri corespunzătoare. Există chiar grupuri întregi de utilizatori care folosesc acelaşi exponent public, doar modulul N fiind

diferit. În acest caz există însă reguli stricte ce trebuiesc respectate pentru cele două numere prime p şi q, astfel încât siguranţa algoritmului să nu fie periclitată. Utilizând, cum spuneam, exponenţi publici mici, se obţine o viteză mai mare de criptare şi verificare în comparaţie cu procesele inverse de decriptare şi semnare a datelor. Utilizând algoritmii generali de calcul ai exponenţialului, operaţiile cu cheie publică consumă un timp proporţional cu O(n²), iar operaţiile cu cheie privată necesită aproximativ O(n³), unde n reprezintă numărul de biţi ai lui N. Tehnicile de multiplicare rapidă, necesită de obicei mai puţini paşi, sunt însă destul de rar folosite datorită complexităţii lor, şi a faptului că pentru lungimi tipice de chei, ele sunt totuşi mai lente. Dacă comparăm viteza algoritmului RSA cu cea a unui algoritm cu cheie simetrică (DES de exemplu), putem observa că în funcţie de implementare (HW sau SW) cel din urmă este cu până la aproximativ 1000 de ori mai rapid decât RSA. Cu toate acestea, utilizarea RSA în algoritmi de distribuire de chei (simetrice) sau în alte aplicaţii, în care viteza este mai puţin importantă, prezintă avantaje de netăgăduit.

Securitatea sistemelor RSA se bazează pe presupunerea că funcţia este

unidirecţională, fiind computaţional dificil de a se găsi mesajul iniţial M în absenţa exponentului de decriptare d. Există însă posibilitatea, cel puţin teoretică, de a încerca factorizarea lui N prin metoda forţei brute sau prin alte metode, fapt ce ar duce la aflarea numerelor p şi q. Apoi utilizând algoritmul euclidian extins se poate calcula exponentul de decriptare d, ceea ce ar duce la compromiterea cheii private şi la descifrarea textului criptat. Încă de la publicarea sa, algoritmul RSA a fost studiat de o mulţime de cercetători, fiind supus la nenumărate teste. Cu toate că de-a lungul celor mai bine de 25 de ani de utilizare au rezultat diverse vulnerabilităţi, algoritmul s-a dovedit suficient de rezistent (până în prezent) pentru a putea oferi un grad ridicat de securitate. Metodele de atac rezultate nu fac decât să ilustreze încă o dată pericolul utilizării RSA în condiţii necorespunzătoare, programarea unei versiuni sigure de RSA nefiind deloc o problemă simplă.

2. Metode de analiză şi atac. O clasificare generală a acestora.

Dificultatea de a inversa funcţia RSA pentru mesaje aleatoare duce la concluzia că, dat fiind tuplul (N, e, C), un atacator nu va putea obţine mesajul criptat M. Cu toate acestea, se pot obţine diverse informaţii despre M, astfel încât RSA nu este un sistem sigur din punct de vedere semantic (date fiind N, e, C, se pot obţine relativ uşor proprietăţi ale lui M – de exemplu simbolul Jacobi al lui M peste N). RSA poate fi făcut însă sigur din punct de vedere semantic dacă se adaugă informaţie aleatoare în procesul de criptare [1].

O clasificare a metodelor de atac este relativ dificil de făcut, cu toate acestea se poate aborda problema din două direcţii. În primul rând se poate încerca clasificarea metodelor de atac după impactul pe care îl au asupra algoritmului. Astfel, se pot identifica două categorii de atacuri:

- atacuri ce compromit cheia privată, compromiţând practic întreaga securitate a sistemului;

- atacuri ce compromit un singur mesaj criptat, cheia privată putând fi însă utilizată în continuare.

Din prima categorie putem enumera metoda forţei brute, atacul exponentului privat mic etc. Atacurile din cea de a doua categorie sunt în general mult mai subtile, folosind metode relativ complicate de aflare a mesajului. Cu toate acestea, timpul utilizat pentru aflarea unui mesaj trebuie să fie mult mai mic decât timpul necesar metodei forţei brute, pentru ca atacul să aibă o anumită relevanţă. Totodată sunt importante şi condiţiile ce trebuiesc îndeplinite astfel încât metoda să poată fi aplicată. O altă metodă de a aborda o eventuală clasificare a metodelor de analiză şi atac o reprezintă impărţirea acestora pe categorii după proprietăţile utilizate în cadrul atacului. Putem enumera astfel:

- metode elementare de atac;

- metoda exponentului privat mic;

- metodele exponentului public mic;

- atacuri îndreptate împotriva diverselor implementări.

3. Factorizarea numerelor întregi

O metodă de a ataca algoritmul RSA este aceea de a încerca factorizarea modulului N.

Aceasta mai este numită şi metoda forţei brute. Dacă factorizarea lui N reuşeşte, este foarte

simplu de a se calcula apoi (p-1)*(q-1) şi de a se găsi exponentul de decriptare. În practică aceasta însemnă compromiterea cheii private, permiţând atacatorului atât citirea mesajelor, cât şi falsificarea semnăturilor. O perioadă de timp s-a crezut că securitatea RSA este direct proporţională cu problema factorizării numerelor prime, dar cercetări recente au dezvăluit faptul că “spargerea” unui sistem RSA nu este echivalentă cu factorizarea lui N. Cu alte cuvinte, s-a dovedit că a “sparge” un sistem RSA cu exponent privat mic este mai simplă decât rezolvarea problemei factorizării lui N. Aceasta însă nu însemnă neapărat găsirea unei vulnerabilităţi a algoritmului [2]. Securitatea RSA ar fi puternic afectată dacă s-ar reuşi găsirea unei metode uşoare de factorizare a numerelor mari şi foarte mari. Doar avansurile tehnologice în domeniul hardware (în particular viteza crescută de procesare) nu pot duce la o ameninţare reală a algoritmului, deoarece prin alegerea unor chei cu lungime tot mai mare, această problemă se rezolvă de la sine. De notat este şi faptul că algoritmul cel mai rapid de factorizare este “General Number Field Sieve”, care rulează pe numere de n biţi lungime în , unde c < 2.