Lo scambio di chiavi Diffie-Hellman spiegato
Per migliaia di anni, inviare un messaggio segreto significava prima condividere una chiave segreta di persona o tramite corriere. Nel 1976 due ricercatori di Stanford mostrarono che due parti potevano creare una chiave condivisa dal nulla, scambiandosi messaggi sotto gli occhi di tutti. L'idea aprì l'era della crittografia a chiave pubblica ed è ancora all'opera ogni volta che un browser mostra un lucchetto.
Il problema della distribuzione delle chiavi
Un cifrario come AES è sicuro solo quanto la sua chiave, ed entrambe le parti hanno bisogno della stessa chiave. Prima del 1976 la chiave doveva essere consegnata in segreto: con la valigia diplomatica, tramite corrieri fidati o con libri di codici stampati in anticipo. Per due sconosciuti che vogliono comunicare in modo sicuro subito, per esempio un negozio e un cliente su Internet, è impossibile. L'articolo di Whitfield Diffie e Martin Hellman «New Directions in Cryptography» risolse il problema con un metodo che non richiede alcun segreto preliminare.
Aritmetica sull'orologio
Lo scambio usa l'aritmetica modulare: calcoli su un orologio con p ore, dove p è un grande numero primo. Su questo orologio le potenze si comportano in modo notevole. Se g è una radice primitiva, i numeri g, g², g³, … mod p saltano qua e là e toccano ogni ora da 1 a p − 1 prima di ripetersi, in un ordine che sembra casuale. Calcolare gᵃ mod p è veloce, con circa tante moltiplicazioni quante sono le cifre binarie di a. Invertirlo no.
Lo scambio passo dopo passo
Alice e Bob concordano apertamente p e g. Alice sceglie un segreto a e invia A = gᵃ mod p; Bob sceglie un segreto b e invia B = gᵇ mod p. Alice calcola Bᵃ = (gᵇ)ᵃ e Bob calcola Aᵇ = (gᵃ)ᵇ, entrambi mod p. Poiché l'ordine degli esponenti non conta, entrambi ottengono g^(ab) mod p. Con il classico piccolo esempio p = 23, g = 5, a = 6 e b = 15, Alice invia 8, Bob invia 19, ed entrambi arrivano al segreto condiviso 2.
Il problema del logaritmo discreto
Eve vede p, g, A e B. Se potesse trovare a da A = gᵃ mod p, potrebbe calcolare il segreto proprio come fa Alice. Questo è il problema del logaritmo discreto. I migliori algoritmi classici noti, come il crivello dei campi di numeri, sono molto più veloci che provare ogni esponente, ma richiedono comunque un tempo che cresce più rapidamente di qualsiasi potenza del numero di cifre. Con primi di 2048 bit il problema è fuori dalla portata di qualunque computer esistente. Non si sa se sia possibile qualcosa di più veloce, e la sicurezza dello scambio si fonda su questa convinzione.
Man in the middle
Diffie-Hellman protegge da chi ascolta, ma non da un impostore. Mallory, che si trova tra Alice e Bob, può condurre uno scambio con ciascuno dei due e passare i messaggi, leggendo tutto. La difesa è l'autenticazione: in HTTPS il server firma la sua parte dello scambio con una chiave certificata da un'autorità fidata, così il browser sa di parlare davvero con il sito giusto. Scambio di chiavi e firme vanno sempre insieme.
Chi l'ha inventato?
Diffie e Hellman pubblicarono nel 1976, partendo dalle idee di Ralph Merkle; in seguito Hellman chiese che anche a lui venisse riconosciuto il merito. Nel 1997 l'agenzia di intelligence britannica GCHQ rivelò che i suoi matematici ci erano arrivati per primi: James Ellis aveva avuto l'idea della crittografia a chiave pubblica nel 1970, Clifford Cocks aveva trovato un sistema simile a RSA nel 1973 e Malcolm Williamson aveva scoperto lo stesso scambio di chiavi nel 1974, tutto tenuto segreto per oltre vent'anni.
Diffie-Hellman oggi
Le connessioni moderne usano per lo più Diffie-Hellman su curve ellittiche, che offre la stessa sicurezza con numeri molto più corti, per esempio la curva X25519 in TLS 1.3, Signal e WhatsApp. Usare una nuova coppia di segreti per ogni connessione garantisce la forward secrecy: anche se la chiave a lungo termine di un server venisse rubata in seguito, le conversazioni passate resterebbero al sicuro. I parametri deboli restano un pericolo, come ha mostrato nel 2015 l'attacco Logjam per i vecchi primi a 512 bit, e un grande computer quantistico che eseguisse l'algoritmo di Shor violerebbe sia il Diffie-Hellman classico sia quello su curve ellittiche: per questo oggi si stanno introducendo, accanto a essi, scambi di chiavi post-quantistici.
Esploralo
Apri il visualizzatore Diffie-Hellman per seguire i cinque passi su una tabella di ciò che sanno Alice, il canale pubblico e Bob, come colori e come numeri. Scegli primi da 23 fino a 2.147.483.647, imposta tu i segreti e lascia attaccare Eve provando ogni esponente: guardala riuscire all'istante con i primi piccoli e osserva come cresce il tempo di ricerca stimato man mano che il primo si allunga.
Domande frequenti
Diffie-Hellman è la stessa cosa di RSA?
No, anche se entrambi sono metodi a chiave pubblica degli anni Settanta. RSA, pubblicato nel 1977, può cifrare e firmare con una chiave pubblica e una privata e si basa sulla difficoltà di fattorizzare numeri grandi. Diffie-Hellman serve solo ad accordarsi su un segreto condiviso e si basa sul problema del logaritmo discreto.
Quanto sono grandi i numeri nella pratica?
Il Diffie-Hellman classico usa primi di almeno 2048 bit, circa 617 cifre decimali, e spesso di 3072 o 4096 bit. Le versioni su curve ellittiche usano chiavi di circa 256 bit per una sicurezza paragonabile.
Perché ogni bit in più raddoppia il lavoro di Eve?
Un primo con un bit in più è circa due volte più grande, quindi ci sono circa il doppio degli esponenti da provare. Gli attacchi reali sono più astuti che provare ogni esponente, ma il loro costo cresce comunque molto rapidamente con la dimensione del primo.
Perché Alice e Bob hanno bisogno di un numero primo?
Con un modulo primo ogni numero da 1 a p − 1 ha un inverso ed esistono radici primitive, quindi le potenze di g coprono tutte le possibilità. Spesso si scelgono primi sicuri, per cui anche (p − 1)/2 è primo, per escludere scorciatoie che sfruttano piccoli fattori di p − 1.
Pronto a provarlo?
Apri PictorX nel tuo browser: nessuna installazione, nessuna carta di credito richiesta per iniziare.
Apri il visualizzatore Diffie-Hellman