El problema de Diffie-Hellman

Se puede escribir mucho sobre el protocolo de cifrado de Diffie-Hellman, incluyendo interesantes historias sobre cómo realmente no fue el primer protocolo de cifrado asimétrico, al contrario de lo que muchos piensan. Esta entrada va a ser un poco densa para los que no estén medianamente puestos en el tema, y no va sobre criptografía. Espero poder hablar del protocolo de cifrado de Diffie-Hellman al completo más adelante, pero esta vez me gustaría centrarme en un pequeño detalle que he visto en la versión inglesa de la Wikipedia sobre la descripción del problema propuesto por Diffie-Hellman, cuya versión en español no existe, por cierto. Si vais a la descripción del problema, podréis leer lo siguiente:

Given an element g and the values of gx and gy, what is the value of gxy?

Formally, g is a generator of some group (typically the multiplicative group of a finite field or an elliptic curve group) and x and y are randomly chosen integers.

Lo que viene a ser en la lengua de Cervantes algo así como:

Dado un elemento g y los valores de gx y gy, ¿cuál es el valor de gxy?

Formalmente, g es un generador de algún grupo (típicamente el grupo multiplicativo de un cuerpo finito o un grupo correspondiente a una curva elíptica) y x e y son números enteros elegidos al azar.

palangifiles.com Creative Commons.

No sé a vosotros, pero ese segundo párrafo me parece la típica afirmación que se prueba por intimidación. Voy a intentar arrojar algo de luz sobre el asunto así que, ya que los cobardes se habrán marchado hace unas cuantas líneas, puedo decir que esta entrada es sobre teoría de grupos y álgebra abstracta. Corred insensatos.

Lo primero y más básico, un grupo no es nada más que un conjunto de números ligados a una operación. Por ejemplo, los números pares y la suma forman un grupo. Cada grupo tiene ciertas características; todos los grupos son cerrados, pero un grupo puede ser finito o infinito, cíclico o no cíclico, conmutativo o no… Por ahora solo voy a centrarme en esas tres primeras características.

Volviendo al ejemplo de los números pares, son claramente un grupo cerrado, porque no importa con qué números del grupo hagamos la operación (recordemos que nuestro grupo está formado por los números pares y la suma, todo grupo tiene una operación definida), el resultado siempre va a formar parte del grupo. En términos más simples, siempre que sumes dos números pares el resultado va a ser otro número par. Resulta que también es un grupo infinito, porque hay un número infinito de elementos que pertenecen al grupo. Cuando creas que tienes una lista con todos los números pares, añade 2 al ultimo y ya tienes otro numero par... ad infinitum. Hasta ahora nada complicado, pero el concepto de grupo cíclico tal vez sea algo más complejo para los que no hayan visto antes álgebra abstracta.

Retículo de particiones del conjunto {1,2,3,4}. Wikimedia Commons

En un partido de fútbol, un equipo podría marcar cualquier número de goles, porque los goles se marcan de uno en uno. En álgebra estaríamos hablando del conjunto de números naturales asociados a la suma. Si eliges un número positivo, no importa cuál, en teoría ése podría ser el número de goles marcados por un equipo. En baloncesto, suponiendo que no existieran ni tiros libres ni triples, cada canasta vale dos puntos. En ese caso, ningún equipo bajo ninguna circunstancia podría tener un resultado impar porque, como decíamos antes, siempre que sumes dos números pares (en este caso 2 es siempre uno de esos números), el resultado será otro número par. En el ejemplo del fútbol, cualquier número natural puede ser generado si sumamos 1+1+1… Suficientes veces, por eso, ese determinado grupo es un grupo cíclico y tiene el numero 1 como generador. En el segundo ejemplo, dado un número impar, no podría generar ese número no importa cuántas veces realice la operación 2+2+2+2… Por lo tanto, 2 no es un generador para el conjunto de números naturales bajo la suma. Sin embargo, si consideramos el conjunto de números pares, ¡2 sí es un generador! Dame cualquier número par, que si sumo 2+2+2+2… suficientes veces, llegaré a ese resultado. Como tiene un generador, ese grupo es un grupo cíclico.Entonces pues, ambos grupos son cíclicos. El primero tiene 1 como generador y el segundo tiene el número 2 como generador.

Las raíces complejas bajo multiplicación son un ejemplo de grupo cíclico. Wikimedia Commons

¿Y a qué viene todo este rollo sobre teoría de grupos para entender el protocolo de cifrado de Diffie-Hellman? Pues volvamos a la primera línea de nuestra definición del problema:

Dado un elemento g y los valores de gx y gy, ¿cual es el valor de gxy?

Ahora en vez de la suma nuestra operación es la multiplicación. Observemos dos posibles casos: g puede ser un generador o no. Si g no es un generador, no importa cuántas veces realice la operación g × g × g × g… va a haber algún numero perteneciente al mismo grupo que nunca podría ser parte del resultado. Si suficientes números son excluidos del resultado, ¡estaremos comprometiendo la seguridad de nuestra clave! Imagina que g fuese 2. En ese caso, mi clave privada y la clave compartida sólo podrán ser una potencia de 2. Con un poquito más de información, como la longitud de la clave, intentar adivinarla sería un juego de niños. Y por eso es importante que g sea un generador para su grupo, o que al menos su clase residual (el conjunto de elementos que g podría generar) sea suficientemente grande. Así, cuando tenemos un numero en común, g, y tú realizas la operación g × g × g × g… y veces, o sea,  gy , y me mandas el resultado; y yo hago la operación gy × gy × gy × gy… x veces, lo que viene a ser simplemente gxy, un atacante tendrá muchas claves que probar hasta que dé con el mismo resultado que yo obtuve con esa operación. Con un poco de suerte, serán demasiadas claves para que acierte a tiempo, entonces mi clave será segura.