:: Scambio di chiavi Diffie-Hellman ::
Torna alla pagina di crittografia
Che cos'è
Alice e Bob vogliono comunicarsi un segreto, in questo caso un numero segreto. Ma il canale su cui parlano non è sicuro. Come faranno i nostri eroi?
Come funziona
Devo calcolare due parametri iniziali
p = un numero primo
g = un numero generatore di Zp*
e questi due numeri sono diffusi pubblicamente.
Alice e Bob NON SANNO all'inizio quale chiave si scambieranno: entrambi la scopriranno alla fine!
Ad ogni modo, ecco quello che succede:
- Alice calcola un x a caso, ed invia a Bob il valore gx mod p
- Bob calcola un y a caso, ed invia ad Alice il valore gy mod p
Il segreto è dato da gxy mod p
- Alice riceve gy e conosce x: è quindi in grado di fare (gy)x mod p
- Bob riceve gx e conosce y: è quindi in grado di fare (gx)y mod p
Ricordo che gxy è uguale a gyx.
Perché è sicuro
È sicuro perché un attaccante che vede transitare il valore gx o gy non è in grado di ricavare, da esso, la x o la y.
O meglio, sarebbe in grado, ma il problema è calcolare il logaritmo discreto:
gx = a mod p
Conosco x, a e p: so calcolare qual'è quel numero x tale che, se elevo g alla x, ottengo a mod p?
Ci vuole molto ma molto tempo di calcolo, ecco perché è un problema difficile!
Che cos'è il generatore?
Il generatore, o radice primitiva, di Zp*, è quel numero appartenente all'insieme Zp*, il quale, elevato a potenza per ciascuno degli elementi di Zp*, mi dà a sua volta tutti gli elementi di Zp*, in un qualche ordine.
Per capirci subito, prendiamo il campo Z11 e il numero 2, che evidentemente appartiene a Z11.
21 = 2 mod 11
22 = 4 mod 11
23 = 8 mod 11
24 = 16 = 5 mod 11
25 = 32 = 10 mod 11
26 = 64 = 9 mod 11
27 = 128 = 7 mod 11
28 = 256 = 3 mod 11
29 = 512 = 6 mod 11
210 = 1024 = 1 mod 11
Vedete quindi che, in un qualsiasi ordine, le potenze di 2 mod 11 generano tutti i valori di Z11. Capito che cos'è il generatore?
Come faccio a calcolare il generatore di un certo Zp?
L'idea banale è: prendo tutti i possibili g, e faccio tutte le potenze finché non ne trovo uno che soddisfa la proprietà citata qui sopra.
Il problema ovviamente nasce quando p è molto ampio, e calcolare tutte le potenze di un numero diventa una cosa mostruosa.
Allora, uso il seguente sistema:
- Trovo la fattorizzazione di p-1: sarà una cosa del tipo p1e1p2e2...pnen, in cui i vari pi sono i fattori di p-1, e i vari ei sono i relativi esponenti.
- Scelgo un numero g a caso, minore di p
- Vedo se questo numero g rispetta il seguente sistema:
g(p-1) / p1 != 1 mod p
g(p-1) / p2 != 1 mod p
...
g(p-1) / pn != 1 mod p
Se per tutte le congruenze, g(p-1) / pn != 1, allora quel g è generatore di Zp
Facciamo un esempio, con p = 11 e g = 3.
Se p = 11, allora p-1 = 10, che si fattorizza come 10 = 2 * 5'.
Il sistema diventa:
3(10) / 2 != 1 mod 11
3(10) / 5 != 1 mod 11
È vero che 3(10) / 2 != 1 mod p ? 35 mod 11 = 1 quindi NO!
Ciò vuol dire che 3 non è un generatore di Z11.
Prendiamo invece g = 2:
2(10) / 2 != 1 mod 11
2(10) / 5 != 1 mod 11
2'^5^ = 10 mod 11
2'^2'^ = 4 mod 11
Questo vuol dire che il sistema è rispettato, e 2 è generatore di Z11.
Generalizzazione per 3 persone
Se sono 3 persone a volersi mettere d'accordo, cioè Alice, Bob e Charlie, il procedimento è semplice: ognuno dei tre si inventa un valore, x, y o z, e il segreto sarà composto da gxyz.
Attacco man in the middle
Se un attaccante riesce ad impossessarsi del canale sul quale Alice e Bob comunicano, può giocare un bello scherzetto ad entrambi. Si presuppone che il Cattivo sia in grado di intercettare tutti i messaggi provenienti da Alice o Bob, e reinviarli senza che questi si accorgano di nulla.
Come dicevamo all'inizio, i valori p e g sono pubblici. Quindi, quando Alice crede di comunicare con Bob, in realtà comunica con Cattivo, e quello che succede è che crea un segreto tra lei e Cattivo! Alice crede di condividerlo con Bob, invece lo condivide con Cattivo.
Allo stesso tempo, Cattivo si spaccia per Alice e comunica a Bob un valore gc, e in pratica concorda con Bob un'altra chiave.
Quello che succede è che Alice manda un messaggio a Cattivo, con la chiave concordata con Cattivo, mentre lei è invece convinta di mandare un messaggio a Bob con la chiave concordata con Bob. Idem per quest'ultimo.
Cattivo prende il messaggio da Alice, lo guarda tranquillamente, e lo reimpacchetta con la chiave di Bob, il quale è convinto di ricevere roba da Alice.
Torna alla pagina di crittografia