Criptografía (CCLXXX): Intercambio de clave de Diffie-Hellman

Entre las entradas que pongo en este blog para contar de la forma más comprensible de la que sea capaz lo que voy aprendiendo sobre criptología, le toca el turno al protocolo criptográfico para el intercambio de clave propuesto por Whitfield Diffie y Martin Hellman en 1976.

El intercambio de clave de Diffie-Hellman es un protocolo que se utiliza para el intercambio seguro de una clave entre dos interlocutores a través de un canal inseguro, como puede ser Internet.

Sean A (Alicia) y B (Bernardo) los dos interlocutores que desean intercambiar una clave de sesión, un número que se utiliza como clave para cifrar y descifrar utilizando un criptosistema de clave simétrica o secreta y que ambos interlocutores deben conocer (compartir), sin poner en peligro el secreto de ésta si las comunicaciones entre ambos son interceptadas por un tercero.

A y B actuarían de la siguiente manera:

1.- Se ponen de acuerdo para escoger un número primo 'p' y un generador 'g' o raíz primitiva módulo 'p'. Ambos números son públicos, es decir, pueden ser conocidos por cualquiera, incluso por un atacante que intercepte las comunicaciones en las que A y B los escogen.

¿Qué es un generador ‘g’ o raíz primitiva módulo ‘p’? Pues esto no es tan importante, ya que como diré más adelante el protocolo funciona aunque el segundo número escogido no lo sea, pero lo explico (espero haberlo entendido bien y no equivocarme mucho): es un resto de ‘p’ cuyas operaciones g¹ mod p, g² mod p,…, g^p-1 mod p dan como resultado todos los restos de ‘p’ desde 1 a p - 1.

Así, por ejemplo, si p = 7, entonces 3 es un generador o raíz primitiva módulo 7, ya que:

3¹ mod 7 = 3; 3² mod 7 = 2; 3³ mod 7 = 6; 3⁴ mod 7 = 4; 3⁵ mod 7 = 5; 3⁶ mod 7 = 1

Pero 2 no lo es:

2¹ mod 7 = 2; 2² mod 7 = 4; 2³ mod 7 = 1; 2⁴ mod 7 = 2; 2⁵ mod 7 = 4; 2⁶ mod 7 = 1

¿Cómo puedo saber si un número concreto, ‘g’, es un generador o raíz primitiva módulo ‘p’? Pues lo es si el orden de ‘g’ respecto al módulo ‘p’ (el exponente positivo ‘o’ más pequeño tal que g^o ≡ 1 (mod p)) es ϕ(p).

En nuestro caso, como ‘p’ es primo, entonces ϕ(p) = p - 1, por lo que en el ejemplo anterior ϕ(7) = 7 - 1 = 6 y, por tanto, sólo los restos de 7 cuyo orden (‘o’) sea 6 son un generador o raíz primitiva módulo 7. El orden de los restos de 7 es el siguiente:

1¹ ≡ 1 (mod 7); o(1) = 1 ≠ ϕ(7). 1 no es un generador o raíz primitiva de 7.

2³ ≡ 1 (mod 7); o(2) = 3 ≠ ϕ(7). 2 no es un generador o raíz primitiva de 7.

3⁶ ≡ 1 (mod 7); o(3) = 6 = ϕ(7). 3 es un generador o raíz primitiva de 7.

4³ ≡ 1 (mod 7); o(4) = 3 ≠ ϕ(7). 4 no es un generador o raíz primitiva de 7.

5⁶ ≡ 1 (mod 7); o(5) = 6 = ϕ(7). 5 es un generador o raíz primitiva de 7.

6² ≡ 1 (mod 7); o(6) = 2 ≠ ϕ(7). 6 no es un generador o raíz primitiva de 7.

Por lo que sólo 3 y 5 son generadores o raíces primitivas módulo 7.

Si se escoge un segundo número que no sea un generador o raíz primitiva de 'p' el protocolo también funciona y, debido a que encontrar raíces primitivas de un número primo 'p' muy grande puede ser muy costos en tiempo de cómputo y recursos, en la práctica se puede utilizar un número pequeño (por ejemplo 2 o 5) que en realidad no lo sea, ya que para un número primo 'p' muy grande el sistema no será inseguro por esto.

2.- A escoge un número entero aleatorio 'a' mayor que 0 y menor que 'p', que será secreto (sólo ella debe conocerlo), y envía a B el resultado de la operación g^a mod p.

3.- De forma análoga, B escoge un número entero aleatorio 'b' mayor que 0 y menor que 'p', que será secreto (sólo él debe conocerlo), y envía a A el resultado de la operación g^b mod p.

4.- En este momento, tanto A como B están ya en disposición de calcular la clave de sesión ('k') compartida sin intercambiarla por ningún sitio. Es decir, A puede calcular el secreto compartido (la clave de sesión) a partir del número que le ha mandado B en el paso anterior (g^b mod p) y el número secreto que ella ha escogido en el paso 2 ('a'), es decir, sin más que realizar la siguiente operación: k = (g^b mod p)^a mod p; mientras que B puede calcularlo a partir del número que le ha mandado A en el paso 2 (g^a mod p) y el número secreto que él ha escogido en el paso 3 ('b'), es decir, sin más que realizar la siguiente operación: k = (g^a mod p)^b mod p.

Veamos un ejemplo con un número primo 'p' pequeño, pero para que este protocolo sea seguro es necesario utilizar un número mucho más grande, por ejemplo de 2.048 bits:

1.- A y B acuerdan utilizar 997 como número primo 'p' y 3 como generador ('g') de 'p'.

2.- A escoge 8 como número secreto y envía a B el resultado de 3⁸ mod 997 = 579.

3.- B escoge 14 como número secreto y envía a A el resultado de 3¹⁴ mod 997 = 360.

4.- El secreto compartido es:

4.1.- A calcula: k = (360)⁸ mod 997 = 30.

4.2.- B calcula: k = (579)¹⁴ mod 997 = 30.

La fortaleza de este protocolo reside en que para obtener el secreto compartido entre A y B (la clave de sesión 'k') el atacante, conociendo los números públicos intercambiados entre A y B, se enfrenta al problema del logaritmo discreto (PLD), es decir, las operaciones que realizan A y B son muy rápidas y consumen muy pocos recursos, pero aunque el atacante conozca los números públicos el cálculo de 'k' se vuelve inabordable cuando 'p' es un número primo muy grande por los elevadísimos tiempo de cómputo y potencia de cálculo que se requieren.

Sin embargo, si este protocolo se realiza de forma no autenticada puede ser vulnerable a un ataque de intermediario (MitM, por las siglas en inglés de 'Man in the Middle') ya que un atacante podría interponerse en las comunicaciones entre A y B, suplantando a uno frente al otro y haciendo que ninguno de los dos se dé cuenta de que están siendo hackeados.

Quizás también te interese: