L’RSA è il capostipite della crittografia a chiave pubblica: un sistema in cui chiunque può cifrare un messaggio per un destinatario, ma solo il destinatario può decifrarlo. La svolta concettuale, rispetto alla crittografia classica, è che le due parti non devono condividere in anticipo un segreto comune. Ogni utente possiede una coppia di chiavi: una pubblica, diffusa apertamente, e una privata, custodita gelosamente.
Il fondamento non è un trucco informatico, ma un fatto di teoria dei numeri: esistono operazioni facili da eseguire ma difficili da invertire. Moltiplicare due numeri primi grandi è immediato; ritrovare quei due primi a partire dal solo prodotto è, allo stato dell’arte, computazionalmente proibitivo. RSA costruisce su questa asimmetria l’intera sicurezza.
Aritmetica modulare
RSA vive nell’aritmetica modulare, l’aritmetica dei resti. Lavorare modulo n significa considerare solo il resto della divisione per n: numeri che differiscono di un multiplo di n sono considerati uguali. Si scrive:
se a e b hanno lo stesso resto diviso n. È l’aritmetica dell’orologio: dopo le 12 si ricomincia. In questo mondo finito le potenze si comportano in modo ciclico, e proprio questa ciclicità rende possibile cifrare e decifrare con due esponenti diversi che si “annullano” a vicenda.
Il teorema di Eulero
Il motore matematico di RSA è il teorema di Eulero. Definita la funzione di Eulero \varphi(n) come il numero di interi tra 1 e n coprimi con n, vale, per ogni a coprimo con n:
La conseguenza è che, lavorando modulo n, gli esponenti si comportano modulo \varphi(n). Se due esponenti e e d soddisfano:
allora elevare a e e poi a d riporta al numero di partenza:
Qui è racchiuso tutto RSA: e cifra, d decifra, e la coppia funziona perché e e d sono inversi modulo \varphi(n). Chi conosce \varphi(n) può calcolare d da e; chi non lo conosce, no.
Generazione delle chiavi
La costruzione di una coppia di chiavi segue passi precisi:
| Passo | Operazione |
|---|---|
| 1 | scegliere due primi grandi e distinti p, q |
| 2 | calcolare il modulo n = p \cdot q |
| 3 | calcolare \varphi(n) = (p-1)(q-1) |
| 4 | scegliere un esponente pubblico e coprimo con \varphi(n) |
| 5 | calcolare d \equiv e^{-1} \pmod{\varphi(n)} |
Il punto cruciale è il passo 3: \varphi(n) = (p-1)(q-1) si calcola solo conoscendo i fattori p e q. Chi possiede p e q ottiene \varphi(n), quindi d. Chi vede solo n dovrebbe prima fattorizzarlo, e qui sta il muro.
Il risultato sono due chiavi:
- chiave pubblica (n, e) — diffusa a tutti;
- chiave privata (n, d) — tenuta segreta; i primi p, q vanno distrutti o protetti.
Cifratura e decifratura
Per inviare un messaggio m (un numero, con 0 \le m < n), il mittente usa la chiave pubblica del destinatario:
Il destinatario recupera il messaggio con la propria chiave privata:
L’uguaglianza finale c^d = m^{ed} \equiv m \pmod n vale per il teorema di Eulero, perché e e d sono inversi modulo \varphi(n). Chiunque può cifrare (la chiave pubblica è nota), ma solo chi possiede d può decifrare. Le potenze modulari si calcolano in fretta con l’esponenziazione rapida (quadrati ripetuti), anche con numeri di migliaia di bit.
Firma digitale
Lo schema funziona anche al contrario, e questo dà la firma digitale. Il mittente “cifra” con la propria chiave privata un’impronta (hash) del documento:
Chiunque può verificare usando la chiave pubblica del firmatario:
Se l’uguaglianza regge, la firma è autentica: solo chi possiede d poteva produrla, e il documento non è stato alterato (altrimenti l’hash non corrisponderebbe). RSA fornisce così due servizi opposti con lo stesso meccanismo: riservatezza (cifrare con la pubblica) e autenticità (firmare con la privata).
La sicurezza: fattorizzazione
La sicurezza di RSA si regge su un’asimmetria computazionale:
| Operazione | Difficoltà |
|---|---|
| moltiplicare p \cdot q = n | facile |
| fattorizzare n in p e q | difficile (per n grande) |
Un attaccante vede (n, e) e il messaggio cifrato c. Per decifrare gli servirebbe d, che richiede \varphi(n) = (p-1)(q-1), che richiede p e q, cioè la fattorizzazione di n. Non si conosce alcun algoritmo classico efficiente per fattorizzare numeri grandi: con primi di centinaia di cifre, il tempo necessario eccede l’età dell’universo con le risorse attuali.
Attenzione: non è dimostrato che rompere RSA equivalga a fattorizzare, né che la fattorizzazione sia intrinsecamente difficile. La sicurezza è empirica e congetturale, fondata sul fatto che nessuno ha trovato un metodo veloce. Per questo le dimensioni delle chiavi crescono nel tempo: 2048 o 4096 bit oggi, man mano che la potenza di calcolo aumenta.
Limiti reali
RSA è robusto nei fondamenti ma delicato nell’uso:
- è lento rispetto ai cifrari simmetrici; nella pratica si usa RSA solo per scambiare una chiave simmetrica, poi si cifra coi simmetrici (cifratura ibrida);
- richiede chiavi grandi (≥ 2048 bit) che continuano a crescere con la potenza di calcolo;
- è insicuro se usato “grezzo”: serve un padding corretto (OAEP per cifrare, PSS per firmare), altrimenti è vulnerabile;
- una generazione difettosa dei primi (entropia scarsa, primi vicini o riusati) compromette tutto;
- un computer quantistico efficiente romperebbe RSA con l’algoritmo di Shor, che fattorizza in tempo polinomiale: di qui la ricerca sulla crittografia post-quantistica;
- la sicurezza dipende dalla custodia della chiave privata: se trapela, cade ogni garanzia.
Sintesi operativa
RSA realizza la crittografia a chiave pubblica trasformando un fatto di teoria dei numeri in un sistema di sicurezza: moltiplicare due primi è facile, fattorizzare il loro prodotto è proibitivo.
Il meccanismo si regge sul teorema di Eulero: scelti due primi p, q, si pubblica (n, e) e si tiene segreto d, inverso di e modulo \varphi(n) = (p-1)(q-1). Cifrare è elevare a e modulo n, decifrare è elevare a d; le due operazioni si annullano perché e d \equiv 1 \pmod{\varphi(n)}. Lo stesso schema, usato al contrario, produce la firma digitale: riservatezza e autenticità dallo stesso principio. La sicurezza non è dimostrata ma poggia sulla difficoltà pratica della fattorizzazione — un muro solido oggi, che la crittografia quantistica potrebbe un giorno abbattere, e per questo le chiavi crescono e si studiano alternative post-quantistiche.