Scambio di Chiavi Diffie-Hellman¶
La Storia Dietro la Matematica¶
All'inizio degli anni '70, la crittografia aveva un problema fondamentale. Se Alice e Bob volevano comunicare segretamente, dovevano prima condividere una chiave segreta. Ma come si condivide una chiave segreta... senza avere già un canale sicuro? Era un problema dell'uovo e della gallina che aveva afflitto la crittografia per millenni.
Whitfield Diffie e Martin Hellman, alla Stanford University, risolsero questo problema apparentemente impossibile nel 1976. Il loro articolo, "New Directions in Cryptography," è una delle pubblicazioni più importanti nella storia dell'informatica.
L'intuizione chiave è una bellissima proprietà unidirezionale dell'esponenziazione modulare. Calcolare \(g^a \mod p\) è veloce. Ma dato \(g^a \mod p\), trovare \(a\) — il problema del logaritmo discreto — sembra essere straordinariamente difficile.
Diffie e Hellman ricevettero il Premio Turing 2015.
Perché È Importante¶
- TLS/HTTPS — Ogni connessione web sicura inizia con uno scambio Diffie-Hellman
- SSH — Le connessioni shell sicure usano DH per stabilire chiavi di sessione
- VPN — IPsec e WireGuard usano varianti di DH
- Perfect forward secrecy — Anche se le chiavi a lungo termine sono compromesse, le sessioni passate restano sicure
Il Protocollo¶
Parametri pubblici: Un primo grande \(p\) e un generatore \(g\) del gruppo moltiplicativo \(\mathbb{Z}_p^*\).
| Passo | Alice | Canale Pubblico | Bob |
|---|---|---|---|
| 1 | Sceglie il segreto \(a\) | Sceglie il segreto \(b\) | |
| 2 | Calcola \(A = g^a \mod p\) | \(A \longrightarrow\) | |
| 3 | \(\longleftarrow B\) | Calcola \(B = g^b \mod p\) | |
| 4 | Calcola \(s = B^a \mod p\) | Calcola \(s = A^b \mod p\) |
Segreto condiviso: \(s = g^{ab} \mod p\)
Derivazione¶
Passo 1: Il Gruppo Moltiplicativo \(\mathbb{Z}_p^*\)¶
Per un primo \(p\), l'insieme \(\mathbb{Z}_p^* = \{1, 2, \ldots, p-1\}\) forma un gruppo sotto la moltiplicazione modulo \(p\) con ordine \(p - 1\).
Passo 2: Generatori e Gruppi Ciclici¶
Un generatore \(g\) di \(\mathbb{Z}_p^*\) è un elemento le cui potenze successive producono ogni elemento del gruppo:
Tali generatori esistono per ogni primo \(p\) (sono chiamati radici primitive modulo \(p\)).
Passo 3: Perché Entrambe le Parti Calcolano lo Stesso Segreto¶
Poiché \(ba = ab\): \(s_A = s_B = g^{ab} \mod p\).
Passo 4: Perché un Intercettatore Non Può Calcolare il Segreto¶
Un intercettatore vede \(p\), \(g\), \(A = g^a \mod p\) e \(B = g^b \mod p\). Per calcolare \(s = g^{ab} \mod p\), deve risolvere il problema del logaritmo discreto, che per primi grandi è computazionalmente impossibile.
Variabili Spiegate¶
| Simbolo | Nome | Descrizione |
|---|---|---|
| \(p\) | Primo modulo | Un numero primo grande (pubblico) |
| \(g\) | Generatore | Una radice primitiva modulo \(p\) (pubblica) |
| \(a\) | Segreto di Alice | Un intero casuale |
| \(b\) | Segreto di Bob | Un intero casuale |
| \(A\) | Valore pubblico di Alice | \(g^a \mod p\) |
| \(B\) | Valore pubblico di Bob | \(g^b \mod p\) |
| \(s\) | Segreto condiviso | \(g^{ab} \mod p\) |
Esempio Svolto¶
Parametri pubblici: \(p = 23\), \(g = 5\).
Alice sceglie \(a = 6\): \(A = 5^6 \mod 23 = 8\)
Bob sceglie \(b = 15\): \(B = 5^{15} \mod 23 = 19\)
Segreto condiviso:
Alice: \(s = 19^6 \mod 23 = 2\)
Bob: \(s = 8^{15} \mod 23 = 2\)
Entrambi calcolano \(s = 2\).
Errori Comuni¶
- Usare primi piccoli: \(p\) deve essere almeno 2048 bit.
- Non usare un primo sicuro: Un primo sicuro ha la forma \(p = 2q + 1\) dove anche \(q\) è primo.
- Riutilizzare chiavi effimere: I segreti \(a\) e \(b\) devono essere generati nuovi per ogni sessione.
- Nessuna autenticazione: DH è vulnerabile ad attacchi man-in-the-middle. L'autenticazione è essenziale.
Formule Correlate¶
- RSA — Cifratura a chiave pubblica basata sulla fattorizzazione
- Crittografia a Curve Ellittiche — ECDH: la versione su curve ellittiche
Riferimenti¶
- Diffie, W., & Hellman, M. (1976). New Directions in Cryptography. IEEE Transactions on Information Theory, 22(6), 644–654.
- Menezes, A., van Oorschot, P., & Vanstone, S. (1996). Handbook of Applied Cryptography. CRC Press.