Ce este RSA?
Rivest-Shamir-Adleman, 1977. E cel mai cunoscut algoritm de criptare cu cheie publica.
Principiul matematic
RSA se bazeaza pe dificultatea factorizarii numerelor mari. E usor sa inmultesti doua numere prime mari, dar extrem de greu sa refaci drumul invers.
Generarea cheilor
- Alege doua numere prime foarte mari, p si q (de ex. ~1024 biti)
- Calculeaza n = p * q
- Calculeaza φ(n) = (p-1)(q-1)
- Alege e, coprim cu φ(n) (uzual e = 65537)
- Calculeaza d = e^(-1) mod φ(n)
Cheia publica: (n, e) Cheia privata: (n, d)
Criptare si decriptare
Criptare: c = m^e mod n Decriptare: m = c^d mod n
De ce e sigur?
Pentru un numar n de 2048 biti, factorizarea necesita miliarde de ani cu tehnologia actuala. Algoritmul clasic cel mai rapid (GNFS) are complexitate sub-exponentiala, dar tot impracticabila.
Calculatoarele cuantice (algoritmul lui Shor) ar putea sparge RSA eficient — de asta se cerceteaza criptografia post-cuantica.
Conexiunea cu numerele prime
Calitatea cheii RSA depinde direct de calitatea numerelor prime alese:
- Trebuie sa fie cu adevarat prime (testate cu algoritmi probabilistici)
- Trebuie sa fie suficient de mari (~1024-2048 biti)
- Nu trebuie sa fie prea apropiate (diferenta mare intre p si q)
- Trebuie generate aleator, nu dintr-o lista predefinita
Testele de primalitate folosite: Miller-Rabin (probabilistic), testul Baillie-PSW.
Aplicatii
HTTPS, email criptat (PGP), semnaturi digitale, SSH, blockchain, cartele bancare.