Diffie-Hellman

Explicación del intercambio de claves Diffie-Hellman y del concepto de grupos de Diffie-Hellman. Conviene tener un conocimiento básico de teoría de grupos y estructuras algebráicas.

Fuentes

• SPK Tech Fit

• EITCA

Intercambio de claves de Diffie-Hellman

Partimos de la base de que $Z_p$ es el cuerpo de los enteros módulo $p$, con $p$ primo.

El algoritmo DH clásico opera sobre el conjunto {${1,2,...,p-1}$} y usa la operación de multiplicación mod $p$.

Dos personas, Alice y Bob, quieren acordar un número secreto mientras todos los demás les escuchan. Para ello:

• Eligen dos números (que el resto sabe):

  • $p$: Un número primo muy grande que forma $Z_p$.

  • $g$: Una raíz primitiva mod $p$.

• Eligen claves privadas:

  • Alice elige un entero secreto $a$.

  • Bob elige un entero secreto $b$.

• Intercambian públicamente:

  • Alice calcula $A$: $A = g^a\ (mod\ p)$ y lo comparte públicamente.

  • Bob calcula $B$: $B = g^b\ (mod\ p)$ y lo comparte públicamente.

• Calculan el valor secreto:

  • Alice toma el valor $B$ de Bob y lo eleva a su valor secreto $a$: $S = B^a\ (mod\ p)$

  • Bob toma el valor $A$ de Alice y lo eleva a su valor secreto $b$: $S = A^b\ (mod\ p)$

Dado que la multiplicación es conmutativa:

• Resultado de Alice: $S = B^a = (g^b)^a = g^{ab}$

• Resultado de Bob: $S = A^b = (g^a)^b = g^{ab}$

Un oyente externo conoce $p,g,A$ y $B$, sólo necesita conocer $a$ o $b$ para conseguir la clave $S$. Para números normales (en el campo, de, p.ej, $\mathbb{R}$), un oyente podría calcular lo siguiente:

$B = g^b$ Si $B$ y $g$ son conocidos, y se busca $b$:

$b = \log_g$

Esto es sencillo de calcular si estamos en $\mathbb{R}$, pero para conjuntos como $Z_p$ se hace mucho más difícil.

En números reales, si buscas $g$, pruebas con un valor, y da un resultado bajo, sabes que debes probar con uno mayor. En $Z_p$ no pasa nada parecido, por ejemplo:

• $3^1 \equiv 3\ (mod\ 17)$

• $3^2 \equiv 9\ (mod\ 17)$

• $3^3 \equiv 10\ (mod\ 17)$

• $3^4 \equiv 13\ (mod\ 17)$

• $3^5 \equiv 5\ (mod\ 17)$

• ...

No se sigue un patrón, no hay nada que indique si el resultado está más arriba (mayor $a$ o $b$) o más abajo.

Grupos de Diffie-Hellman

Los grupos de Diffie-Hellman que se pueden ver, por ejemplo, en configuraciones y transformaciones IKE, son simplemente valores estandarizados de $p$ y $g$.

Cada vez que se crea una SA no es práctico generar un nuevo número primo grande $p$, así que para ello hay varios precalculados, con diferentes niveles de complejidad.

P.ej:

• Grupo 2: $p$ tiene 1024 bit. Ahora mismo obsoleto y débil contra tablas pre-calculadas.

• Grupo 14: Estándar. $p$ tiene 2048 bit. Mucho más seguro.

• Grupos 19 y superiores (ECDH): Usan algoritmos de curva elíptica (similar al DH, usando puntos de una curva en el espacio), son igual de seguros que el DH pero más eficientes. (Una clave de 256bit de ECDH es igual de segura que una de 2048 de DH).