Swappa : Uni / Scambio di chiavi Diffie-Hellman

 :: 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 g^x mod p
• Bob calcola un y a caso, ed invia ad Alice il valore g^y mod p

Il segreto è dato da g^xy mod p

• Alice riceve g^y e conosce x: è quindi in grado di fare (g^y)^x mod p
• Bob riceve g^x e conosce y: è quindi in grado di fare (g^x)^y mod p

Ricordo che g^xy è uguale a g^yx.

Perché è sicuro

È sicuro perché un attaccante che vede transitare il valore g^x o g^y non è in grado di ricavare, da esso, la x o la y.

O meglio, sarebbe in grado, ma il problema è calcolare il logaritmo discreto:
g^x = 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 Z_p^*, è quel numero appartenente all'insieme Z_p^*, il quale, elevato a potenza per ciascuno degli elementi di Z_p^*, mi dà a sua volta tutti gli elementi di Z_p^*, in un qualche ordine.

Per capirci subito, prendiamo il campo Z₁₁ e il numero 2, che evidentemente appartiene a Z₁₁.

 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 Z₁₁. Capito che cos'è il generatore?

Come faccio a calcolare il generatore di un certo Z_p?

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 p1^e1p2^e2...pn^en, in cui i vari pⁱ sono i fattori di p-1, e i vari e_i 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 Z_p

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 ? 3⁵ mod 11 = 1 quindi NO!
Ciò vuol dire che 3 non è un generatore di Z₁₁.

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 Z₁₁.

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 g^xyz.

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 g^c, 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