El intercambio de claves Diffie-Hellman explicado

Durante miles de años, enviar un mensaje secreto significaba compartir antes una clave secreta en persona o mediante un mensajero. En 1976, dos investigadores de Stanford demostraron que dos partes podían crear una clave compartida de la nada, intercambiando mensajes a la vista de cualquiera. La idea abrió la era de la criptografía de clave pública y sigue actuando cada vez que un navegador muestra un candado.

Alice y Bob a ambos lados de un canal público, cada uno mezclando una pintura amarilla común con un color secreto, y ambos terminando con la misma mezcla mientras Eve observa
Alice y Bob a ambos lados de un canal público, cada uno mezclando una pintura amarilla común con un color secreto, y ambos terminando con la misma mezcla mientras Eve observa

El problema de la distribución de claves

Un cifrado como AES es tan seguro como su clave, y ambas partes necesitan la misma clave. Antes de 1976 la clave tenía que entregarse en secreto: por valija diplomática, mediante mensajeros de confianza o con libros de códigos impresos de antemano. Para dos desconocidos que quieren comunicarse de forma segura ahora mismo, por ejemplo una tienda y un cliente en internet, eso es imposible. El artículo de Whitfield Diffie y Martin Hellman «New Directions in Cryptography» resolvió el problema con un método que no necesita ningún secreto previo.

Aritmética en un reloj

El intercambio usa aritmética modular: cálculos en un reloj de p horas, donde p es un primo grande. En este reloj las potencias se comportan de forma notable. Si g es una raíz primitiva, los números g, g², g³, … mod p saltan de un lado a otro y pasan por cada hora de 1 a p − 1 antes de repetirse, en un orden que parece aleatorio. Calcular gᵃ mod p es rápido, con aproximadamente tantas multiplicaciones como cifras binarias tiene a. Deshacerlo no lo es.

El intercambio paso a paso

Alice y Bob acuerdan abiertamente p y g. Alice elige un secreto a y envía A = gᵃ mod p; Bob elige un secreto b y envía B = gᵇ mod p. Alice calcula Bᵃ = (gᵇ)ᵃ y Bob calcula Aᵇ = (gᵃ)ᵇ, ambos mod p. Como el orden de los exponentes no importa, ambos obtienen g^(ab) mod p. Con el pequeño ejemplo clásico p = 23, g = 5, a = 6 y b = 15, Alice envía 8, Bob envía 19, y ambos llegan al secreto compartido 2.

El problema del logaritmo discreto

Eve ve p, g, A y B. Si pudiera hallar a a partir de A = gᵃ mod p, podría calcular el secreto igual que Alice. Este es el problema del logaritmo discreto. Los mejores algoritmos clásicos conocidos, como la criba del cuerpo de números, son mucho más rápidos que probar todos los exponentes, pero aun así necesitan un tiempo que crece más deprisa que cualquier potencia del número de cifras. Con primos de 2048 bits, el problema está fuera del alcance de cualquier ordenador que exista. No se sabe si es posible algo más rápido, y la seguridad del intercambio descansa en esa creencia.

Ataque de intermediario

Diffie-Hellman protege contra quien escucha, pero no contra un impostor. Mallory, situado entre Alice y Bob, puede realizar un intercambio con cada uno de ellos y pasar los mensajes, leyéndolo todo. La defensa es la autenticación: en HTTPS el servidor firma su parte del intercambio con una clave certificada por una autoridad de confianza, de modo que el navegador sabe que realmente está hablando con el sitio correcto. El intercambio de claves y las firmas siempre van juntos.

¿Quién lo inventó?

Diffie y Hellman lo publicaron en 1976, basándose en ideas de Ralph Merkle; más tarde, Hellman pidió que también a él se le reconociera el mérito. En 1997, la agencia de inteligencia británica GCHQ reveló que sus matemáticos habían llegado antes: James Ellis tuvo la idea de la criptografía de clave pública en 1970, Clifford Cocks encontró un sistema similar a RSA en 1973 y Malcolm Williamson descubrió el mismo intercambio de claves en 1974, todo ello mantenido en secreto durante más de veinte años.

Martin Hellman (izquierda) y Whitfield Diffie (derecha), 1977
Martin Hellman (izquierda) y Whitfield Diffie (derecha), 1977
Ralph Merkle en la Singularity Summit de 2007.
Ralph Merkle en la Singularity Summit de 2007.

Diffie-Hellman hoy

Las conexiones modernas usan sobre todo Diffie-Hellman de curva elíptica, que ofrece la misma seguridad con números mucho más cortos, por ejemplo la curva X25519 en TLS 1.3, Signal y WhatsApp. Usar un par nuevo de secretos en cada conexión proporciona secreto hacia adelante: aunque más adelante roben la clave a largo plazo de un servidor, las conversaciones pasadas siguen a salvo. Los parámetros débiles siguen siendo un peligro, como demostró en 2015 el ataque Logjam con antiguos primos de 512 bits, y un gran ordenador cuántico que ejecutara el algoritmo de Shor rompería tanto el Diffie-Hellman clásico como el de curva elíptica, por lo que ya se están desplegando intercambios de claves poscuánticos junto a ellos.

Explóralo

Abre el visualizador Diffie-Hellman para seguir los cinco pasos en un tablero con lo que saben Alice, el canal público y Bob, como pintura y como números. Elige primos desde 23 hasta 2.147.483.647, fija tú mismo los secretos y deja que Eve ataque probando todos los exponentes: mira cómo acierta al instante con primos pequeños y cómo crece el tiempo de búsqueda estimado a medida que el primo se alarga.

Preguntas frecuentes

¿Es Diffie-Hellman lo mismo que RSA?

No, aunque ambos son métodos de clave pública de los años setenta. RSA, publicado en 1977, puede cifrar y firmar con una clave pública y una privada, y se basa en la dificultad de factorizar números grandes. Diffie-Hellman solo acuerda un secreto compartido y se basa en el problema del logaritmo discreto.

¿Qué tamaño tienen los números en la práctica?

El Diffie-Hellman clásico usa primos de al menos 2048 bits, unas 617 cifras decimales, y a menudo de 3072 o 4096 bits. Las versiones de curva elíptica usan claves de unos 256 bits para una seguridad comparable.

¿Por qué cada bit adicional duplica el trabajo de Eve?

Un primo con un bit más es aproximadamente el doble de grande, así que hay aproximadamente el doble de exponentes que probar. Los ataques reales son más ingeniosos que probar todos los exponentes, pero su coste sigue creciendo muy rápido con el tamaño del primo.

¿Por qué Alice y Bob necesitan un primo?

Con un módulo primo, todo número de 1 a p − 1 tiene inverso y existen raíces primitivas, de modo que las potencias de g cubren todas las posibilidades. A menudo se eligen primos seguros, en los que (p − 1)/2 también es primo, para descartar atajos que aprovechan factores pequeños de p − 1.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Abrir el visualizador Diffie-Hellman