Swappa :: Scambio di chiavi Diffie-Hellman

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'''?

to:

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'''?

Restore

June 26, 2008, at 02:54 PM by dario -

Added lines 88-90:

!!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^''''.

Changed lines 92-95 from:

... da completare ...

!!Generalizzazione per 3 persone
... da completare

to:

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.

Restore

June 26, 2008, at 01:50 PM by dario -

Changed line 77 from:

È vero che '''3'^(10) / 2^' != 1 mod p '''? '''3'^5^' mod 11 = 1 quindi NO!\\

to:

È vero che '''3'^(10) / 2^' != 1 mod p '''? '''3'^5^' mod 11 = 1''' quindi NO!\\

Restore

June 26, 2008, at 01:49 PM by dario -

Added lines 1-94:

(:title Scambio di chiavi Diffie-Hellman:)
%titolo%''':: Scambio di chiavi Diffie-Hellman ::'''

[[Torna alla pagina di crittografia -> 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 Z'_p_''^*^'

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'_11_' e il numero 2, che evidentemente appartiene a Z'_11_'.
2'^1^' = '''2''' mod 11
2'^2^' = '''4''' mod 11
2'^3^' = '''8''' mod 11
2'^4^' = 16 = '''5''' mod 11
2'^5^' = 32 = '''10''' mod 11
2'^6^' = 64 = '''9''' mod 11
2'^7^' = 128 = '''7''' mod 11
2'^8^' = 256 = '''3''' mod 11
2'^9^' = 512 = '''6''' mod 11
2'^10^' = 1024 = '''1''' mod 11

Vedete quindi che, in un qualsiasi ordine, le potenze di 2 mod 11 generano tutti i valori di Z'_11_'. 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'^e1^'p2'^e2^'...pn'^en^'''', in cui i vari '''p'^i^'''' 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'^5^' mod 11 = 1 quindi NO!\\
Ciò vuol dire che 3 '''non è''' un generatore di Z'_11_'.

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'_11_'.

!!Attacco meet in the middle
... da completare ...

!!Generalizzazione per 3 persone
... da completare

[[Torna alla pagina di crittografia -> Crittografia]]

Restore