RSA explicat

De fiecare dată când un browser afișează un lacăt, un mesaj este semnat sau un program verifică o actualizare, criptografia cu cheie publică este la lucru, iar RSA este forma ei cea mai cunoscută. Ideea ei este că cheia care încuie un mesaj poate fi publicată, în timp ce cheia care îl deschide rămâne privată. Remarcabil este că întregul sistem se sprijină pe aritmetica învățată la școală: numere prime, înmulțire și resturi.

Numerele prime secrete 61 și 53 dau modulul public 3233. Literele din HELLO devin 3000, 28, 2726, 2726 și 1307 cu exponentul public 17, iar exponentul privat 2753 readuce 3000 la 72
Numerele prime secrete 61 și 53 dau modulul public 3233. Literele din HELLO devin 3000, 28, 2726, 2726 și 1307 cu exponentul public 17, iar exponentul privat 2753 readuce 3000 la 72

Problema pe care o rezolvă RSA

Cifrurile mai vechi, de la deplasarea lui Cezar până la modernul AES, folosesc aceeași cheie pentru a încuia și a descuia, așa că cele două părți trebuie mai întâi să împartă în privat o cheie secretă. Criptografia cu cheie publică elimină acest pas. Fiecare persoană are două chei: o cheie publică, pe care oricine o poate folosi pentru a-i cripta un mesaj, și o cheie privată, pe care doar ea o deține și care singură îl poate decripta. Whitfield Diffie și Martin Hellman au descris ideea în 1976, iar un an mai târziu Ron Rivest, Adi Shamir și Leonard Adleman de la MIT au găsit o metodă de a o pune în practică, numită RSA după inițialele lor.

Martin Hellman (stânga) și Whitfield Diffie (dreapta), 1977
Martin Hellman (stânga) și Whitfield Diffie (dreapta), 1977

Crearea cheilor

Alegeți două numere prime mari, p și q, și înmulțiți-le: n = p × q. Calculați φ(n) = (p − 1)(q − 1), indicatorul lui Euler, care numără numerele mai mici decât n ce nu au niciun factor comun cu el. Alegeți un exponent public e care nu are niciun factor comun cu φ(n); alegerea obișnuită este 65537. Apoi găsiți exponentul privat d astfel încât e × d să dea restul 1 la împărțirea prin φ(n). Algoritmul lui Euclid extins face asta rapid. Cheia publică este perechea (e, n); cheia privată este d. Cu p = 61 și q = 53 se obțin n = 3233, φ(n) = 3120, e = 17 și d = 2753.

Criptare și decriptare

Un mesaj este mai întâi transformat într-un număr m mai mic decât n. Pentru a-l cripta, calculați c = mᵉ mod n, restul împărțirii lui mᵉ la n. Pentru a decripta, calculați cᵈ mod n. Teorema lui Euler garantează că se obține din nou m, pentru că e × d este cu unu mai mare decât un multiplu al lui φ(n). Cu cheile de mai sus, litera A, codul 65, devine 65¹⁷ mod 3233 = 2790, iar 2790²⁷⁵³ mod 3233 = 65 din nou. Puteri atât de mari nu sunt scrise niciodată în întregime: ridicarea repetată la pătrat le calculează cu o ridicare la pătrat pentru fiecare bit al exponentului, luând restul la fiecare pas.

Semnături digitale

RSA funcționează și invers. Ridicarea unui mesaj la exponentul privat, s = mᵈ mod n, produce o semnătură pe care doar proprietarul cheii o poate crea. Oricine o poate verifica cu cheia publică: dacă sᵉ mod n îl redă pe m, mesajul provine de la deținătorul lui d și nu a fost modificat pe drum. În practică nu se semnează mesajul însuși, ci un rezumat scurt (hash) al lui. Asemenea semnături protejează actualizările de software, site-urile securizate și documentele electronice.

De ce este sigur

Oricine poate vedea n și e. Ca să găsească d, un atacator are nevoie de φ(n), iar ca să găsească φ(n) are nevoie de p și q, așa că spargerea RSA se reduce la factorizarea lui n. Înmulțirea a două numere prime îi ia unui calculator o fracțiune de microsecundă; descompunerea produsului înapoi în ele este considerată extrem de dificilă. Cel mai mare număr din competiția RSA factorizat până acum, RSA-250, în 2020, are 829 de biți și a necesitat circa 2700 de ani de timp de calcul. Cheile folosite astăzi au cel puțin 2048 de biți, aproximativ 617 cifre.

Un secret descoperit de două ori

În 1973, cu patru ani înainte de RSA, matematicianul britanic Clifford Cocks a găsit aceeași schemă în timp ce lucra la agenția de informații GCHQ, pornind de la o idee a colegului său James Ellis. Lucrarea a fost clasificată și a fost făcută publică abia în 1997. RSA a fost brevetat în Statele Unite în 1983; brevetul a expirat în septembrie 2000, la două săptămâni după ce algoritmul fusese trecut în domeniul public.

Ron Rivest, Adi Shamir și Len Adleman (de la stânga la dreapta)
Ron Rivest, Adi Shamir și Len Adleman (de la stânga la dreapta)

RSA în practică

RSA real nu criptează niciodată textul direct. Mesajul este completat cu octeți aleatori, după o schemă precum OAEP, astfel încât același mesaj să fie criptat de fiecare dată altfel și să nu se scurgă niciun tipar. Pentru că RSA este lent, este folosit mai ales pentru a schimba sau a proteja o cheie scurtă pentru un cifru simetric rapid, cum ar fi AES, sau pentru semnare. Calculatoarele cuantice suficient de mari ar putea factoriza rapid n cu algoritmul lui Shor din 1994, motiv pentru care sunt introduse noi metode post-cuantice alături de RSA.

Explorați

Deschideți demonstrația de criptare RSA ca să construiți chei din propriile numere prime sau din numere aleatorii de la 2 la 8 cifre, să vedeți cum algoritmul lui Euclid extins găsește d rând cu rând, să criptați sau să semnați un mesaj caracter cu caracter și să urmăriți ridicarea repetată la pătrat pentru orice caracter. Apoi lăsați-o pe Eve să factorizeze n și urmăriți cum crește timpul de care are nevoie odată cu mărimea numerelor prime.

Întrebări frecvente

De ce are nevoie RSA de numere prime?

Pentru că φ(n) este ușor de calculat doar când știți cum se descompune n în factori primi. Pentru n = p × q, cu p și q prime, φ(n) = (p − 1)(q − 1). Numerele prime fac, de asemenea, ca n să fie cât mai greu de factorizat pentru mărimea sa, deoarece nu are deloc factori mici.

De ce este e adesea 65537?

65537 = 2¹⁶ + 1 este prim și are în binar doar două cifre de 1, așa că o criptare cu el necesită doar 16 ridicări la pătrat și o înmulțire. Este, de asemenea, suficient de mare pentru a evita slăbiciunile exponenților foarte mici, precum 3.

Care este diferența dintre RSA și Diffie-Hellman?

Diffie-Hellman le permite la două persoane să convină asupra unei chei secrete comune pe un canal deschis; singur, nu criptează și nu semnează nimic. RSA criptează și semnează direct cu o pereche de chei. Ambele se bazează pe probleme ușoare într-un sens și grele în celălalt: factorizarea pentru RSA, logaritmul discret pentru Diffie-Hellman.

Pot fi folosite cheile demonstrației pentru criptare reală?

Nu. Numerele sale prime au cel mult douăsprezece cifre, așa că orice cheie creată de ea poate fi factorizată în câteva secunde sau mai puțin, iar fiecare caracter este criptat separat, fără completare. Scopul ei este să arate cum funcționează RSA, nu să protejeze ceva.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Deschideți demonstrația de criptare RSA