Criptomanía | Introducción formal a la Criptografía de Curva Elíptica. Ejemplos de algoritmos: ECDSA y ECDH. Firma y verificación de firmas. 

Este artículo es la tercera entrega de la serie de artículos Criptografía de Curva Elíptica: una introducción formal.

Esta serie de artículos sobre criptografía de curva elíptica va a estar compuesta por los siguiente artículos:

  1. Curvas elípticas: ¿qué son y que propiedades tienen?
  2. Curvas elípticas: cuerpos finitos y logaritmo discreto 
  3. ECDH y ECDSA: ejemplos de algoritmos de criptografía de curva elíptica (el artículo actual)
  4. Algoritmos para desencriptar criptosistemas ECC en comparación con criptosistemas RSA

En el primer artículo, vimos como las curvas elípticas cumplen las propiedades de un “grupo”. Específicamente hemos definido una regla para la suma de puntos de una curva: dados tres puntos alineados, su suma es cero (P+Q+R=0). Y a partir de esa regla hemos determinado un método geométrico y un método algebraico para calcular sumas de puntos.

Después presentamos la multiplicación escalar (nP=P+P+\ldots+P) y finalmente encontramos un algortimo “fácil” para calcular las multiplicaciones escalares: double and add.

En el segundo artículo de la serie, hemos restringido las curvas elípticas a un campo finito de enteros de modulo primo. Al hacerlo, hemos descubierto que los puntos de una curva elíptica restringida a un campo finito forman subgrupos cíclicos. Sobre estos subgrupos cíclicos hemos definido los términos de punto base, orden y cofactor.

Por último, vimos que la multiplicación escalar en campos finitos es un problema “fácil”, mientras que el problema del logaritmo discreto parece ser “difícil”.

Ahora, por fin, vamos a ver como todos estos conceptos teóricos se aplican a la criptografía.

¿Preparados? ¡¡Vamos!!

Parámetros

Un algoritmo de curva elíptica funcionará en un subgrupo cíclico de una curva elíptica restringida a un campo finito. Luego, un algoritmo ECC necesita los siguientes parámetros:

  • Un número primo p, que determinará el tamaño del campo finito.
  • Los coeficientes (a,b) de la ecuación de la curva elíptica.
  • El punto base G que generará nuestro subgrupo.
  • El orden n del subgrupo.
  • El cofactor h del subgrupo.

En conclusión, los parámetros para definir nuestros algoritmos, son el sexteto (p,a,b,G,n,h).

Curvas aleatorias

Cuando he dicho que el problema del logaritmo discreto era “difícil” no estaba siendo del todo correcto. Hay algunas clases de curvas elípticas que son particularmente débiles y permiten el uso con éxito de algunos algoritmos para resolver el problema del logaritmo discreto de manera eficiente. Por ejemplo, todas las curvas que tienen p=hn (es decir, el orden del campo finito es igual al orden de la curva elíptica) son vulnerables a ataques Smart, que pueden resolver el problema del logaritmo discreto en tiempo polinómico en un ordenador clásico.

Ahora, imagina que te doy los parámetros del dominio de una curva. Existe la posibilidad de que yo haya descubierto una nueva clase de curvas vulnerables que solo yo conozca, y que haya construido un algoritmo “rápido” para resolver el problema del logaritmo discreto en la curva que te he facilitado. ¿Cómo puedo convencerte de lo contrario? Es decir, ¿cómo puedo convencerte de que no conozco ninguna vulnerabilidad de dicha curva en concreto? ¿Cómo puedo asegurarte que la curva es “segura” (que no conozco ninguna forma especial de atacarla)?

En un intento de resolver este problema, a veces tenemos un parámetro adicional para definir el dominio de la curva: la semilla S (the seed). Este es un número al azar usado para generar los coeficientes a y b, o el punto base G, o ambas cosas. Estos parámetros son generados calculando el hash de la semilla S. Cómo ya sabéis, los hashes son “fáciles” de generar, pero “difíciles” de deshacer.

ecdh-ecdsa-1

Un simple esquema de como una curva aleatoria es generada a partir de una semilla: el hash de un número al azar es usado para calcular diferentes parámetros de la curva.

ecdh-ecdsa-2

Si quisiéramos hacer trampas y tratar de recuperar la semilla a partir de los parámetros, tendríamos que resolver un problema “difícil”: invertir un hash

Una curva generada a partir de una semilla se dice que es de aleatoriedad verificable. El principio de usar hashes para generar parámetros es conocido como “nothing up my sleeve“, y es ampliamente usado en la criptografía.

Este método debería darnos cierta seguridad de que la curva que usamos no ha sido específicamente creada para ser vulnerable a alguna clase de ataque conocido por el “autor” de la curva. De hecho, si te doy una curva con una semilla, significa que yo no he elegido arbitrariamente los parámetros (lo has hecho tú al elegir tu semilla), y deberías poder estar relativamente seguro de que la curva no tiene ninguna vulnerabilidad específica que yo pueda aprovechar. El porqué de “relativamente” será explicado en el siguiente artículo, no dejes de leerlo.

Si estas interesado, puedes leer este documento de la SEC (Standards for Efficent Cryptography), donde podrás encontrar la explicación de un algoritmo para generar una curva de aleatoriedad verificable y/o para comprobar la aleatoriedad de la misma (página 21 del documento).

Andrea Corbellini ha creado un pequeño script Python que verifica que todas las curvas aleatorias que actualmente utiliza OpenSSL. Échale un vistazo.

Criptografía de Curva Elíptica

Ha sido largo, pero ¡por fin estamos aquí!

Es simple:

  1. La clave privada (private key) es un número entero d al azar elegido entre \{1,\ldots,n-1\} (donde n es el orden del subgrupo).
  2. La clave pública (public key) es el punto H=dG (dónde es el punto base del subgrupo).

¿Veis? Si conocemos d y G (junto con los demás parámetros), encontrar H es “fácil”. Pero si conocemos H y G, encontrar la clave privada d es “difícil”, porque requiere que resolvamos el problema del logaritmo discreto.

Ahora vamos a describir dos algoritmos de clave pública basados en esto: ECDH (Elliptic curve Diffie-Hellman), que se usa para cifrado, y ECDSA (Elliptic Curve Digital Signature Algorithm), utilizado para firmas digitales.

Cifrado con ECDH

ECDH es una variante del algoritmo Diffie-Hellman para curvas elípticas. De hecho, es un protocolo de establecimiento de claves, más que un algoritmo de encriptación. Esto básicamente significa que ECDH establece, hasta cierto punto, como se deberían generar e intercambiar las claves entre las partes implicadas. Cómo cifrar esos datos usando esas claves es cosa nuestra.

El problema que resuelve este algoritmo es el siguiente: dos partes (generalmente interpretadas por Alice  y Bob) quieren intercambiar información de forma segura, para que una tercera parte (el intermediario o “the Man In the Middle”) no pueda decodificar la información si intercepta el mensaje. Este es uno de los principios tras el protocolo TLS, por daros un ejemplo.

Este sería el proceso:

  1. Primero, Alice y Bob generan su propio par de claves (private and public keys). Tenemos la clave privada d_A y la clave pública H_A=d_AG de Alice, y las claves d_B y H_B=d_BG de Bob.
    Tanto Alice como Bob utilizan los mismos parámetros: el mismo punto base G en la misma curva elíptica restringida sobre el mismo campo finito.
  2. Alice y Bob intercambian sus claves públicas H_A y H_B a través de un canal inseguro. El intermediario podría interceptar una o ambas claves públicas, pero en ningún caso tendrá acceso a las claves privadas (d_A y d_B) sin resolver el problema del logaritmo discreto.
  3. Alice calcula S=d_AH_B (usando su propia clave privada y la clave privada de Bob), y Bob calcula S=d_BH_A (usado su propia clave privada y la clave pública de Alice). Ved que el resultado S es el mismo para ambos, de hecho:

S=d_AH_B=d_A(d_BG)=d_B(d_AG)=d_BH_A

El intermediario, sin embargo, solo conoce las claves públicas H_A y H_B (junto con el resto de los parámetros) y nunca podrá conocer la clave secreta compartida S. Esto es lo que se conoce como el problema de Diffie-Hellman, que se puede definir como:

Dados tres puntos P, aP y bP, ¿cuál es el resultado de abP?

O, de manera equivalente:

Dados tres enteros k, k^x y k^y, ¿cuál es el resultado de k^{xy}?

(La última forma se utiliza en la versión original del algoritmo Diffie-Hellman, basado en la aritmética modular)

ecdh-ecdsa-3

El protocolo de establecimiento de claves Diffie-Hellman: Alice y Bob pueden calcular “fácilmente” su clave secreta compartida, pero el “intermediario” tendría que resolver un problema “difícil”

El principio detrás del problema de Diffie-Hellman está explicado de manera genial por Khan Academy en este vídeo de YouTube, que luego explica el algoritmo de Diffie-Hellman aplicado a la aritmética modular (no a las curvas elípticas).

El problema de Diffie-Hellman para las curvas elípticas es considerado un problema “difícil”. Se cree tan “difícil” como el problema del logaritmo discreto, aunque no hay pruebas matemáticas de ello. De lo que podemos estar seguros es que no puede ser “más difícil”, porque resolver un logaritmo discreto es una forma de resolver el problema de Diffie-Hellman.

Ahora que Alice y Bob han conseguido su clave secreta compartida, pueden intercambiar información de manera segura con cualquier algoritmo de cifrado simétrico.

Por ejemplo, pueden utilizar la coordenada x de S como la clave para encriptar mensajes usando sistemas de cifrado seguro como AES o 3DES. Esto es más o menos lo que hace TLS, la diferencia es que TLS concatena la coordenada x con otros números relativos a la conexión y luego genera un hash de la cadena resultante.

Haciendo pruebas con ECDH

Andrea Corbellini ha creado un pequeño script Python para generar claves públicas, privadas y compartidas en una curva elíptica.

Aunque no seas programador (yo no lo soy) jugar con este código puede ayudarte a entender aún más este sistema. Copia el código de GitHub y pégalo en un compilador online. En las líneas 11, 13, 14, 16, 19 y 21 puedes encontrar y modificar los parámetros de la curva.

Este script hace uso de una curva estandarizada, secp256k1, propuesta por la SECG (Standards for Efficient Cryptography Group, fundado por Certicom). Esta misma curva es la que usa Bitcoin para firmas digitales.

Los parámetros utilizados (a menos que quieras cambiarlos) son:

  • p=0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f
  • a=0
  • b=7
  • x_G=0x79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
  • y_G=0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8
  • n=0xfffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141
  • h=1

(parámetros tomados del código fuente de OpenSSL)

Si haces algún cambio, recuerda que si no cumples las condiciones que vimos especialmente en el artículo anterior, el script no funcionará.

Este script es realmente simple e incluye algunos de los algoritmos que hemos mencionado en esta serie de artículos: suma de puntos, double and add, ECDH… Os recomiendo intentar leerlo y ejecutarlo. Producirá un output equivalente a este:

Curve: secp256k1
Alice's private key: 0xe32868331fa8ef0138de0de85478346aec5e3912b6029ae71691c384237a3eeb
Alice's public key: (0x86b1aa5120f079594348c67647679e7ac4c365b2c01330db782b0ba611c1d677, 0x5f4376a23eed633657a90f385ba21068ed7e29859a7fab09e953cc5b3e89beba)
Bob's private key: 0xcef147652aa90162e1fff9cf07f2605ea05529ca215a04350a98ecc24aa34342
Bob's public key: (0x4034127647bb7fdab7f1526c7d10be8b28174e2bba35b06ffd8a26fc2c20134a, 0x9e773199edc1ea792b150270ea3317689286c9fe239dd5b9c5cfd9e81b4b632)
Shared secret: (0x3e2ffbc3aa8a2836c1689e55cd169ba638b58a3a18803fcf7de153525b28c3cd, 0x43ca148c92af58ebdb525542488a4fe6397809200fe8c61b41a105449507083)

ECDH “Efímera”

Algunos de vosotros habréis oído hablar de ECDHE en vez de ECDH. La “E” en ECHDE se refiere a “Ephemeral” (efímero en español) e implica que las claves intercambiadas son temporales, en vez de estáticas.

ECDHE se usa, por ejemplo, en TLS, done ambos, cliente y servidor, generan sus pares de claves pública/privada cuando se establece la conexión.

Firmar con ECDSA

El escenario es el siguiente: Alice quiere firmar un mensaje con su clave privada (d_A), y Bob quiere validar la firma de Alice usando su clave pública (H_A). Nadie, a excepción de Alice, debería poder generar firmas válidas. Todo el mundo debería poder comprobar una firma.

Una vez más, Alice y Bob usan los mismos parámetros. El algoritmo que vamos a usar es ECDSA, una variante del algoritmo DSA aplicado a curvas elípticas.

ECDSA funciona con el hash del mensaje, en vez de con el mensaje en si mismo. La elección de la función para generar el hash depende de nosotros, pero obviamente debería ser una función criptográficamente segura. El hash del mensaje tiene que truncarse, para que la longitud en bits del hash sea la misma longitud en bits de n (el orden del subgrupo). El hash truncado es un entero y se denotará con la letra z.

El algoritmo ejecutado por Alice para firmar el mensaje es el siguiente:

  1. Escoge un número entero aleatorio k elegido entre \{1,\ldots,n-1\} (dónde n todavía es el orden del subgrupo).
  2. Calcula el punto P=kG (dónde G es el punto base del subgrupo).
  3. Calcula el número r=x_P\mathbf{mod}\ {n} (dónde x_P es la coordenada x de P).
  4. Si r=0 entonces elige otro valor para k y vuelve a intentarlo.
  5. Calcula s=k^{-1}(z+rd_A)\mathbf{mod}\ {n} (dónde d_A es la clave privada de Alice y k^{-1} es la inverso multiplicativo de k módulo n).
  6. Si s=0, entonces elige otro k y prueba otra vez.

El par (r,s) es la firma.

ecdh-ecdsa-4

Alice firma el hash z usando su clave privada d_A y un número aleatorio k. Bob verifica que el mensaje ha sido firmado por Alice usando su clave pública H_A

Simplificándolo, este algoritmo primero genera un punto secreto k. k se esconde en r gracias a la multiplicación de puntos (que, recordemos, es “fácil” de hacer pero “difícil” de deshacer). Luego usamos r en la ecuación s=k^{-1}(z+rd_A)\mathbf{mod}\ {n}.

Sabes que para calcular s, hemos calculado el inverso de k módulo n. Cómo ya dijimos en el artículo anterior, esto solo funcionará siempre si n es un número primo. Si un subgrupo tiene un orden no-primo, no podremos utilizar ECDSA.

Verificando una firma

Para poder verificar la firma de Alice necesitaremos su clave pública H_A, el hash (truncado) z y, obviamente, la firma (r,s).

  1. Calcula el número entero u_1=s^{-1}z\mathbf{mod}\ {n}
  2. Calcula el entero u_2=r^{-1}z\mathbf{mod}\ {n}
  3. Por último, calcula el punto P=u_1G+u_2H_A

La firma solo es válida si r=x_P\mathbf{mod}\ {n}

Demostración del algoritmo

La lógica detrás de este algoritmo puede que no sea obvia a primera vista, sin embargo, si ponemos todas las ecuaciones que hemos visto hasta ahora juntas, probablemente lo veas más claro.

Empecemos a partir de P=u_1G+u_2H_A. Sabemos, por la definición de clave pública, que H_A=d_AG (dónde d_A es la clave privada). Podemos escribir:

P=u_1G+u_2H_A

P=u_1G+u_2d_AG

P=(u_1+u_2d_A)G

Usando las definiciones de u_1 y u_2, podemos escribir:

P=(u_1+u_2d_A)G

P=(s^{-1}z+s^{-1}rd_A)G

P=s^{-1}(z+rd_A)G

En estas ecuaciones hemos omitido “\mathbf{mod}\ {n}” por dos motivos: brevedad y redundancia.

Previamente, hemos definido s=k^{-1}(z+rd_A)\mathbf{mod}\ {n}. Multiplicando ambos lados de la ecuación por k y dividiendo por s, obtenemos: k=s^{-1}(z+rd_A)\mathbf{mod}\ {n}. Sustituyendo este resultado en nuestra ecuación para P, obtenemos:

P=s^{-1}(z+rd_A)G

P=kG

¡Esta es la misma ecuación para P que teniamos en el paso 2 de nuestro algoritmo para generación de firmas! Cuando generamos firmas y cuando las verificamos, estamos calculando el mismo punto P, simplemente usamos caminos/ecuaciones diferentes. Y por eso el algoritmo funciona.

Haciendo pruebas con ECDSA

Una vez más, Andrea Corbellini ha escrito un pequeño script Python para la generación y verificación de firmas. El código comparte algunas partes con el script para ECDH, concretamente comparte los parámetros y el algoritmo de generación de claves públicas y privadas.

El script debería producir un output parecido a este:

Curve: secp256k1
Private key: 0x9f4c9eb899bd86e0e83ecca659602a15b2edb648e2ae4ee4a256b17bb29a1a1e
Public key: (0xabd9791437093d377ca25ea974ddc099eafa3d97c7250d2ea32af6a1556f92a, 0x3fe60f6150b6d87ae8d64b78199b13f26977407c801f233288c97ddc4acca326)

Message: b'Hello!'
Signature: (0xddcb8b5abfe46902f2ac54ab9cd5cf205e359c03fdf66ead1130826f79d45478, 0x551a5b2cd8465db43254df998ba577cb28e1ee73c5530430395e4fba96610151)
Verification: signature matches

Message: b'Hi there!'
Verification: invalid signature

Message: b'Hello!'
Public key: (0xc40572bb38dec72b82b3efb1efc8552588b8774149a32e546fb703021cf3b78a, 0x8c6e5c5a9c1ea4cad778072fe955ed1c6a2a92f516f02cab57e0ba7d0765f8bb)
Verification: invalid signature

Como podéis ver, en primer lugar el script firma un mensaje (la cadena “Hello!”). Seguidamente verifica la firma, que obviamente, coincide.

Después, intenta verificar la firma con otro mensaje (“Hi there!” en vez de “Hello!”), y la verificación falla.

Por último, intenta verificar la firma con el mensaje correcto (“Hello!”) pero con una clave pública aleatoria. Y otra vez el script falla en la verificación y devuelve un error.

Solo usando la clave pública correcta del autor en su mensaje, obtendremos como resultado a firma verificada.

Es decir, el propietario, y solamente él, de cierta clave pública puede demostrar ser el propietario de la clave privada correspondiente sin revelarla. Por ejemplo,podemos verificar la identidad del autor del mensaje firmado.

La importancia de k

Cuando “firmamos” con ECDSA, es muy importante que mantengamos k en secreto. Si usáramos la misma k en todas nuestras firmas, o si nuestro generador de números aleatorios fuera predecible de alguna manera, ¡un atacante podría encontrar nuestra clave privada!

Este es el tipo de fallo que cometió Sony hace unos años. Básicamente, la consola de juegos PlatStation 3 solo puede ejecutar juegos firmados por Sony usando el algoritmo ECDSA. De esta forma, si queremos crear un nuevo juego para PlayStation 3, no podríamos distribuirlo al público sin la firma de Sony. El problema fue el siguiente: todas las firmas de Sony se generaron usando una k estática.

Nota graciosa: aparentemente, el generador de números aleatorios de Sony estaba inspirado en XKCDDilbert.

Al usar una k fija, podíamos recuperar fácilmente la clave privada de Sony d_S simplemente comprando 2 juegos firmados por Sony, extrayendo sus hashes (z_1 y z_2) y sus firmas ((r_1,s_1) y (r_2,s_2)), junto con el resto de parámetros.

Estos serían los pasos a seguir:

  • Primero, sabed que r_1=r_2 (porque r=xP\mathbf{mod}\ {n} y P=kG son iguales para ambas firmas).
  • A partir de la ecuación para s, (s_1-s_2)\mathbf{mod}\ {n}=k^{-1}(z_1-z_2)\mathbf{mod}\ {n}
  • Ahora multiplica ambos lados de la ecuación por k: k(s_1-s_2)\mathbf{mod}\ {n}=(z_1-z_2)\mathbf{mod}\ {n}.
  • Divide entre (s_1-s_2) para obtener k=(z_1-z_2)(s_1-s_2)^{-1}\mathbf{mod}\ {n}.

La última ecuacion nos permite calcular k usando solo los dos hashes y sus correspondientes firmas. Ahora podemos extraer la clave privada usando la ecuación para s:

s=k^{-1}(z+rd_S)\mathbf{mod}\ {n} \Rightarrow d_S=r^{-1}(sk-z)\mathbf{mod}\ {n}[/latex]

Métodos parecidos pueden usarse si k no es estática pero si es predecible de alguna manera.

¡Más en el próximo artículo!

Espero de verdad que hayáis entendido y os haya entretenido este artículo. Sino, una segunda leída acompañada de papel y lápiz para despejar un par de incógnitas, seguro que te ayuda.

Si te han quedad preguntas, o si directamente no has entendido nada no dudes en preguntar. ¡¡Te ayudaremos encantados!!

La cuarta entrega de esta serie de artículos sobre criptografía de curva elíptica tratará sobre algunas técnicas para resolver logaritmos discretos, algunos fallos importantes de la criptografía de Curva Elíptica y una comparación “superficial” con RSA, ¡no te lo pierdas!

Lee el siguiente artículo de la serie » (pendiente de publicación)

The following two tabs change content below.
Libertario, tecnófilo e ingeniero mecánico. Apasionado de la tecnología blockchain en general y de Monero en particular.

Latest posts by Fernando Gomez (see all)