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

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

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

${\displaystyle \rightarrow }$ ${\displaystyle \leftarrow }$ =

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

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

Fonament matemàtic

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

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ó

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é

• Complexitat algorísmica
• criptografia asimètrica
• Martin Hellman
• Whitfield Diffie
• Ralph Merkle
• RSA
• ElGamal

Referències

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