Criptografía (CCXCIV): Intercambio de clave de Diffie-Hellman en curvas elípticas (ECDH)

Ya expliqué en este post en qué consiste el protocolo de intercambio de clave de Diffie-Hellman y cómo se lleva a efecto entre dos usuarios. Además, también decía que este protocolo criptográfico se utiliza generalmente para el intercambio seguro de una clave, que será empleada en una sesión para el cifrado y descifrado utilizando un criptosistema de clave simétrica o secreta, entre dos interlocutores a través de un canal inseguro, como puede ser Internet, y, por tanto, su objetivo es salvaguardar el secreto de la clave de sesión si las comunicaciones entre ambos son interceptadas por un tercero.

Pues bien, en esta entrada voy a explicar cómo se lleva a cabo el protocolo de Diffie-Hellmann en Curvas Elípticas ('Elliptic curve Diffie–Hellman' o 'ECDH' por sus siglas en inglés).

Sean A (Alicia) y B (Bernardo) los dos interlocutores que desean intercambiar una clave de sesión.

A y B actuarían de la siguiente manera:

1.- Se ponen de acuerdo para escoger un cuerpo finito ℤ𝑝, una curva elíptica 𝔼 definida sobre él y un punto ‘P’ de la misma.

Sin entrar en mayores disquisiciones matemáticas, decir que el punto 'P' seleccionado desempeña el papel de elemento generador ('g') del grupo cíclico de puntos de la curva que van a formar el grupo delimitado con sus operaciones.

Cualquier punto de la curva es un generador de un grupo cíclico, pero para lograr mayor seguridad conviene que éste incluya a todos los puntos de la curva.

¿Cómo nos aseguramos de elegir un punto 'P' que sea un elemento generador del resto de puntos de la curva?, es decir, que si lo vamos multiplicando por los sucesivos valores desde 1 a p + 1 vayamos obteniendo todos los puntos de la curva, punto en el infinito (𝒪) incluido. Pues, si no lo he entendido mal, basta con decir que en el caso de que la curva tenga un número de puntos (orden o valor cardinal de la curva) que sea un número primo nos aseguramos de que todos los puntos de la misma tienen el mismo orden (escalar entero positivo más pequeño que multiplicado por el punto da como resultado el punto en el infinito), que coincide con el orden de la curva, y, por tanto, nos aseguramos de que cualquiera de ellos puede utilizarse como elemento generador del resto de puntos de la curva, razón por la cual en criptografía se suelen utilizar curvas cuyo orden, es decir, cuyo número de puntos (punto en el infinito, 𝒪, incluido) sea un número primo.

Estos datos 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 eligen.

2.- A escoge un número entero aleatorio 'a' de orden de magnitud 'p', que será secreto (sólo ella debe conocerlo), y envía a B el resultado de la operación a * P.

3.- De forma análoga, B escoge un número entero aleatorio 'b' de orden de magnitud 'p', que será secreto (sólo él debe conocerlo), y envía a A el resultado de la operación b * 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 (b * 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 = (b * P) * a; mientras que B puede calcularlo a partir del número que le ha mandado A en el paso 2 (a * 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 = (a * P) * b.

Veamos un ejemplo:

1.- A y B acuerdan utilizar la curva elíptica 𝔼: y² = x³ - 1 x + 1 definida sobre ℤ13, y como punto ‘P’ = (6, 4).

Con el script en Python que puse en este post, vemos que el número de puntos de esta curva es 19 (18 más el punto en el infinito):

2.- A escoge 11 como número secreto y envía a B el resultado de a * P. Con el script en Python que puse en esta entrada, vemos que 11 * (6, 4) = (1, 12).

3.- B escoge 8 como número secreto y envía a A el resultado de b * P. Con el script en Python que puse en esta entrada, vemos que 8 * (6, 4) = (1, 1).