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
- Scegliere due grandi numeri primi p e q (generati casualmente, tipicamente di 1024–2048 bit ciascuno).
- Calcolare n = p \cdot q — il modulo RSA, parte pubblica.
- Calcolare \phi(n) = (p-1)(q-1) — la funzione di Eulero.
- Scegliere e tale che 1 < e < \phi(n) e \gcd(e, \phi(n)) = 1. Valore standard: e = 65537.
- 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.