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 ga [mod p].
  • Bob fa el mateix amb el nombre b.
  • Alice, elevant el nombre rebut de Bob a la potència a, obté gba [mod p].
  • Bob fa el càlcul anàleg i obté gab [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 gab [mod p].

Exemple modifica

Alice
Secret Públic Càlcul
p, g
a
ga [mod p]
(gb [mod p])a [mod p]
 
 
=
Bob
Càlcul Públic Secret
p, g
b
gb [mod p]
(ga [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 ga [mod p] = 3⁶ [23] = 16
  4. Bob escull al seu torn un nombre secret b =15
  5. Bob envia a Alice el valor gb [mod p] = 315 [23] = 12
  6. Ara Alice pot calcular la clau secreta: (gb[mod p])a [mod p] = 12⁶ [23] = 9
  7. Bob fa el mateix i obté la mateixa clau que Alice: (ga [mod p])b [mod p ] = 1615 [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 pn per obtenir el residu ([mòdul]). Els grups tenen la propietat associativa de les potències, la igualtat (gb)a [p] = (ga)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 gab a partir de ga i gb, 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 ga [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 gab [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 ga [p] i gb [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 ga [p] i gb [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 gb ' [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

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