In crittografia , lo scambio di chiavi Diffie-Hellman , dal nome dei suoi autori Whitfield Diffie e Martin Hellman , è un metodo, pubblicato nel 1976, con il quale due agenti , convenzionalmente chiamati Alice e Bob , possono concordare un numero (che possono usare come un chiave per crittografare la conversazione successiva) senza che un terzo agente chiamato Eve possa scoprire il numero, anche dopo aver ascoltato tutti i loro scambi. Questa idea ha vinto ai due autori il Premio Turing nel 2015 .
Diamo prima una spiegazione intuitiva facendo un'analogia con i colori. L'obiettivo è che Alice e Bob si mettano d'accordo su un colore segreto, senza che Eve possa saperlo. Questa spiegazione è pittorica e non ha senso pratico, ma aiuta a comprendere l'essenza dello scambio di chiavi Diffie-Hellman. Partiamo dal presupposto che gli agenti possono mescolare i colori, ma che è difficile (soprattutto per Eve!) Estrarre i colori usati per fare una miscela. Il principio è il seguente.
Alla fine del protocollo, Alice e Bob hanno lo stesso colore marrone, che rappresenta il colore segreto condiviso. Supponendo che sia difficile per Eva estrarre i colori usati per ottenere i colori pubblici arancione e blu, Eva non conosce il colore marrone finale.
Nel principio originale descritto di seguito, viene scelto un numero primo p . I "colori" sono numeri modulo p. La miscelazione di due colori consiste nell'elevare un numero a una certa potenza modulo p. Trovare i colori usati in una miscela corrisponde all'inversione dell'elevamento a potenza, che è un difficile problema algoritmico.
Descriviamo il principio originale.
Alla fine del protocollo, sia Alice che Bob conoscono il numero g ab [mod p ] ma non Eve. Poiché è difficile invertire l' esponenziazione in un campo finito (o su una curva ellittica), cioè calcolare il logaritmo discreto , Eva non può scoprirlo, quindi non può calcolare g ab [mod p ].
Nella descrizione sopra, Alice e Bob stanno lavorando nel campo finito Z / p Z , scambieranno i numeri modulo p . In generale, lo scambio di chiavi Diffie-Hellman generalizza a qualsiasi gruppo ciclico finito (invece di accordarsi su un numero primo p, concordano su un gruppo finito). Questo gruppo finito può essere un campo finito , di cui usano solo la moltiplicazione, o una curva ellittica .
In pratica, possiamo prendere un numero primo p di Sophie Germain (tale che anche q = 2p + 1 primo) di grande dimensione e un generatore g in Z / pZ (g è quindi primo con p-1).
Il metodo utilizza la nozione di gruppo , ad esempio il gruppo moltiplicativo di interi modulo p , dove p è un numero primo: in questo caso, le operazioni matematiche (moltiplicazione, potenza, divisione) vengono eseguite modulo p, cioè - diciamo per mantenendo solo il resto della divisione euclidea di p. Poiché i gruppi hanno la proprietà dell'associatività , l'uguaglianza ( g b ) a = ( g a ) b è valida ed entrambe le parti ottengono effettivamente la stessa chiave segreta.
La sicurezza di questo protocollo sta nella difficoltà del problema del logaritmo discreto: affinché Eva trovi g ab da g a e g b , deve elevare l'uno o l'altro rispettivamente alla potenza bo alla potenza a . Ma dedurre a (risp. B ) da g a (risp. G b ) è un problema che non sappiamo come risolvere efficacemente nel caso generale. Eve non è quindi in grado (computazionalmente) di dedurre dalle informazioni g a , g b , g e p , il valore di g ab .
Tuttavia, il gruppo di partenza deve essere ben scelto e i numeri utilizzati devono essere abbastanza grandi, ad esempio per evitare un attacco di ricerca esaustivo . Attualmente vengono generalmente utilizzati numeri primi p di dimensione 2048 bit (dell'ordine di 600 cifre in scrittura decimale), per i quali la risoluzione del logaritmo discreto non è considerata fattibile. Se dovesse emergere una soluzione pratica per risolvere un logaritmo discreto, potrebbero cadere altri sistemi crittografici , in particolare il sistema ElGamal , che si basa sullo stesso principio.
Questo protocollo è vulnerabile all '" attacco man-in-the-middle ", che coinvolge un aggressore in grado di leggere e modificare tutti i messaggi scambiati tra Alice e Bob.
Questo attacco si basa sull'intercettazione di g a e g b , che è facile poiché vengono scambiati in chiaro; si presume che l' elemento g sia conosciuto da tutti gli aggressori. Per trovare i numeri uno e b e quindi rompere completamente i scambio, sarebbe necessario calcolare il logaritmo discreto di g una e g b , che è praticamente impossibile.
Ma un aggressore può mettersi tra Alice e Bob, intercettare la chiave g a inviata da Alice e inviare a Bob un'altra chiave g a ' , fingendo di essere Alice. Allo stesso modo, può sostituire la chiave g b inviata da Bob ad Alice con una chiave g b ' , fingendo di essere Bob. L'aggressore quindi comunica con Alice utilizzando la chiave condivisa g ab ' e comunica con Bob utilizzando la chiave condivisa g a'b , Alice e Bob credono di comunicare direttamente. Questo è chiamato "attacco man-in-the-middle".
Alice e Bob credono di essersi scambiati una chiave segreta quando in realtà hanno scambiato ciascuno una chiave segreta con l'aggressore, l'uomo al centro.
La classica soluzione alternativa per questo attacco è firmare scambi di valore utilizzando una coppia di chiavi asimmetriche certificata da una terza parte fidata o le cui metà pubbliche sono state precedentemente scambiate da entrambi i partecipanti.
Alice può così essere certa che la chiave che riceve provenga effettivamente da Bob e viceversa per Bob.