RSA è stato il primo sistema a chiave pubblica davvero pratico, e per decenni è stato la colonna portante di HTTPS, della posta cifrata e delle firme digitali. Prende il nome dai suoi tre autori, Ron Rivest, Adi Shamir e Leonard Adleman, che lo presentarono nel 1977. Il suo funzionamento si può capire con un po' di aritmetica delle scuole superiori.
L'idea di fondo: una porta a senso unico
RSA si basa su un'asimmetria matematica. Moltiplicare due numeri primi grandi è facile; partire dal prodotto e risalire ai due fattori è invece estremamente difficile quando i numeri hanno centinaia di cifre. Nessuno conosce un metodo efficiente per farlo con i computer classici.
Chi crea la chiave conosce i due primi e quindi possiede una "scorciatoia"; tutti gli altri vedono solo il prodotto.
Come si costruisce una coppia di chiavi
Il procedimento, semplificato, è questo:
- si scelgono due numeri primi grandi, p e q, e si tengono segreti;
- si calcola n = p × q, detto modulo;
- si calcola un valore legato a p e q, φ(n) = (p − 1) × (q − 1);
- si sceglie un esponente pubblico e, che non abbia divisori in comune con φ(n); in pratica si usa quasi sempre 65537;
- si calcola l'esponente privato d, in modo che e × d dia resto 1 se diviso per φ(n).
La chiave pubblica è la coppia (n, e). La chiave privata è d, insieme ai primi p e q che servono a calcolarla.
Un esempio con numeri piccoli
Con numeri giocattolo il meccanismo diventa visibile:
- p = 61, q = 53, quindi n = 3233;
- φ(n) = 60 × 52 = 3120;
- scegliamo e = 17;
- l'esponente privato risulta d = 2753, perché 17 × 2753 = 46801, che diviso per 3120 dà resto 1.
Per cifrare il messaggio m = 65 si calcola 65 elevato alla 17, e se ne prende il resto della divisione per 3233: il risultato è c = 2790. Per decifrare si calcola 2790 elevato alla 2753, sempre modulo 3233, e si ottiene di nuovo 65.
Nella realtà n ha 2048 bit o più, cioè circa 617 cifre decimali. Fattorizzare un numero del genere è fuori dalla portata dei computer attuali.
Cifrare e firmare
Con la stessa coppia di chiavi si possono fare due cose diverse.
- Cifratura: chiunque usa la chiave pubblica (n, e) per cifrare; solo il titolare di d può decifrare.
- Firma: il titolare usa d per produrre una firma sull'impronta (hash) di un documento; chiunque, con la chiave pubblica, verifica che la firma corrisponda.
Nella pratica RSA non cifra quasi mai i dati veri e propri: è lento e può gestire solo blocchi piccoli. Viene usato per proteggere una chiave simmetrica o per firmare un'impronta crittografica.
Il dettaglio che fa la differenza: il padding
L'RSA "da manuale" descritto sopra, applicato così com'è, è insicuro. Ha proprietà matematiche che un attaccante può sfruttare: lo stesso messaggio produce sempre lo stesso testo cifrato, e alcuni messaggi possono essere manipolati in modo prevedibile.
Per questo si usano schemi di padding, cioè regole per preparare il messaggio prima dell'operazione matematica, aggiungendo struttura e casualità:
- OAEP per la cifratura;
- PSS per le firme.
Il vecchio schema PKCS#1 v1.5 per la cifratura è stato al centro di diversi attacchi pratici, in cui un server che segnalava in modo diverso gli errori di padding permetteva a un attaccante di decifrare messaggi un pezzo alla volta. La lezione è chiara: in crittografia non basta un algoritmo giusto, serve anche il modo giusto di usarlo.
Quanto deve essere lunga una chiave RSA
| Lunghezza | Valutazione attuale |
|---|---|
| 1024 bit | Da considerare superata |
| 2048 bit | Minimo accettabile oggi |
| 3072 bit | Scelta consigliata per un orizzonte più lungo |
| 4096 bit | Margine maggiore, a costo di più lentezza |
Le chiavi RSA crescono rapidamente all'aumentare della sicurezza desiderata, e con esse i tempi di calcolo. Per questo molti sistemi moderni preferiscono le curve ellittiche, che offrono una sicurezza paragonabile con chiavi molto più corte.
Le minacce reali
Gli attacchi riusciti contro RSA raramente "rompono" la matematica. Più spesso sfruttano:
- primi generati male, per esempio con un generatore di numeri casuali difettoso, così che chiavi diverse condividono un fattore;
- chiavi troppo corte rimaste in uso per abitudine;
- implementazioni vulnerabili che rivelano informazioni sulla chiave privata attraverso i tempi di calcolo o i messaggi di errore;
- chiavi private custodite male, copiate su server, backup o computer non protetti.
C'è poi una minaccia futura: un computer quantistico sufficientemente grande, usando l'algoritmo di Shor, potrebbe fattorizzare n in modo efficiente. Oggi una macchina del genere non esiste, ma è il motivo per cui si sta lavorando alla migrazione verso algoritmi post-quantistici.
In sintesi
- RSA si basa sulla difficoltà di fattorizzare il prodotto di due grandi numeri primi.
- La chiave pubblica è (n, e); la chiave privata d si calcola conoscendo i fattori segreti p e q.
- Serve sia per cifrare piccole quantità di dati, come chiavi di sessione, sia per firmare.
- Senza un padding corretto (OAEP, PSS) RSA è vulnerabile.
- Oggi si usano almeno 2048 bit, e per il futuro si pianifica la transizione post-quantistica.
