Cheile
Cum se găsește d: algoritmul lui Euclid extins
Fiecare rând rezultă din împărțirea celor două rânduri de deasupra lui. În rândul cu restul 1, ultima coloană este d (adăugați φ(n) dacă este negativ).
| Cât | Rest | Coeficientul lui e |
|---|
Mesajul
Trimis prin rețea
| Bit | La pătrat | Înmulțire cu m |
|---|
Spargerea cheii
Demonstrație de criptare RSA
RSA permite oricui să încuie un mesaj cu cheia dumneavoastră publică, în timp ce doar dumneavoastră îl puteți deschide cu cheia privată. În spatele lui stau câteva rânduri de aritmetică școlară: două numere prime, o înmulțire, un rest și un invers ingenios. Construiți o pereche de chei din numere prime alese de dumneavoastră, criptați și decriptați un mesaj caracter cu caracter, semnați-l ca oricine să poată verifica faptul că provine de la dumneavoastră, apoi jucați rolul atacatorului și factorizați n ca să vedeți de ce cheile reale au nevoie de sute de cifre. Alegeți două numere prime p și q sau apăsați „Numere prime noi”. Aplicația construiește cheia publică (e, n) și cheia privată d și arată cum îl găsește algoritmul lui Euclid extins pe d. Scrieți un mesaj: fiecare caracter este criptat cu cheia publică și decriptat cu cheia privată. Faceți clic pe un rând ca să vedeți puterea calculată prin ridicări repetate la pătrat. Treceți la „Semnează” ca să semnați în schimb cu cheia privată și apăsați „Factorizează n” ca să vedeți cât de repede cedează cheile mici.
Cum funcționează
- Introduceți două numere prime p și q sau alegeți o mărime și apăsați „Numere prime noi”; aplicația calculează n, φ(n), e și d și arată cum se găsește d.
- Scrieți un mesaj și alegeți „Criptează” sau „Semnează”. Fiecare caracter este transformat într-un număr și ridicat la o putere mod n; faceți clic pe un rând ca să vedeți ridicarea repetată la pătrat.
- Apăsați „Factorizează n” ca s-o lăsați pe Eve să descompună n în cele două numere prime ale sale și să recupereze cheia privată.
Cum funcționează cheile
Înmulțiți două numere prime: n = p × q. Cu p = 61 și q = 53, n = 3233. Numărul φ(n) = (p − 1)(q − 1) = 3120 numără numerele mai mici decât n care nu au niciun factor comun cu el și poate fi calculat doar de cineva care cunoaște p și q. Alegeți e = 17, care nu are niciun factor comun cu 3120, și găsiți d astfel încât e × d să fie cu 1 mai mare decât un multiplu al lui φ(n): aici d = 2753, pentru că 17 × 2753 = 46801 = 15 × 3120 + 1. Publicați (e, n) și păstrați d. Un mesaj m devine c = mᵉ mod n, iar teorema lui Euler garantează că cᵈ mod n îl redă pe m.
De ce este greu de spart
Tot ce îi trebuie unui atacator este ascuns în factorii lui n. Cu n = 3233 nu e nicio protecție: încercarea divizorilor impari îl găsește pe 53 după vreo două duzini de încercări. Dar efortul crește odată cu rădăcina pătrată a lui n. Un modul de 2048 de biți are circa 617 cifre și nicio metodă cunoscută, pe niciun calculator existent astăzi, nu îl poate factoriza într-un timp util. Semnarea rulează RSA invers: s = mᵈ mod n poate fi produs doar cu cheia privată, iar oricine poate verifica faptul că sᵉ mod n îl redă pe m.
Întrebări frecvente
De ce nu poate nimeni calcula d din cheia publică?
Ca să găsiți d aveți nevoie de φ(n) = (p − 1)(q − 1), iar ca să obțineți φ(n) aveți nevoie de p și q. Recuperarea lor din n înseamnă factorizarea lui n, iar pentru numere cu sute de cifre nu se cunoaște nicio metodă rapidă. Demonstrația vă permite să factorizați chei de jucărie într-o fracțiune de secundă, ceea ce arată exact de ce cheile reale sunt atât de mari.
De ce este mesajul criptat câte un caracter?
Pentru că cheile de jucărie sunt mici: RSA poate cripta doar un număr mai mic decât n. Cu n = 3233 încape codul oricărui caracter, dar o propoziție întreagă nu. RSA real folosește un modul de 2048 de biți sau mai mult, completează mesajul cu octeți aleatori, astfel încât același mesaj să nu fie niciodată criptat de două ori la fel, și în practică criptează doar o cheie scurtă pentru un cifru mai rapid, cum ar fi AES.
Ce face ridicarea repetată la pătrat?
Calculează puteri uriașe precum m²⁷⁵³ mod n fără a scrie vreodată numărul uriaș. Scrieți exponentul în binar, apoi parcurgeți-i biții: ridicați rezultatul curent la pătrat pentru fiecare bit și înmulțiți-l cu m pentru fiecare 1, luând de fiecare dată restul mod n. Un exponent de 2048 de biți are nevoie doar de aproximativ 2048 de ridicări la pătrat.
Care este diferența dintre criptare și semnare?
Criptarea folosește cheia publică a destinatarului, astfel încât doar cheia privată a destinatarului o poate anula. Semnarea folosește cheia privată a expeditorului, astfel încât oricine o poate verifica cu cheia publică a expeditorului și poate ști că mesajul provine de la deținătorul acelei chei și nu a fost modificat.
Este mesajul meu trimis undeva?
Nu. Totul este calculat în browserul dumneavoastră, iar numerele prime și mesajul rămân în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor