viernes, mayo 20, 2005

Apuntes sobre Criptografía V: Intercambio de claves de Diffie y Hellman

En el capítulo anterior expandimos un poco más nuestro conocimientos sobre los algoritmos de clave pública. Hoy veremos lo que se puede catalogar como el padre de estos algoritmos: el intercambio de claves seguro de Diffie y Hellman. Whitfiled Diffie y Martín Hellman en 1976 desarrollaron un protocolo para realizar el intercambio de claves e intentar así solventar el gran problema de los algoritmos simétricos. Básicamente el protocolo consiste en los siguientes pasos:

  • A y B generan un grupo multiplicativo (con inverso) p – siendo p primo - y un generador g de dicho primo. Estos dos valores son públicos.
  • A genera un número aleatorio a y le envía a B ga mod p.
  • B genera un número aleatorio b y le envía a A gb mod p.
  • B calcula (ga)b mod p = gab mod p, y borra b.
  • A calcula (gb)a mod p = gba mod p, y borra a.
  • La clave secreta que solo comparten A y B es gab mod p.

Si un intruso que conoce g y p y que intercepte ga mod p y gb mod p no podrá descubrir gab mod p porque es incapaz de descubrir el valor de a y b, a menos que resuelva un logaritmo en un campo discreto de números. Resolver este problema tiene un orden exponencial a p, lo que es lo mismo que para resolver este problema se necesitan "2 elevado a p" iteraciones del algoritmo, haced cuentas si p tiene una longitud de 1024 bits. Siendo conocido gab mod p – llamemosle R- g y p, tendría que resolver la siguiente ecuación para encontrar el valor de a: a = log g R mod p, esto es un logaritmo discreto.

Pero el intercambio de diffie-hellman es sensible a un ataque de “hombre en el medio” – “man in middle” es decir:

  • A genera un número aleatorio a y le envía a B ga mod p.
  • C intercepta ga mod p, genera un valor c y envía a B, gc mod p.
  • B genera un número aleatorio b y le envía a A gb mod p.
  • C intercepta gb mod p, genera un valor c y envía a A, gc mod p.
  • B calcula (gb)c mod p = gbc mod p, y borra b.
  • A calcula (ga)c mod p = gac mod p, y borra a.
  • C calcula (gc)b mod p = gcb mod p y (gc)a mod p = gac mod p
  • C a partir de este momento haría de puente entre las conversaciones de A y B, pudiendo hasta modificar los mensajes de ambos y falsear la comunicación.

Por último comentar que es posible ampliar el intercambio a más de dos individuos, ampliando hasta n individuos, al final todos acabarían calculando gabc mod p – en este caso n=3, basta con ir enviando los cálculos en anillo – A envía a B ga mod p, B envía gb mod p a C, etc.