RSA (algoritmo crittografico)

RSA è un algoritmo di crittografia a chiave pubblica (asimmetrica) pubblicato nel 1977 da Ron Rivest, Adi Shamir e Leonard Adleman — le cui iniziali formano l’acronimo. È il primo algoritmo asimmetrico pratico e rimane, dopo quasi cinquant’anni, uno degli standard più diffusi per la cifratura di chiavi simmetriche, la firma digitale e i protocolli di autenticazione. La sua sicurezza si fonda sulla difficoltà computazionale della fattorizzazione di interi grandi: moltiplicare due grandi numeri primi è rapido; fattorizzare il prodotto in tempi ragionevoli è, con gli algoritmi attuali, computazionalmente proibitivo per chiavi sufficientemente lunghe.

Generazione delle chiavi

1. Scegliere due grandi numeri primi $p$ e $q$ (generati casualmente, tipicamente di 1024–2048 bit ciascuno).
2. Calcolare $n = p \cdot q$ — il modulo RSA, parte pubblica.
3. Calcolare $\phi(n) = (p-1)(q-1)$ — la funzione di Eulero.
4. Scegliere $e$ tale che $1 < e < \phi(n)$ e $\gcd(e, \phi(n)) = 1$. Valore standard: $e = 65537$.
5. Calcolare $d$ tale che $d \cdot e \equiv 1 \pmod{\phi(n)}$ — l’inverso moltiplicare di $e$ modulo $\phi(n)$.

La chiave pubblica è la coppia $(n, e)$. La chiave privata è $(n, d)$. I valori $p$, $q$ e $\phi(n)$ vanno distrutti dopo la generazione.

Cifratura e decifratura

Data la chiave pubblica $(n, e)$ e un messaggio $m$ (con $0 \leq m < n$):

$c = m^e \bmod n$

Per decifrare con la chiave privata $(n, d)$:

$m = c^d \bmod n$

La correttezza segue dal Piccolo Teorema di Fermat generalizzato: $m^{ed} \equiv m \pmod{n}$ quando $ed \equiv 1 \pmod{\phi(n)}$.

Firma digitale

Nella firma, i ruoli si invertono: il mittente cifra con la propria chiave privata un hash del messaggio; chiunque può verificare con la chiave pubblica. Questo garantisce autenticità (solo chi possiede la chiave privata può firmare) e integrità (una modifica al messaggio invalida la firma).

Lunghezza delle chiavi e sicurezza

La sicurezza di RSA dipende dalla lunghezza del modulo $n$:

Lunghezza chiave	Stima sicurezza equivalente	Status
512 bit	<56 bit	Rotto (1999)
1024 bit	~80 bit	Deprecato (NIST 2013)
2048 bit	~112 bit	Minimo raccomandato attuale
3072 bit	~128 bit	Raccomandato per dati con vita >2030
4096 bit	~140 bit	Alto livello di sicurezza

Vulnerabilità pratiche

RSA testbook (senza padding) è vulnerabile a vari attacchi algebrici. In pratica si usano schemi di padding sicuri: OAEP (Optimal Asymmetric Encryption Padding) per la cifratura, PSS (Probabilistic Signature Scheme) per la firma. L’uso di RSA con PKCS#1 v1.5 padding per la cifratura è vulnerabile all’attacco di Bleichenbacher (1998) e va evitato nei nuovi sistemi.

RSA e crittografia post-quantistica

Un computer quantistico sufficientemente grande potrebbe eseguire l’algoritmo di Shor, che fattorizza interi in tempo polinomiale, rendendo RSA insicuro. Questo motiva la transizione verso algoritmi di crittografia post-quantistica standardizzati dal NIST nel 2024.