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.
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.
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.
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