Il protocollo di Diffie-Hellman
Il protocollo di Diffie-Hellman consente a due parti di generare una chiave segreta condivisa attraverso un canale pubblico senza trasmetterla direttamente.
Quindi, non è una vera e propria cifratura diretta di messaggi, ma un protocollo per generare a distanza una chiave privata condivisa che può poi essere utilizzata con algoritmi di cifratura simmetrica, come AES o altri, per cifrare e decifrare messaggi.
Si basa sul problema del logaritmo discreto, che è computazionalmente difficile da risolvere.
Come funziona?
Considero due utenti \( A \) e \( B \) che si trovano a distanza. Ad esempio, uno in Italia e l'altro in Australia.
Vorrebbero comunicare criptando i loro messaggi tramite una chiave segreta condivisa. Ovviamente, non possono comunicarla direttamente tramite il mezzo di trasmissione perché rischierebbe d'essere intercettato.
Il protocollo di Diffie-Hellman permette loro di risolvere questo problema.
Per prima cosa, i due utenti \( A \) e \( B \) decidono di utilizzare due valori pubblici noti a tutti:
- Un numero primo \( p \),
- Una base \( g \) da usare come generatore del gruppo moltiplicativo modulo \( p \)
Ogni utente sceglie una chiave privata segreta che non comunica a nessuno.
- \( A \) sceglie \( a \) (chiave privata),
- \( B \) sceglie \( b \) (chiave privata).
Ogni parte calcola e scambia la propria chiave pubblica.
- \( A \) calcola \( A_{\text{pub}} = g^a \mod p \) e lo invia a \( B \)
- \( B \) calcola \( B_{\text{pub}} = g^b \mod p \) e lo invia ad \( A \)
Entrambi gli utenti calcolano una chiave segreta condivisa usando la chiave pubblica ricevuta e la propria chiave privata:
- \( A \) calcola: \( K = (B_{\text{pub}})^a \mod p = g^{ab} \mod p \)
- \( B \) calcola: \( K = (A_{\text{pub}})^b \mod p = g^{ab} \mod p \)
La chiave segreta condivisa \( K \) è identica per entrambe le parti.
In questo modo, i due utenti hanno scambiato una chiave privata condivisa senza doverla comunicare direttamente.
A questo putnto, entrambi gli utenti possono usare la chiave privata condivisa $ K $ per cifrare e decifrare i loro messaggi tramite un algoritmo di cifratura simmetrica.
Un esempio pratico
In questo esempio provo a creare una chiave segreta condivisa tramite il protocollo di Diffie-Hellman tra due utenti \( A \) e \( B \).
Poi utilizzo la chiave per cifrare il messaggio "ciao", usando nuovi dati per le chiavi pubbliche e private.
Per semplicità, infine, utilizzerò come algoritmo di cifratura il cifrario di Cesare.
I due utenti \( A \) e \( B \) decidono di utilizzare questi valori pubblici:
- \( p = 23 \) (numero primo condiviso),
- \( g = 5 \) (base condivisa).
Poi scelgono le rispettive chiavi private che non condividono.
- \( A \) sceglie \( e_A = 6 \)
- \( B \) sceglie \( e_B = 15 \)
Quindi, calcolano le rispettive chiavi pubbliche.
- \( A \) calcola e pubblica: \( X_A = g^{e_A} \mod p = 5^6 \mod 23 = 8 \)
- \( B \) calcola e pubblica: \( X_B = g^{e_B} \mod p = 5^{15} \mod 23 = 19 \).
Verifica. Per calcolare le congruenze applico le proprietà delle potenze sapendo che: $$ 5^1 \mod 23 = 5 $$ $$ 5^2 \mod 23 = 2 $$ $$ 5^4 \mod 23 = (5^2 \mod 23) \cdot (5^2 \mod 23) = 2 \cdot 2 = 4 $$ $$ 5^8 \mod 23 = (5^4 \mod 23) \cdot (5^4 \mod 23) = 4 \cdot 4 = 16 $$ Tramite questi risultati posso calcolare entrambe le congruenze facilmente. $$ 5^6 \mod 23 = (5^4 \cdot 5^2 ) \mod 23 = 4 \cdot 2 = 8 $$ $$ 5^{15} \mod 23 = (5^8 \cdot 5^6 \cdot 5^1 ) \mod 23 = (16 \cdot 8 \cdot 5 ) \mod 23 = 19 $$
I due utenti si scambiano le chiavi pubbliche.
- \( A \) invia \( X_A = 8 \) a \( B \)
- \( B \) invia \( X_B = 19 \) a \( A \).
Possono usare le chiavi pubbliche per ottenere una chiave condivisa:
- \( A \) calcola: \( X_{AB} = X_B^{e_A} \mod p = 19^6 \mod 23 = 2 \),
- \( B \) calcola: \( X_{AB} = X_A^{e_B} \mod p = 8^{15} \mod 23 = 2 \).
In questo caso, la chiave condivisa è \( X_{AB} = 2 \).
Verifica. Anche in questo caso posso calcolare le congruenze usando le proprietà delle potenze. $$ 19^1 \mod 23 = 19 $$ $$ 19^2 \mod 23 = 361 \mod 23 = 16 $$ $$ 19^4 \mod 23 = (19^2 \cdot 19^2) \mod 23 = 16 \cdot 16 \mod 23 = 3 $$ Tramite questi risultati posso calcolare la prima congruenza $$ 19^6 \mod 23 = (19^4 \cdot 19^2) \mod 23 = 3 \cdot 16 \mod 23 = 2 $$ Con la stessa tecnica posso calcolare la seconda congruenza. $$ 8^1 \mod 23 = 8 $$ $$ 8^2 \mod 23 = 8 \cdot 8 \mod 23 = 18 $$ $$ 8^4 \mod 23 = 18 \cdot 18 \mod 23 = 2 $$ $$ 8^8 \mod 23 = 2 \cdot 2 \mod 23 = 4 $$ Quindi, la congruenza vale $$ 8^{15} \mod 23 = (8^8 \cdot 8^4 \cdot 8^2 \cdot 8^1) \mod 23 =(4 \cdot 2 \cdot 18 \cdot 8) \mod 23 = 2 $$
A questo punto, i due utenti sono entrambi in possesso della chiave condivisa e possono usarla per cifrare e decifrare i messaggi.
Cifratura del messaggio
Per semplicità, utilizzo il cifrario di Cesare come esempio di sistema di cifratura.
Nota. Si tratta ovviamente di un caso didattico: la chiave privata condivisa può essere applicata a qualsiasi altro sistema di cifratura ben più sofisticato. In pratica, al posto di Cesare si dovrebbe utilizzare un cifrario moderno, come AES (Advanced Encryption Standard), che sfrutta la chiave condivisa \( X_{AB} \) per cifrare e decifrare messaggi in modo sicuro.
L'utente \( A \) cifra il messaggio "ciao" con la chiave \( X_{AB} = 2 \) che implica un semplice spostamento di due posti delle lettere nell'alfabeto.
La parola "ciao" è composta dalle lettere "c", "i", "a", "o", che hanno i seguenti valori numerici nell'alfabeto \( c = 2, i = 8, a = 0, o = 14 \) di 26 lettere.
| Lettera | Codice | Lettera | Codice | Lettera | Codice |
|---|---|---|---|---|---|
| a | 0 | b | 1 | c | 2 |
| d | 3 | e | 4 | f | 5 |
| g | 6 | h | 7 | i | 8 |
| j | 9 | k | 10 | l | 11 |
| m | 12 | n | 13 | o | 14 |
| p | 15 | q | 16 | r | 17 |
| s | 18 | t | 19 | u | 20 |
| v | 21 | w | 22 | x | 23 |
| y | 24 | z | 25 |
Quindi, il messaggio "ciao" cifrato con la chiave condivisa \( X_{AB} = 2 \) (modulo 26) diventa:
- \( c = (2 + 2) \mod 26 = 4 \) → "e"
- \( i = (8 + 2) \mod 26 = 10 \) → "k"
- \( a = (0 + 2) \mod 26 = 2 \) → "c"
- \( o = (14 + 2) \mod 26 = 16 \) → "q"
Il messaggio cifrato è "ekcq" e viene inviato all'utente \( B \).
Decifratura del messaggio
Il destinatario \( B \) riceve il messaggio cifrato "ekcq".
Usa la chiave condivisa \( X_{AB} = 2 \) per decifrarlo:
- \( e = (4 - 2) \mod 26 = 2 \) → "c"
- \( k = (10 - 2) \mod 26 = 8 \) → "i"
- \( c = (2 - 2) \mod 26 = 0 \) → "a"
- \( q = (16 - 2) \mod 26 = 14 \) → "o"
In questo modo ottiene il messaggio originale "ciao".
Il protocollo è sicuro? Anche se un terzo dovesse intercettare i valori pubblici (\( p \), \( g \), \( X_A \), \( X_B \)), non potrebbe calcolare la chiave segreta condivisa \( X_{AB} \) senza risolvere un problema computazionalmente difficile come un logaritmo discreto. In sostanza, il sistema permette a due persone di **stabilire una chiave segreta** per comunicazioni sicure, anche se stanno usando un canale pubblico non sicuro.
La sicurezza del protocollo
Un sistema basato sull'ipotesi di Diffie-Hellman e sui logaritmi discreti, non è necessariamente più sicuro di RSA.
La sicurezza del protocollo di Diffie-Hellman si basa sulla difficoltà di calcolare il logaritmo discreto.
Ad esempio, dato \( g^{e} \mod p \), è molto difficile risalire a \( e \).
Nota. Per fare un confronto, è più veloce rispetto a RSA, in quanto le operazioni di moltiplicazione e esponenziazione modulari sono più efficienti. Inoltre, richiede chiavi di lunghezza minore per garantire la stessa sicurezza rispetto a RSA.
D'altra parte se l'ipotesi di Diffie-Hellman fosse violata (o il logaritmo discreto fosse risolvibile in modo efficiente), l'intero sistema diventerebbe insicuro.
In generale, entrambi i sistemi (RSA e Diffie-Hellman) sono sicuri, ma il sistema basato sul logaritmo discreto è generalmente più efficiente per la condivisione di chiavi private, mentre RSA è più versatile per la crittografia diretta dei messaggi.
Per una maggiore sicurezza oggi potrei considerare un approccio ibrido che combina i vantaggi di entrambi i sistemi.
Nota. Sia il sistema RSA che il logaritmo discreto (Diffie-Hellman) potrebbero diventare insicuri con l'arrivo dei computer quantistici perché l'algoritmo di Shor può fattorizzare numeri grandi in modo efficiente. Quindi, nel tempo potrebbero diventare vulnerabili. Quindi, nel futuro saranno necessarie alternative crittografiche come la crittografia post-quantistica.
Pro e contro del protocollo di Diffie-Hellman
Questo metodo consente di creare una chiave condivisa in modo sicuro su un canale non protetto.
Il calcolo della chiave condivisa è veloce e non richiede uno scambio di chiavi private.
Può essere combinato con cifrari moderni per fornire cifratura sicura.
D'altra parte, il protocollo Diffie-Hellman da solo non garantisce autenticità perché si espone al rischio del Man-in-the-Middle (MitM).
Esempio. Un attaccante potrebbe inserirsi nel mezzo e fingere di essere \( A \) con \( B \), o viceversa. Per mitigare questo rischio, si usa autenticazione tramite certificati.
Un altro handicap è che non cifra direttamente i messaggi. È necessario un cifrario simmetrico (ad esempio AES) per cifrare e decifrare i dati.
E così via.
