Intercanvi de claus Diffie-Hellman

En criptografia, l'intercanvi de claus Diffie-Hellman, que pren el nom dels seus autors Whitfield Diffie i Martin Hellman,^[1] és un mètode per la qual dues persones designades convencionalment Alice i Bob es poden posar d'acord sobre un nombre (que poden fer servir com clau per xifrar la conversa que segueix a l'intercanvi) sense que una tercera persona anomenada Eva pugui descobrir el nombre encara que estigui escoltant.

Principi[modifica]

Principi d'un intercanvi de claus Diffie-Hellman

A continuació es detallen els passos en l'intercanvi de claus:

Alice i Bob escullen un grup (o bé un cos finit, del qual no utilitzen més que la multiplicació, o bé una corba el·líptica i un element generador g d'aquest grup.
Alice escull un nombre a l'atzar a, eleva g a la potència a, i diu a Bob g^a [mod p].
Bob fa el mateix amb el nombre b.
Alice, elevant el nombre rebut de Bob a la potència a, obté g^ba [mod p].
Bob fa el càlcul anàleg i obté g^ab [mod p], que és el mateix. Però com que és difícil invertir la funció exponencial en un cos finit, és a dir, calcular el logaritme discret, llavors Eva no pot descobrir a i b, i per tant no pot calcular g^ab [mod p].

Exemple[modifica]

Alice
Secret	Públic	Càlcul
	p, g
a
		g^a [mod p]
	…
	(g^b [mod p])^a [mod p]

$\rightarrow$

$\leftarrow$

=

Bob
Càlcul	Públic	Secret
	p, g
		b
	…
g^b [mod p]
	(g^a [mod p])^b [mod p]

Alice i Bob escullen un nombre primer p i una base g. En el nostre exemple p=23 i g=3
Alice escull un nombre secret a =6
Envia a Bob el valor g^a [mod p] = 3⁶ [23] = 16
Bob escull al seu torn un nombre secret b =15
Bob envia a Alice el valor g^b [mod p] = 3¹⁵ [23] = 12
Ara Alice pot calcular la clau secreta: (g^b[mod p])^a [mod p] = 12⁶ [23] = 9
Bob fa el mateix i obté la mateixa clau que Alice: (g^a [mod p])^b [mod p ] = 16¹⁵ [23] = 9

Fonament matemàtic[modifica]

El concepte fa servir la noció de grup multiplicatiu amb enters ([mòdul] p) amb p un nombre primer. En resum, les operacions matemàtiques (multiplicació, potència, divisió) es fan servir tals qual però el resultat s'ha de dividir entre pⁿ per obtenir el residu ([mòdul]). Els grups tenen la propietat associativa de les potències, la igualtat (g^b)^a [p] = (g^a)^b [p] és vàlida i les dues parts obtenen realment la mateixa clau secreta.

La seguretat d'aquest protocol resideix en la dificultat del problema del logaritme discret: perquè Eva trobi g^ab a partir de g^a i g^b, ha d'elevar l'un o l'altre a la potència b o a la potència a respectivament. Però deduir a (resp. b) gràcies a g^a [p ] (resp. g ^b [p]) és un problema que no se sap resoldre eficientment. Eva es troba per tant en la impossibilitat (des del punt de vista de potència de càlcul) de deduir g^ab [p].

Cal tanmateix que el grup de sortida sigui ben escollit i que els nombres que es fan servir siguin prou grans per evitar un atac per la força bruta.

L'atac de l'home del mig[modifica]

Aquest protocol és vulnerable a l'atac de l'home del mig que implica un agressor interposat capaç de llegir i de modificar tots els missatges intercanviats entre Alice i Bob.

Aquest atac es basa en la intercepció dels nombres g^a [p] i g^b [p] cosa que és fàcil, ja que són intercanviats en clar; l'element g se suposa conegut per tots els agressors.

Per trobar els nombres a i b i així trencar completament l'intercanvi, cal calcular el logaritme discret dels nombres g^a [p] i g^b [p], cosa impossible a la pràctica.

Però en l'atac de l'home del mig, l'agressor se situa entre Alice i Bob, intercepta la clau g ^a [p] enviada per Alice i envia a Bob una clau diferent g ^{a '} [p ], fent-se passar per Alice. Igualment, reemplaça la clau g ^b [p] enviada per Bob a Alice per una clau g^{b '} [p], fent-se passar per Bob. L'agressor pot així comunicar-se amb Alice fent servir la clau compartida g ^{ab '} [p] i comunicar-se amb Bob fent servir la clau compartida g ^a'b [p].

Alice i Bob creuen així haver intercanviat una clau secreta, mentre que en realitat tenen cadascun una clau secreta intercanviada amb l'agressor, l'home del mig.

Solució[modifica]

La forma clàssica d'aturar aquest atac consisteix a signar els intercanvis de valors amb l'ajuda d'un parell de claus asimètriques certificades per una tercera part fiable, o de las qual les meitats públiques han estat intercanviades abans pels dos participants.

Així Alice pot tenir la seguretat que la clau que rep prové efectivament de Bob, i inversament per a Bob.

Vegeu també[modifica]

Referències[modifica]

↑ Diffie, W. i M.E.Hellman. "New directions in cryptography", IEEE Transactions on Information Theory 22 (1976), pp. 644-654.

[1] Diffie, W. i M.E.Hellman. "New directions in cryptography", IEEE Transactions on Information Theory 22 (1976), pp. 644-654.

[1]