Diffie-Hellman: un secreto acordado en público

Alice envía gᵃ mod p, Bob envía gᵇ mod p y ambos llegan a gᵃᵇ mod p sin que ninguno lo haya transmitido. Eva observa cada número que cruza la línea. Recorre el intercambio paso a paso y luego sigue su ataque; cambia después p y g para descubrir qué le facilita tanto el trabajo.

Ejemplo resuelto — Diffie-Hellman: un secreto acordado en público

Número público de Alice	8
Número público de Bob	19
El secreto compartido	2
Valores posibles del secreto	22 de 22
Fuerza bruta para este A	7 (22 en el peor caso)
Pohlig-Hellman para este A	8 (13 en el peor caso)
Secreto de Eva a partir de x	2

Estos son los valores que muestra la calculadora al abrir la página. Cambia cualquier entrada de arriba para recalcularlos.

Cargando simulación interactiva...

Lección

La teoría — Diffie-Hellman: un secreto acordado en público

En un intercambio de claves de Diffie-Hellman, dos partes acuerdan un número secreto a través de un canal que cualquiera puede leer. Fijan en público un primo p y una base g. Cada parte elige un exponente privado, hace público el resultado de elevar g a esa potencia mod p y luego eleva el número público de la otra a su propio exponente: (gᵇ)ᵃ = (gᵃ)ᵇ = gᵃᵇ mod p. Revertir el proceso exige resolver un logaritmo discreto: dado A = gᵃ mod p, hallar un x tal que gˣ ≡ A (mod p). Diffie y Hellman señalaron en 1976 que no veían modo de deducir el secreto compartido a partir de los números públicos sin resolverlo, aunque tampoco tenían una demostración de que fuera imposible. El orden de g es el menor n ≥ 1 con gⁿ ≡ 1 (mod p); g es un generador cuando su orden es p − 1.

Qué significa cada símbolo

p: el módulo primo, público
g: la base, pública
a, b: los exponentes privados de Alice y Bob
A, B: sus números públicos, gᵃ mod p y gᵇ mod p
x: el exponente que halla Eva; cualquier x con gˣ ≡ A sirve, de modo que halla a módulo el orden de g
ord(g): el orden de g: cuántos valores distintos puede tomar el secreto compartido

Supone: p es un primo entre 5 y 1.999, g una base entre 2 y p − 2, y a y b van de 1 a p − 2. Un intento es una comparación entre una potencia calculada y un objetivo; ambos recuentos incluyen el intento que tiene éxito. Cada cifra de Pohlig-Hellman se obtiene probando sus candidatos por orden, tal como lo describieron Pohlig y Hellman para factores pequeños; para factores grandes propusieron además una búsqueda que intercambia memoria por tiempo, algoritmo que esta página no ejecuta. El ejemplo original de Diffie y Hellman empleaba un primo de unos 200 bits, para el que estimaron el cálculo del logaritmo en torno a 2¹⁰⁰ operaciones.

Con 257, la base 2 solo deja dieciséis secretos posibles 🖖

Pulsa Un bucle de 16. Al ser 257 un número primo, da la impresión de que A y B podrían ser cualquiera de los 256 restos no nulos. Pero 2⁸ = 256, que equivale a −1 mod 257. Por tanto, 2¹⁶ = 1 y las potencias de 2 quedan atrapadas en un ciclo de 16 valores: 1, 2, 4, 8, 16, 32, 64, 128, 256, 255, 253, 249, 241, 225, 193, 129. Esas son las casillas sombreadas. Sean cuales sean a y b, gᵃᵇ será uno de ellos, y en este caso es 129. La fuerza bruta de Eva se detiene tras 14 intentos y nunca requerirá más de 16. El x obtenido, 13, no es el 77 de Alice: basta con que coincida con él módulo 16, que es todo lo que el exponente puede determinar. Un módulo primo no basta para protegerte de esto. De las 254 bases posibles entre 2 y 255, 126 no son generadores; dos de ellas, 16 y 241, dejan solo cuatro secretos posibles. En 263, donde p − 1 = 2 × 131, el orden de cada base de 2 a 261 es 131 o 262.

Primos gemelos: 811 intentos frente a 21 🖖

Pulsa p − 1 en piezas pequeñas. 1621 es primo y 1620 = 2² · 3⁴ · 5, así que Pohlig-Hellman nunca explora las 1.620 potencias de g. Halla a mod 4 probando candidatos de dos en dos, a mod 81 de tres en tres y a mod 5 entre cinco opciones; luego reúne las piezas mediante el teorema chino del resto: como mucho 2·2 + 4·3 + 5 = 21 intentos, y 15 en este caso, donde la fuerza bruta necesita 1.235. Elige ahora el 1619 en la tabla de primos cercanos a p. Es apenas dos unidades menor, pero 1618 = 2 × 809: hay una sola pieza de 809 candidatos, 811 intentos en el peor caso y 427 para el mismo valor de a. El esfuerzo de Eva no lo marca p, sino el mayor factor primo de p − 1. Entre los 301 primos que admite esta página, el peor caso de Pohlig-Hellman nunca supera a ese factor en más de 25; en 172 de ellos supone menos de la décima parte que la fuerza bruta, y en 146 de los 300 saltos entre primos consecutivos, el coste disminuye. Pohlig y Hellman lo dijeron sin rodeos en 1978: si p − 1 solo tiene factores primos pequeños, la exponenciación mod p «no es una buena función unidireccional».

La base más segura no es un generador 🖖

Pulsa Base de orden primo. En 263, la base 2 no es un generador: sus potencias se repiten a los 131 pasos y solo permite 131 secretos. Escribe ahora g = 5, que sí es generador, y los posibles secretos se duplican. Fíjate en el peor caso de Pohlig-Hellman para esa base: 133 intentos, 2 de ellos dedicados a la última cifra binaria de a, porque A¹³¹ vale 1 cuando a es par y 262 (que equivale a −1) cuando a es impar. Un generador revela ese dígito en cualquier primo impar, puesto que p − 1 es par. Vuelve a g = 2. Su orden, 131, es primo: Pohlig-Hellman no tiene nada que descomponer y su peor caso exige 131 intentos, exactamente los mismos que la fuerza bruta. El generador duplicaba los secretos posibles, pero le regalaba a Eva un bit sin esfuerzo alguno: solo con A y B, ella puede deducir si el secreto es un cuadrado mod 263. En cambio, como toda potencia de 2 es un cuadrado, con g = 2 no tiene por dónde empezar.

Problema resuelto al detalle

Recuperar el secreto de Alice con p = 101 5 pasos
Alice y Bob eligen p = 101 y g = 2. Eva intercepta A = 12 y B = 53. Encuentra un x con 2ˣ ≡ 12 (mod 101) mediante Pohlig-Hellman, cuenta los intentos y usa x para deducir el secreto compartido. Indica después cuánto costaría el mismo ataque con p = 65.537.

Abre este problema en la herramienta
1. Como 100 = 2² · 5², x queda determinado por x mod 4 y x mod 25. El orden de 2 divide a 100, y tanto 2⁵⁰ = 100 como 2²⁰ = 95 son distintos de 1, así que el orden es 100: el 2 es un generador.
  
  $100 = 2^{2} \cdot 5^{2}, 2^{50} \equiv 100, 2^{20} \equiv 95 (both \neq = 1) \Rightarrow ord (2) = 100$
2. Módulo 4, γ = 2⁵⁰ = 100, que equivale a −1. Primera cifra binaria: 12⁵⁰ = 100, luego d = 1 al segundo intento. Lo descontamos: 12 · 2⁻¹ = 12 · 51 = 612 ≡ 6, y 6²⁵ = 100, de modo que la siguiente cifra también es 1, de nuevo al segundo intento. Así, x ≡ 1 + 1 · 2 = 3 (mod 4).
  
  $1 2^{50} \equiv 100 \Rightarrow d_{0} = 1; 12 \cdot 2^{- 1} = 12 \cdot 51 \equiv 6, 6^{25} \equiv 100 \Rightarrow d_{1} = 1; x \equiv 3 (mod 4)$
3. Módulo 25, γ = 2²⁰ = 95, cuyas potencias son 1, 95, 36, 87, 84. Primera cifra en base 5: 12²⁰ = 95, luego d = 1 al segundo intento. Lo descontamos: 6⁴ = 1.296 ≡ 84, con lo que la siguiente cifra es 4 al quinto intento. Así, x ≡ 1 + 4 · 5 = 21 (mod 25).
  
  $9 5^{0..4} = 1, 95, 36, 87, 84; 1 2^{20} \equiv 95 \Rightarrow d_{0} = 1; 6^{4} = 1296 \equiv 84 \Rightarrow d_{1} = 4; x \equiv 21 (mod 25)$
4. Los números menores que 100 congruentes con 21 mod 25 son 21, 46, 71 y 96; de ellos, solo el 71 es 3 mod 4. Por tanto, x = 71 tras 2 + 2 + 2 + 5 = 11 intentos, cuando el peor caso requería 2·2 + 2·5 = 14. La fuerza bruta habría probado del 0 al 71, es decir, 72 intentos. El secreto compartido es 53⁷¹ mod 101 = 35.
  
  $x \in {21, 46, 71, 96}, x \equiv 3 (mod 4) \Rightarrow x = 71; 2 + 2 + 2 + 5 = 11 tries, at worst 2 \cdot 2 + 2 \cdot 5 = 14$
5. 65.537 = 2¹⁶ + 1 es primo y p − 1 = 2¹⁶. Pohlig-Hellman resuelve sus dieciséis cifras binarias una a una, con dos candidatos para cada una: a lo sumo 32 intentos, frente a los 65.536 que podría requerir la fuerza bruta. Pohlig y Hellman analizaron este caso concreto, p = 2ⁿ + 1, antes de abordar el caso general.
  
  $s = B^{x} = 5 3^{71} mod 101 = 35; 65537 = 2^{16} + 1 : at worst 16 \cdot 2 = 32 tries$
Respuesta

x = 71, tras 11 intentos (como máximo 14), y el secreto compartido es 35. Con p = 65.537, el ataque requiere a lo sumo 32 intentos. La página se detiene en 1.999, de modo que esa cifra surge del cálculo teórico y no de una simulación.

$x = 71, 11 tries, s = 35$

Ruta de aprendizaje

Cómo se rompen los códigos

Referencias (2)

The exchange itself, the definition's sentence that its authors could see no way round a logarithm and had no proof, and the 200-bit example in `assumes`: Whitfield Diffie and Martin E. Hellman, "New Directions in Cryptography," IEEE Transactions on Information Theory 22(6), 644–654, November 1976. §III, p. 649.
The second insight's quotation, the digit-by-digit search the page runs, and the worked problem's p = 2ⁿ + 1: Stephen C. Pohlig and Martin E. Hellman, "An Improved Algorithm for Computing Logarithms over GF(p) and Its Cryptographic Significance," IEEE Transactions on Information Theory 24(1), 106–110, January 1978. §III–IV, pp. 107–110.

Por el equipo de 42Math · Contrastado con fuentes publicadas. Se agradecen correcciones.