Modulul n
φ(n) (p − 1)(q − 1)
Cheia publică (e, n)
Cheia privată d e · d mod φ(n) = 1

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âtRestCoeficientul lui e

    Mesajul

    Caracter Cod m Rezultat

    Trimis prin rețea

    BitLa pătratÎnmulțire cu m

    Spargerea cheii

    Acțiune

    Mai multe informații despre RSA

    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ă

    1. 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.
    2. 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.
    3. 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