Algoritmul de criptografie RSA

Articol postat de:

RSA

In criptografie, RSA este un algoritm criptografic cu chei publice, primul algoritm utilizat atat pentru criptare, cat si pentru semnatura electronica. Algoritmul a fost dezvoltat in 1977 si publicat in 1978 de Ron Rivest, Adi Shamir si Leonard Adleman la MIT si isi trage numele de la initialele numelor celor trei autori.

Puterea sa criptografica se bazeaza pe dificultatea problemei factorizarii numerelor intregi, problema la care se reduce criptanaliza RSA si pentru care toti algoritmii de rezolvare cunoscuti au complexitate exponentiala. Exista insa cateva metode de criptanaliza care ocolesc factorizarea efectiva, exploatand maniere eronate de implementare efectiva a schemei de criptare.

Functionare

RSA este un algoritm de criptare pe blocuri. Aceasta inseamna ca atat textul clar cat si cel cifrat sunt numere intre 0 si n-1, cu un n ales. Un mesaj de dimensiune mai mare decat log n este impartit in segmente de lungime corespunzatoare, numite blocuri, care sunt cifrate rand pe rand. De asemenea, ca algoritm criptografic cu chei publice, functioneaza pe baza unei perechi de chei legate matematic intre ele: o cheie publica, cunoscuta de toata lumea, si una secreta, necunoscuta decat de detinatorul acesteia.

Generarea cheilor

Perechea de chei se genereaza dupa urmatorii pasi:

  1. Se genereaza doua numere prime, de preferat mari, p si q;
  2. Se calculeaza n = pq si Φ = (p-1)(q-1)
  3. Se alege un intreg aleator e, 1 < e < Φ astfel incat cmmdc(e, Φ) = 1. Perechea (n, e) este cheia publica.
  4. Folosind algoritmul lui Euclid extins, se calculeaza intregul d, unicul cu proprietatea ca de ≡ 1mod Φ. (n, d) constituie cheia secreta.

Decizia cu privire la care dintre e si d este cheia publica si care este cea secreta este, din punct de vedere matematic, arbitrara, oricare dintre cele doua numere poate juca oricare dintre roluri. In practica insa, pentru a mari viteza de criptare, si intrucat dintre cele doua numere eeste cel ales arbitrar, e este cheia publica iar valoarea sa este aleasa un numar mic, de regula 3, 17 sau 65537 (216+1). Aceasta conduce la un numar minim de inmultiri, deci la o performanta sporita, deoarece toate aceste numere au doar doua cifre 1 in reprezentarea lor binara.

Criptarea si decriptarea

Presupunand ca mesajul clar este sub forma unui numar m, mai mic decat n, atunci mesajul cifrat, notat cu c este

c = me (mod n)

unde e este cheia publica a destinatarului mesajului. Pentru a decripta mesajul, destinatarul isi foloseste cheia sa secreta d, care are proprietatea foarte importanta ca:

de ≡ 1 mod Φ

Astfel, mesajul clar este recuperat calculand:

m = cd (mod n)

Oricine poate cripta mesaje cu cheia publica a destinatarului, dar numai acesta din urma poate decripta, deoarece trebuie sa foloseasca cheia sa secreta.

Algoritmul poate fi folosit si pentru semnatura electronica, folosind cheile invers. Daca o entitate cripteaza un mesaj (sau mai degraba un hash al acestuia) cu cheia sa secreta si ataseaza rezultatul mesajului sau, atunci oricine poate verifica, decriptand cu cheia publica a semnatarului si comparand rezultatul cu mesajul clar (sau cu hash-ul acestuia), ca intr-adevar acea entitate este autorul mesajului.

Demonstratia formulei de decriptare

Formula de decriptare este valabila, deoarece:

cd mod n = med mod ned ≡ 1 (mod Φ) si, fiindca Φ = (p – 1)(q -1), atuncied ≡ 1 (mod p – 1) sied ≡ 1 (mod q – 1)

si deci se poate scrie:

ed = k (p – 1) + 1ed = h (q – 1) + 1

Dar, cum p este prim, si deci prim cu m, conform micii teoreme a lui Fermat, rezulta ca

mp-1 ≡ 1 (mod p)

Astfel,

med = mk(p-1)+1 = (mp-1)km = 1km = m.

Daca p nu este totusi prim cu m, atunci inseamna ca m este multiplu al lui p, caz trivial in care m este congruent cu 0 modulo p, si deci ridicat la orice putere este congruent cu 0 si deci cu el insusi.

Analog si pentru q, med ≡ m (mod q)

De aici, conform teoremei chinezesti a resturilor, deoarece p si q sunt numere prime, rezulta ca

med ≡ m (mod pq)

Performante in implementari

In general, deoarece se bazeaza pe o operatie destul de costisitoare din punct de vedere al timpului de calcul si al resurselor folosite, si anume exponentierea modulo n, viteza RSA este mult mai mica decat a algoritmilor de criptare cu cheie secreta. Bruce Schneier estima, pe baza unor calcule efectuate in anii 1990, ca o implementare hardware de RSA este de 1000 de ori mai lenta decat o implementare DES, iar in software, RSA este de 100 de ori mai lent.

Exista anumite modificari care pot aduce performante sporite, precum alegerea unui exponent de criptare mic, care astfel reduce calculele necesare criptarii, rezolvand in acelasi timp si unele probleme de securitate. De asemenea, operatiile cu cheia secreta pot fi accelerate pe baza teoremei chinezesti a resturilor, daca se stocheaza pq si unele rezultate intermediare, folosite des. Cu toate acestea, imbunatatirile nu sunt mari, iar ordinul de marime al diferentelor de performanta fata de implementarile algoritmilor cu cheie secreta ramane acelasi. De aceea, in sistemele de comunicatie in timp real, in care viteza de criptare si decriptare este esentiala (cum ar fi, de exemplu, aplicatiile de streaming video sau audio securizate), RSA se foloseste doar la inceputul comunicatiei, pentru a transmite cheia secreta de comunicatie, care ulterior este folosita intr-un algoritm cu cheie secreta, cum ar fi 3DES sau AES.

Securitatea

Problema decriptarii unui mesaj criptat cu RSA este denumita problema RSA. Aceasta consta in obtinerea radicalului de ordin e modulo n, undee si n au proprietatea ca n este produsul a doua numere prime mari p siq, iar e este prim cu produsul dintre p-1 si q-1. In acest moment, cea mai eficienta metoda de a realiza aceasta este descompunerea in factori primi a lui n, si obtinerea astfel a cheii secrete d pe baza lui e. Astfel, este demonstrat ca dificultatea spargerii unui mesaj criptat cu RSA nu este mai dificila decat problema factorizarii. Nu a fost descoperita inca o alta solutie generala a problemei RSA, dar nici nu s-a demonstrat matematic ca nu exista o alta solutie.

Factorizarea intregilor prin metodele comune ajuta la gasirea solutiilor in timp util doar pentru numere mici. Pentru numere mari, algoritmii de factorizare, cu complexitate exponentiala, dau solutia dupa foarte mult timp. Cea mai rapida metoda de factorizare a intregilor, algoritmul general al ciurului campurilor de numere, are o complexitate de o(ec((log n)1/3(log log n )2/3). Aici, c este un numar ce ia valori in jur de 1,9 pentru numere de tipul lui n, adica numere cu doi factori primi. Cel mai mare numar factorizat vreodata prin acest algoritm, rulat in anul 2005, de catre specialisti de la Agentia Federala Germana pentru Securitatea Tehnologiei Informatiei, are 200 de cifre zecimale, iar reprezentarea binara a factorilor primi obtinuti ocupa 663 de biti.Cheile de criptare RSA cele mai sigure au lungimi de peste 1024 de biti.

Atacul RSA prin metoda fortei brute, adica incercarea fiecarei chei secrete posibile, consuma chiar mai mult timp decat factorizarea.

Atacuri impotriva RSA

Desi securitatea algoritmului RSA consta in legatura dintre acesta si factorizarea intregilor, el trebuie folosit cu grija in implementari, deoarece, in caz de folosire eronata, sistemele bazate pe RSA pot fi atacate in anumite maniere care ocolesc factorizarea efectiva a modulului, atacatorul ajungand sa obtina mesajul clar sau cheia secreta.

Atac cu text cifrat ales

In cazul atacului cu text cifrat ales, atacatorul dispune de cheia publica a entitatii atacate (exponentul de criptare e si modulul n), si intercepteaza mesaje cifrate trimise acestuia. Pentru a obtine mesajul clar m dintr-un mesaj cifrat c, atacatorul poate proceda, de exemplu, astfel:

  1. Calculeaza x = ( 2ec ) (mod n)
  2. Trimite entitatii atacate spre semnare pe x, obtinand y = xd (mod n)
  3. Se observa ca x = 2ec (mod n) = 2eme (mod n) = (2m)e (mod n)
  4. Se rezolva ecuatia y = (2m)(mod n)

Atacatorul obtine astfel mesajul cifrat. Exista mai multe feluri de atacuri cifrate, dar sunt cateva moduri de aparare impotriva lor. Unele pot fi evitate daca pur si simplu entitatea protejata cu chei secrete refuza sa semneze texte arbitrare trimise de terti. Daca acest lucru nu este posibil (ca de exemplu in cazul unui notar public care trebuie sa semneze documente electronice prezentate de persoane straine), atunci atacul poate fi prevenit prin folosirea unei perechi diferite de chei pentru criptare si pentru semnatura electronica. De asemenea, este necesar sa se foloseasca si un padding aleator pentru mesaj inainte de criptare sau, in cazul semnaturii, sa nu se semneze mesajul clar, ci un hash al acestuia. De asemenea, atacul poate fi evitat si daca se impune o anumita structura predefinita mesajelor primite spre semnare.

Mesaje necriptate

Intrucat RSA se bazeaza pe ridicarea la putere (modulo un numar n), exista anumite parti de mesaje care nu sunt criptate, parti rezultate in urma impartirii mesajului pe blocuri. Astfel de mesaje sunt mesajele mcu proprietatea ca m=mx (mod n) oricare ar fi x, ca de exemplu m=0,m=1, m=n-1. Numarul exact al acestor mesaje decriptate este (1 + cmmdc(e-1,p-1))(1+cmmdc(e-a,q-1)), si deci este de minim 9 (deoareceep si q sunt impare). Pentru a micsora numarul de astfel de parti de mesaj, este util sa se foloseasca un exponent public e cat mai mic.

Exponentul de criptare mic

In unele aplicatii, se foloseste un exponent de criptare (public) mic, de exemplu 3, pentru a mari performanta, dar si pentru a rezolva unele probleme de securitate. Daca mai multe entitati care comunica folosesc acelasi exponent public (dar fiecare are propriul modul si deci propria cheie secreta), atunci acelasi mesaj trimis mai multor destinatari are urmatoarele valori:

c1 = me(mod n1)c2 = me(mod n2)c3 = me(mod n3)

unde ni sunt modulele celor trei destinatari, e este exponentul comun acestora iar m este mesajul trimis tuturor celor trei. Un atacator poate folosi algoritmul lui Gauss pentru a descoperi o solutie mai mica decatn1n2n3 a unui sistem compus din urmatoarele ecuatii:

x = me(mod n1)x = me(mod n2)x = me(mod n3)

Aceasta solutie este, conform teoremei chinezesti a resturilor, cubul mesajului m. Solutia pentru aceasta problema este cea denumitasararea mesajului (din engleza salting), adica adaugarea unui padding format din numere pseudoaleatoare, padding diferit pentru fiecare expediere a mesajului.


Exponentul de decriptare mic

Daca exponentul de decriptare (cel secret) este mic, pe langa faptul ca multe parti din mesaj nu se cripteaza, asa cum s-a aratat mai sus, exista un algoritm rapid de gasire a lui d, cunoscand informatiile e si n. Acest algoritm nu este eficient daca d este de acelasi ordin de marime cu n, deci daca e este mic, acesta fiind unul din motivele pentru care se alege in general e un numar mic, pentru ca d sa fie cat mai mare.

Sursa: Wikipedia


One Response to Algoritmul de criptografie RSA

  1. Marian spune:

    Buna ziua,
    toate pozele de pe calculator au fost criptate cu RSA 4096 si nu mai pot vedea fisierele jpg. Exista un program de decriptare care sa-mi rezolve problema?

Add Comment Register



Lasă un răspuns

Adresa ta de email nu va fi publicată. Câmpurile necesare sunt marcate *


*

Poți folosi aceste etichete HTML și atribute: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>