RSA spiegato
Ogni volta che un browser mostra un lucchetto, che un messaggio viene firmato o che un software verifica un aggiornamento, è all'opera la crittografia a chiave pubblica, e RSA ne è la forma più nota. La sua idea è che la chiave che chiude un messaggio può essere pubblicata, mentre quella che lo apre resta privata. Sorprendentemente, l'intero sistema si basa sull'aritmetica insegnata a scuola: numeri primi, moltiplicazione e resti.
Il problema che RSA risolve
I cifrari più antichi, dal cifrario di Cesare al moderno AES, usano la stessa chiave per chiudere e aprire, quindi le due parti devono prima condividere in privato una chiave segreta. La crittografia a chiave pubblica elimina questo passaggio. Ogni persona ha due chiavi: una chiave pubblica che chiunque può usare per cifrarle un messaggio e una chiave privata che possiede solo lei e che sola può decifrarlo. Whitfield Diffie e Martin Hellman descrissero l'idea nel 1976, e un anno dopo Ron Rivest, Adi Shamir e Leonard Adleman, al MIT, trovarono un modo per realizzarla, chiamato RSA dalle loro iniziali.
Creare le chiavi
Scegli due grandi numeri primi, p e q, e moltiplicali: n = p × q. Calcola φ(n) = (p − 1)(q − 1), la funzione φ di Euler, che conta i numeri minori di n che non hanno fattori comuni con esso. Scegli un esponente pubblico e che non abbia fattori comuni con φ(n); 65537 è la scelta abituale. Poi trova l'esponente privato d tale che e × d dia resto 1 nella divisione per φ(n). L'algoritmo di Euclide esteso lo fa rapidamente. La chiave pubblica è la coppia (e, n); la chiave privata è d. Con p = 61 e q = 53 si ottiene n = 3233, φ(n) = 3120, e = 17 e d = 2753.
Cifrare e decifrare
Un messaggio viene prima trasformato in un numero m minore di n. Per cifrarlo si calcola c = mᵉ mod n, il resto della divisione di mᵉ per n. Per decifrare si calcola cᵈ mod n. Il teorema di Euler garantisce che si ottiene di nuovo m, perché e × d supera di 1 un multiplo di φ(n). Con le chiavi viste sopra la lettera A, codice 65, diventa 65¹⁷ mod 3233 = 2790, e 2790²⁷⁵³ mod 3233 = 65 di nuovo. Potenze così grandi non vengono mai scritte per esteso: i quadrati ripetuti le calcolano con un elevamento al quadrato per ogni bit dell'esponente, prendendo il resto a ogni passo.
Firme digitali
RSA funziona anche al contrario. Elevando un messaggio all'esponente privato, s = mᵈ mod n, si ottiene una firma che solo il proprietario della chiave può produrre. Chiunque può verificarla con la chiave pubblica: se sᵉ mod n restituisce m, il messaggio viene dal titolare di d e non è stato modificato lungo il percorso. Nella pratica si firma un breve hash del messaggio anziché il messaggio stesso. Firme di questo tipo proteggono gli aggiornamenti software, i siti web sicuri e i documenti elettronici.
Perché è sicuro
Tutti possono vedere n ed e. Per trovare d, un attaccante ha bisogno di φ(n), e per trovare φ(n) servono p e q, quindi violare RSA si riduce a fattorizzare n. Moltiplicare due primi richiede a un computer una frazione di microsecondo; scomporre il prodotto per ritrovarli si ritiene estremamente difficile. Il più grande numero della sfida RSA fattorizzato finora, RSA-250 nel 2020, ha 829 bit e ha richiesto circa 2700 anni di calcolo. Le chiavi in uso oggi hanno almeno 2048 bit, circa 617 cifre.
Un segreto scoperto due volte
Nel 1973, quattro anni prima di RSA, il matematico britannico Clifford Cocks trovò lo stesso schema mentre lavorava presso l'agenzia di intelligence GCHQ, sviluppando un'idea del suo collega James Ellis. Il lavoro era classificato e fu reso pubblico solo nel 1997. RSA stesso fu brevettato negli Stati Uniti nel 1983; il brevetto scadde nel settembre 2000, due settimane dopo che l'algoritmo era stato rilasciato nel pubblico dominio.
RSA nella pratica
Il vero RSA non cifra mai direttamente un testo. Il messaggio viene completato con byte casuali, secondo uno schema come OAEP, in modo che lo stesso messaggio venga cifrato ogni volta in modo diverso e non trapeli alcuna regolarità. Poiché RSA è lento, si usa soprattutto per scambiare o proteggere una chiave corta per un cifrario simmetrico veloce come AES, oppure per firmare. Computer quantistici abbastanza grandi potrebbero fattorizzare n rapidamente con l'algoritmo di Shor del 1994, ed è per questo che accanto a RSA si stanno introducendo nuovi metodi post-quantistici.
Esploralo
Apri la demo della cifratura RSA per costruire chiavi a partire dai tuoi numeri primi o da primi casuali da 2 a 8 cifre, vedere l'algoritmo di Euclide esteso trovare d riga per riga, cifrare o firmare un messaggio carattere per carattere e seguire i quadrati ripetuti per qualsiasi carattere. Poi lascia che Eve fattorizzi n e guarda come il tempo che le serve cresce con la dimensione dei primi.
Domande frequenti
Perché RSA ha bisogno dei numeri primi?
Perché φ(n) è facile da calcolare solo se si sa come n si scompone in fattori primi. Per n = p × q con p e q primi, φ(n) = (p − 1)(q − 1). I numeri primi rendono inoltre n il più difficile possibile da fattorizzare per la sua dimensione, dato che non ha alcun fattore piccolo.
Perché e vale spesso 65537?
65537 = 2¹⁶ + 1 è primo e ha solo due cifre 1 in binario, quindi cifrare con esso richiede appena 16 elevamenti al quadrato e una moltiplicazione. È anche abbastanza grande da evitare le debolezze degli esponenti molto piccoli come 3.
Qual è la differenza tra RSA e Diffie–Hellman?
Diffie–Hellman permette a due persone di accordarsi su una chiave segreta condivisa attraverso un canale aperto; da solo non cifra né firma nulla. RSA cifra e firma direttamente con una coppia di chiavi. Entrambi si basano su problemi facili in un senso e difficili nell'altro: la fattorizzazione per RSA, il logaritmo discreto per Diffie–Hellman.
Le chiavi della demo si possono usare per una cifratura vera?
No. I suoi numeri primi hanno al massimo una dozzina di cifre, quindi qualsiasi chiave che produce può essere fattorizzata in pochi secondi o meno, e cifra ogni carattere separatamente, senza padding. Serve a vedere come funziona RSA, non a proteggere qualcosa.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri la demo della cifratura RSA