L’algoritmo di Diffie-Hellman è un algoritmo di crittografia asimmetrica che permette a due persone di scambiarsi in pubblico una chiave comune (da utilizzare poi per comunicare tramite crittografia simmetrica). L’algoritmo è particolarmente semplice se formulato in termini di teoria dei gruppi.
L’idea è la seguente. Sia $G$ un gruppo ciclico finito (ovvero $G = \Z_N$ per un qualche $N$, tipicamente molto grande). Arduino e Beatrice si mettono d’accordo (in pubblico, cioè queste informazioni sono disponibili a tutti) sul gruppo $G$ da scegliere e su un generatore qualsiasi $g \in G$. Eseguono poi le seguenti operazioni:
- Arduino sceglie un numero naturale $a$, calcola $g^a$ e lo manda a Beatrice.
- Beatrice sceglie un numero naturale $b$, calcola $g^b$ e lo manda ad Arduino.
- Arduino (conoscendo $a$ e $g^b$) calcola la chiave comune $K \equiv (g^b)^a = g^{ab}$.
- Beatrice (conoscendo $b$ e $g^a$) calcola la chiave comune $K \equiv (g^a)^b = g^{ab}$.
L’algoritmo funziona perché $g^{ab}=g^{ba}$. In particolare lo scambio delle informazioni può avvenire anche su un canale non sicuro, e questo in linea di massima non permette di ricavare informazioni sulla chiave. Infatti la sicurezza dell’algoritmo si basa sulla difficoltà di due problemi intermedi:
- Il problema di ricavare $a$ conoscendo $g$ e $g^a$, noto come problema del logaritmo discreto, perché appunto si tratta di trovare l’inversa della funzione esponenziale (sebbene con valori in un gruppo finito). Non è noto un algoritmo con tempo polinomiale (nel numero di bit, che sarebbe $\approx \log{\abs{G}}$) nel caso generale. In alcuni casi speciali (cioè se scegliamo “male” $\abs{G}$), allora è possibile il calcolo in tempo polinomiale e Diffie-Hellman è insicuro. Per evitare questo fenomeno $\abs{G}$ deve avere almeno un fattore primo grande.
- Il problema di ricavare la chiave $g^{ab}$ conoscendo $g$, $g^a$ e $g^b$ è anch’esso difficile da risolvere nel caso generale.
Un problema con questo algoritmo è che è insicuro rispetto ad un attaccante che si ponga “in mezzo” ad A e B, intercettando la loro corrispondenza e fingendosi l’altro davanti ad ognuno.