3 Diffie-Hellman

Il protocollo di Diffie-Hellman permette a due interlocutori che non hanno mai avuto nessun precedente contatto di accordarsi su una chiave segreta utilizzando un canale pubblico. Alcune definizioni necessarie per poter illustrare il protocollo:

Sia $\mathbb{Z}$ l'insieme dei numeri interi.
Un numero $p\in \mathbb{Z}$ è detto primo se è divisibile solo per e per sé stesso.
Un numero $p\in \mathbb{Z}$ si dice primo rispetto a $q\in \mathbb{Z}$ se il massimo comune divisore tra e è . Si dice anche che e sono primi tra loro.
Sia $\mathbb{Z}_{p}$ l'insieme dei numeri interi tra e compresi, ovvero l'insieme $\left\{ 0,...,p-1\right\}$ .
Sia $\mathbb{Z}_{p}^{*}$ il sottoinsieme di $\mathbb{Z}_{p}$ comprendente solo i numeri primi rispetto a . Se è un numero primo allora $\mathbb{Z}_{p}^{*}=\left\{ 1,...,p-1\right\}$ .
Sia un numero intero e un intero positivo, allora indichiamo con $a \bmod m$ il resto della divisione di per , ovvero $a \bmod m=a-\left\lfloor \frac{a}{m}\right\rfloor m$ (dove il simbolo $\left\lfloor x\right\rfloor$ indica l'intero inferiore di ).
Siano e due numeri interi e un intero positivo, allora diciamo che $a \equiv b \pmod{m}$ se $a \bmod m = b \bmod m$ , ovvero se divide .
Un numero $\alpha \in \mathbb{Z}_{p}^{*}$ è detto elemento generatore di $\mathbb{Z}_{p}^{*}$ se il più piccolo numero tale che $\alpha ^{q}\equiv 1 \pmod{p}$ è .

Detti Bob e Alice i due interlocutori, il protocollo procede come segue:

Bob e Alice si accordano pubblicamente su un numero primo $p$ e su un numero $\alpha$ che sia elemento generatore di $\mathbb{Z}_{p}^{*}$ .
Alice sceglie un numero $a_{1}$ tale che $1\leq a_{1}\leq p-2$ , calcola $b_{1}=\alpha ^{a_{1}} \bmod p$ e lo manda a Bob.
Bob sceglie un numero $a_{2}$ tale che $1\leq a_{2}\leq p-2$ , calcola $b_{2}=\alpha ^{a_{2}} \bmod p$ e lo manda ad Alice.
La chiave segreta è $K=\alpha ^{a_{1}a_{2}} \bmod p$ : Alice può calcolarla come $K=b^{a_{1}}_{2} \bmod p$ , mentre Bob può calcolarla come $K=b^{a_{2}}_{1} \bmod p$ .

La sicurezza del protocollo di Diffie-Hellman, ovvero il fatto che un intruso non possa calcolare la chiave $K$ avendo a disposizione solo i dati pubblici $p,\alpha ,b_{1},b_{2}$ , si basa sulla congettura dell'intrattabilità del problema dei logaritmi discreti in $\mathbb{Z}_{p}$ , per cui conoscendo solo i dati pubblici è molto difficile ricavare $a_{1}$ e $a_{2}$ . Così com'è, ovvero senza alcuna forma di autenticazione (come ad esempio dei certificati), è però soggetto ad un attacco di tipo man-in-the-middle. Se infatti un intruso, che chiamiamo Oscar, si pone nel mezzo della comunicazione può intercettare $b_{1}$ e $b_{2}$ e mandare, rispettivamente, ad Alice un valore $b_{3}=\alpha ^{a_{3}} \bmod p$ e a Bob un valore $b_{4}=\alpha ^{a_{4}} \bmod p$ (calcolati a partire da dei valori $a_{3}$ e $a_{4}$ scelti da lui). In questo modo Oscar riuscirà a stabilire una chiave $K_{1}=\alpha ^{a_{1}a_{3}} \bmod p$ con Alice e una chiave $K_{2}=\alpha ^{a_{2}a_{4}} \bmod p$ con Bob, mentre Alice e Bob penseranno di essersi accordati su una chiave tra di loro: così Oscar avrà la successiva comunicazione tra Bob e Alice in chiaro, e potrà leggere i messaggi, modificarli, inserirne altri.