Comunicare in segreto: la soluzione di Diffie ed Hellman

A chi non è mai capitato, magari da bambino, di utilizzare l’alfabeto muto, quella serie di gesti e simboli tracciati con le dita che rispecchiano il normale alfabeto ma che possono essere utilizzati per comunicare un messaggio senza far rumore? E a chi non è mai capitato di utilizzarlo per comunicare un messaggio in modo tale da non essere compreso dagli altri bambini, magari compagni di classe, ignari delle corrispondenze esatte tra lettere dell’alfabeto ordinario e i simboli tracciati nell’aria?

Se vi è capitato allora, nel vostro piccolo e in maniera molto approssimativa, stavate sperimentando un metodo crittografico. L’obiettivo principale della crittografia infatti, si può riassumere, semplificando, proprio in questo: garantire la possibilità di scambiare un messaggio (trasformato nel messaggio cifrato) che non sia comprensibile a coloro che potrebbero intercettarlo ma che in qualche modo possa essere decifrato e compreso dai parlanti in gioco (che devono poter accedere al cosiddetto testo in chiaro).

Per operare il passaggio da testo in chiaro a messaggio cifrato e viceversa viene spesso utilizzata la chiave di cifratura, che, proprio come per un lucchetto, consente a chi la possiede di operare la conversione suddetta. Proprio in quest’ultima frase risiede uno dei problemi che ha avuto maggiore rilevanza, anche storicamente parlando, nel mondo della crittografia: come è possibile condividere una chiave tra due parlanti in modo tale che nessun altro se non questi abbia accesso ad essa? Una prima soluzione potrebbe comprendere la condivisione delle chiavi con cui si vuole crittografare il canale in oggetto tramite un altro mezzo di comunicazione. Così facendo, tuttavia, abbiamo solamente spostato il problema al gradino successivo: chi ci garantisce che il canale su cui stiamo comunicando sia sicuro? E se vogliamo crittografare anch’esso, non ci serve forse condividere una ulteriore chiave? Se la chiave in oggetto dovesse essere condivisa tra i soggetti (diciamo Alice e Bob) mentre la conversazione avviene ancora in chiaro, infatti, non sarebbe difficile per un attaccante intercettare questo messaggio, invalidando di conseguenza la segretezza della comunicazione. Con un parallelismo non preciso ma efficace, potremmo dire che la situazione è simile al momento in cui il vostro compagno di banco ha imparato l’alfabeto muto: anche lui, da quel momento, è stato in grado di intercettare il vostro messaggio cifrato e di decifrarlo accedendo al testo in chiaro, ciò che voi e il vostro compagno volevate comunicare segretamente. Per evitare dunque un regresso all’infinito, dove si istituiscono infiniti canali crittografati tramite i quali condividere la chiave di crittografia successiva, si è storicamente affermato il ricorso ad un mezzo alternativo attraverso cui comunicare segretamente tale valore (magari tramite una linea telefonica confidenziale, un servizio di posta particolarmente affidabile…). Questo aspetto strutturale, tuttavia, presta il fianco ad una importante problematica: sembra necessario che, in qualche modo, i due parlanti debbano precedentemente disporre di un mezzo sicuro tramite cui comunicare.

La soluzione di Diffie ed Hellman: una visione qualitativa

Risale ad un paper del 19761, dal titolo New Directions in Cryptography, il tentativo da parte di Whitfield Diffie e Martin Hellman di ovviare proprio a questo problema ricorrente, il tentativo cioè di istituire un metodo sicuro tramite cui due soggetti possano scambiarsi una chiave di crittografia pur essendo il canale entro cui questo valore viene comunicato non protetto da crittografia. Per realizzare tale proposito Diffie ed Hellman escogitarono un sistema in più passaggi in grado di costruire una chiave la cui conoscenza sembra essere preclusa a qualsiasi soggetto eccetto quelli coinvolti in suddetto procedimento. In questo paragrafo tenteremo di affrontare il funzionamento di questo metodo in maniera qualitativa, tralasciando la matematica (che comunque sarà affrontata nel prossimo paragrafo, per i curiosi), tramite una metafora semplice ma potente (l’esemplificazione di tale procedimento è schematizzata nel disegno seguente).

Immaginiamo due interlocutori, Alice e Bob, ciascuno dei quali possiede un bicchiere, all’interno del quale si trova dell’acqua con del colorante. I colori di Alice e Bob sono differenti e ciascuno viene mantenuto segreto. Immaginiamo ora che Alice e Bob abbiano a disposizione un altro bicchiere con del colorante, questa volta uguale per entrambi, e di dominio pubblico: tutti, anche un eventuale attaccante (in letteratura Eve, da eavesdropper, colui/colei che intercetta, che origlia), conoscono la natura di questo colore comune. Il primo passo del procedimento, a questo punto, consiste nel prendere il colore comune e, privatamente, mescolarlo insieme alla tintura segreta: sia Bob che Alice compiono questa operazione, ciascuno producendo un mix tra il proprio colore privato e quello comune. Fatto questo, Alice e Bob si scambiano il mix ottenuto sul canale in chiaro, quindi sotto gli occhi di tutti, attaccante compreso. Ora, nuovamente in maniera privata, essi aggiungono al bicchiere ottenuto dalla controparte il proprio colore segreto. Così facendo sia Alice che Bob hanno ottenuto un colore del tutto identico, che equivale alla chiave utile per istituire un canale crittografato, a partire da una comunicazione su di un canale pubblico. L’efficacia di questo algoritmo poggia su di un punto fondamentale: l’incapacità dell’attaccante di ricavare la chiave condivisa dalle informazioni in proprio possesso, ovvero – restando nella metafora – l’incapacità di ricavare il colore segreto avendo a disposizione il colore comune e i rispettivi mix di colori di Alice e Bob, scambiati nella prima fase del procedimento. La metafora è particolarmente efficace in quanto rispecchia una caratteristica che contraddistingue la matematica che costituisce l’ossatura di questo metodo: ricavare i colori segreti di Alice e Bob conoscendo il colore comune e i rispettivi mix è una procedura difficoltosa (pensiamo a quando mescoliamo due differenti bicchieri di acqua, macchiati di colore, che abbiamo utilizzato per sciacquare dei pennelli). In maniera più propria, in ambito informatico tale procedura richiede un utilizzo di risorse enormi, in termini di capacità computazionale e tempo.

Diffie–Hellman: cenni matematici

Vediamo ora in maniera più tecnica l’articolazione di questo metodo, prendendo in considerazione anche un esempio numerico:

The simplest and the original implementation of the protocol uses the multiplicative group of integers modulo p, where p is prime, and g is a primitive root modulo p. These two values are chosen in this way to ensure that the resulting shared secret can take on any value from 1 to p–1.

1. Alice and Bob agree to use a modulus p = 23 and base g = 5 (which is a primitive root modulo 23).

2. Alice chooses a secret integer a = 4, then sends Bob A = ga mod p

A = 54 mod 23 = 4

3. Bob chooses a secret integer b = 3, then sends Alice B = gb mod p

B = 53 mod 23 = 10

4. Alice computes s = Ba mod p

s = 104 mod 23 = 18

5. Bob computes s = Ab mod p

s = 43 mod 23 = 18

6. Alice and Bob now share a secret (the number 18).2

Come ben illustrato nell’esempio, la procedura di creazione di una chiave condivisa inizia con la scelta di due numeri p e g3, conosciuti dai due soggetti. Il passaggio successivo consiste nella scelta di due numeri interi differenti da parte di ognuno: a per Alice, b per Bob. A questo punto Alice invia a Bob il numero A, risultato del calcolo di ga mod p e Bob invia ad Alice il corrispettivo numero B, calcolato come segue: gb mod p. L’ultimo passaggio consiste nel computare s, la shared key, tramite un nuovo elevamento a potenza: Alice esegue tale passaggio computando Ba mod p e Bob lo fa tramite il calcolo di Ab mod p. Si nota agevolmente che gli unici valori che vengono resi noti pubblicamente nel canale in chiaro sono p, g, A e B (rispettivamente, nella nostra metafora, il colore comune e i mix di colori di Alice e di Bob): un eventuale soggetto interessato alla conversazione avrebbe solamente i succitati valori numerici a disposizione per tentare di rompere la cifratura dei messaggi. Come evidenziato nell’esempio numerico, s non viene mai condivisa e tutti i passaggi di computazione che vengono svolti da Alice e Bob sono operati privatamente. Più in generale, dunque, possiamo riassumere il procedimento esemplificato poco sopra nel seguente modo:

Alice and Bob agree on a finite cyclic group G of order n and a generating element g in G. (This is usually done long before the rest of the protocol; g is assumed to be known by all attackers.) The group G is written multiplicatively.

1. Alice picks a random natural number a, where 1 ≤ a < n, and sends ga to Bob.

2. Bob picks a random natural number b, which is also 1 ≤ b < n, and sends gb to Alice.

3. Alice computes (gb)a.

4. Bob computes (ga)b.

Both Alice and Bob are now in possession of the group element gab, which can serve as the shared secret key. The group G satisfies the requisite condition for secure communication if there is not an efficient algorithm for determining gab given g, ga, and gb.4

Conclusioni

In questo breve scritto abbiamo considerato in maniera qualitativa e poi maggiormente tecnica il funzionamento della soluzione di Diffie ed Hellman, cercando di comprenderne l’idea alla base e la matematica che ne stabilisce l’efficacia. Pur essendo presenti delle soluzioni che, in casi specifici, consentono di mettere in crisi tale algoritmo5 esso rimane largamente utilizzato in molte delle procedure che richiedono la condivisione di una chiave segreta senza la possibilità di poter comunicare su di un canale non pubblico. Di capitale importanza rimane il lavoro di Diffie ed Hellman come capitale rimane lo spirito e l’inventiva che li hanno guidati nell’analisi di un problema storico e nell’elaborare una soluzione ormai considerata una pietra miliare nella storia della crittografia.


1 W. DIFFIE, M. HELLMAN, New Directions in Cryptography, Iee Transactions on Information Theory, Vol. IT-22, no. 6, November 1976. Url: <https://www-ee.stanford.edu/~hellman/publications/24.pdf>.

2 WIKIPEDIA, Diffie – Hellman key exchange. Url: <https://en.wikipedia.org/wiki/DiffieE2%80%93Hellman_key_exchange>.

3 Dove g è primo e p e una radice primitiva modulo p, semplicemente detta generatore.

4 WIKIPEDIA, Diffie – Hellman key exchange. Ibidem.

5 D. ADRIAN, K. BHARGAVAN, Z. DURUMERIC, P. GAUDRY, M. GREEN, J. A. HALDERMAN, N. HENINGER, D. SPRINGALL, E. THOME, L. VALENTA, B. ANDERSLOOT, E. WUSTROW, S. ZANELLA-BEGUELIN, P. ZIMMERMAN, Imperfect Forward Secrecy: How Diffie–Hellman Fails in Practice.

Dialoga con noi!