L'algoritmo Diffie-Hellman risale al 1976 ed è quindi uno dei primi algoritmi a chiave pubblica; gli autori furono anche i primi a proporre l'idea dei cifrari a chiave pubblica. Va chiarito che questo algoritmo non è un cifrario nel senso che non ha nessun messaggio da cifrare, si limita a generare una chiave pubblica tra due corrispondenti.

L'algoritmo è particolarmente adatto alla generazione di una chiave segreta tra due corrispondenti che comunicano attraverso un canale non sicuro (pubblico). La sua sicurezza si basa sulla complessità computazionale del calcolo del logaritmo discreto. Sulla stessa idea si basa il cifrario di Elgamal che è un vero cifrario come RSA con il quale si può trasmettere in modo segreto una chiave ma anche un messaggio breve, breve perché si tratta di sistemi molto più lenti dei cifrari a chiave segreta come DES a AES.

Supponiamo di avere i soliti Alice e Bruno che vogliono scambiarsi una chiave segreta in modo sicuro.

1. Alice genera e comunica pubblicamente un numero primo $N$ molto elevato (p.es. 1024 bit, circa 300 cifre decimali) e un generatore g (che esiste sicuramente essendo N primo); si potrebbero anche usare due numeri $N, g$ pubblicati da un qualche ente pubblico.
2. Alice genera un numero casuale $a \lt N $ e calcola $A = g^a \pmod N$, ed invia $A$ a Bruno. A questo punto $N, g, A$ sono pubblici, $a$ è noto solo ad Alice.
3. Bruno genera un numero casuale $b \lt N $ e calcola $B = g^b \pmod N$, ed invia $B$ ad Alice. A questo punto $N, g, A, B$ sono pubblici, $a$ è noto solo ad Alice, $b$ solo a Bruno.
4. Alice calcola $k = B^a \pmod N$.
5. Alice calcola $k = A^b \pmod N$.

Inutile aggiungere che i due numeri $k$ sono uguali! Infatti entrambe valgono $g^{ab} \mod N$.

A questo punto Alice e Bruno possono usare $k$ come chiave per comunicare con un cifrario simmetrico p.es. DES.

Esempio

1. Alice sceglie $N = 17, g = 3$ (3 è generatore di 17).
2. Alice sceglie $a = 6$ e quindi $A = 3^6 \mod 17 = 15$.
3. Bruno sceglie $b = 11$ e quindi $B = 3^{11} \mod 17 = 7$.
4. Alice calcola $k = 7^6 \mod 17 = 9$.
5. Bruno calcola $k = 15^{11} \mod 17 = 9$.

La chiave segreta è quindi $9$.

Sicurezza

La cosa importante per la sicurezza è che un terzo che intercettasse i quattro numeri $N, g, A, B$ non sarebbe in grado di ottenere $k = g^{ab} \mod N$ non conoscendo né $a$ né $b$. In realtà basterebbe calcolarli $a = \log_g{A} \quad e \quad b = \log_g{B}$ ma il calcolo del logaritmo discreto è computazionalmente proibitivo per numeri molto grandi (1024 bit e oltre).

Come altri sistemi a chiave pubblica anche DH è però esposto all'attacco del terzo uomo interposto. Nel nostro esempio immaginiamo che Carlo intercetti il numero A che Alice invia a Bruno e, fingendo di essere Bruno, generi un suo numero B e lo invii ad Alice. A questo punto Alice e Carlo generano la chiave segreta k e comunicano via DES; e Carlo può tranquillamente leggere tutti i messaggi che Alice crede di inviare a Bruno! Peggio ancora: Carlo può ripetere il gioco anche con Bruno fingendosi Alice e di qui in avanti, intercettare e leggere tutta la corrispondenza tra gli inconsapevoli Alice e Bruno.

Per prevenire simili attacchi la soluzione è anche qui quella di usare un ente certificatore che garantisca l'identità dei corrispondenti. Alice e Bruno potranno p.es. identificarsi con un meccanismo di firma digitale, utilizzando le chiavi pubbliche fornite dall'ente certificatore.

Di questo tipo è il protocollo Diffie-Hellman autenticato proposto da Diffie, van Oorschot, e Wiener nel 1992 (DVW92).

• Paolo Ferragina, Fabrizio Luccio, Crittografia, Principi, Algoritmi, Applicazioni, Boringhieri, Torino, 2001, pag. 128 → eBook