Curva Elíptica – Cuerpos finitos y logaritmos discretos

Criptomanía | Introducción formal a la Criptografía de Curva Elíptica. Cuerpos finitos y logaritmos discretos. Sigue leyendo para saber más.

Este artículo es la segunda 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 (el artículo actual)
  3. ECDH y ECDSA: ejemplos de algoritmos de criptografía de curva elíptica
  4. Algoritmos para desencriptar criptosistemas ECC en comparación con criptosistemas RSA

En el artículo anterior, hemos visto 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 (). 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 () y hemos encontrado un algortimo “fácil” para calcular las multiplicaciones escalares: double and add.

Ahora vamos a restringir nuestras curvas elípticas a cuerpos (o campos) finitos.

El “cuerpo” de los enteros módulo p

Un “cuerpo finito” es, primero de todo, un conjunto con un número finito de elementos. Un ejemplo de un cuerpo finito es el conjunto de enteros modulo p, dónde p es un número primo. Generalmente se denomina como  o . Nosotros usaremos la última forma de notación.

En todos los cuerpos tenemos dos operaciones binarias: suma (+) y multiplicación (·). Ambas cumplen las propiedades asociativas, conmutativas y de clausura. Para ambas operaciones existe un único elemento identidad, y para cada elemento hay un elemento inverso único. Por último, la multiplicación es distributiva sobre la suma: 

El conjunto de enteros módulo p consiste de todos los números enteros desde 0 hasta p−1. Suma y multiplicación funcionan como en la aritmética modular (también conocida como “aritmética del reloj”).

Aquí algunos ejemplos de operaciones en :

  • Suma: 
  • Resta:
  • Multiplicación: 
  • Inverso aditivo: 
    De hecho: 
  • Inverso multiplicativo
    De hecho: 

Si estas ecuaciones te suenan a chino y necesitas una introducción a la aritmética modular, echa un vistazo a Khan Academy.

Como ya hemos dicho, los enteros modulo p son un cuerpo, y por eso se dan todas las propiedades listadas arriba.

¡El requisito de que sea un número primo es importante! El conjunto de enteros módulo 4 no es un cuerpo: 2 no tiene un inverso multiplicativo (la ecuación no tiene solución).

División modulo p

Pronto usaremos todos estos conceptos en las curvas elípticas en , pero antes de hacerlo es necesario aclarar como calcular .

No es complicado. Simplemente sustituimos así para que quede así:

O por escrito, x dividido entre y es igual a x multiplicado por el inverso multiplicativo de y.

Es decir, para calcular la división tenemos que encontrar el inverso multiplicativo de un número y realizar una simple multiplicación.

El inverso multiplicativo se puede calcular “fácilmente” con el algoritmo de Euclides extendido. En el peor de los casos, este algoritmo tiene una dificultad logarítmica .

Curvas elípticas en Fp

Ahora ya conocemos todo lo necesario para limitar las curvas elípticas a . El conjunto de puntos, que en artículo anterior era:

Ahora se convierte en:

Donde es aún el punto impropio, y  y  son dos números enteros que pertenecen a  .

curva elíptica discretas
En la imagen superior: La curva  con . Notad que, para cada , hay como máximo dos puntos. También ved la simetría sobre el eje en .

curva eliptica discretas singulares
En la imagen superior: La curva  es singular y tiene un punto triple en . No es una curva elíptica válida.

Cómo habréis visto, lo que en el artículo anterior eran curvas continuas, son ahora un conjunto de puntos “inconexos” en el plano-xy. Pero podemos probar que, incluso habiendo restringido el dominio, las curvas elípticas en  todavía son un grupo abeliano.

Suma de puntos

Claramente, necesitamos cambiar un poco la definición de la suma para que funcione bien en . Antes, decíamos que la suma de tres puntos alineados era cero (). Podemos mantener esta definición, pero ¿qué significa que tres puntos estén alineados en ?

Podemos decir que tres puntos están alineados si hay una línea que los conecta a los tres. Pero, por supuesto, las líneas en no son iguales que en . Podemos decir, informalmente, que una línea en es el conjunto de puntos que satisfaga la ecuación (esta es la ecuación general para una línea, con el único añadido de ““).

suma de puntos curva eliptica discreta

En la imagen superior: La suma de puntos ( y ) en la curva .

Podéis ver que la línea que conecta los puntos se “repite” cíclicamente en el plano.

Dado que estamos en un grupo, la suma de puntos mantiene las propiedades que ya conocemos:

  • Q+0=0+Q=Q (a partir de la definición de elemento identidad).
  • Dado un punto distinto de cero Q, la inversa −Q es el punto simétrico sobre y= p/2.
    Dicho de otra forma, −Q=(xQ,−yQmodp).
    Por ejemplo, si una curva en F29 tiene un punto Q=(2,5), la inversa es −Q=(2,−5mod29)=(2,24).
  • P+(−P)=0 (a partir de la definición de elemento inverso).

Suma algebraica

Las ecuaciones para calcular la suma de puntos son exactamente las mismas que en artículo anterior, excepto por el hecho de que necesitamos añadir “mod p” al final de cada expresión.

Así que, dado , podemos calcular P+Q=−R de la siguiente forma:

Si P≠Q, entonces la pendiente m asume la forma:

Si P=Q, entonces m tendrá esta forma:

No es una coincidencia que las ecuaciones no hayan cambiado: de hecho, estas ecuaciones funcionan en cualquier cuerpo (campo), finito o infinito (con la excepción de y , que son dos casos especiales). Para respaldar esta afirmación necesitamos matemáticas muy complejas. Pero si estás muy interesado en saber porque estas ecuaciones funcionan en (casi) cualquier campo, esta es la explicación más sencilla que he encontrado.

Volviendo al tema que nos atañe — no vamos a definir un método geométrico: de hecho, hay unos cuantos problemas con estos. Por ejemplo, en el caso de necesitar calcular P+P necesitamos usar la tangente a la curva en P. Pero sin una curva continua, la palabra “tangente” no tiene ningún sentido. Podemos “solucionar” este y otros problemas que surgen, sin embargo un método geométrico puto sería muy complicado y nada práctico.

Podéis jugar con esta herramienta interactiva para realizar sumas de puntos.

El orden de una curva elíptica

Hemos dicho que una curva elíptica restringida a un cuerpo finito tiene un número finito de puntos. Una pregunta importante que surge de esta afirmación es: ¿cuántos puntos hay exactamente?

Primero, aclarar que el número de puntos que existen en un grupo es lo que se conoce como el orden de grupo.

Probar todos los valores posibles para x desde 0 hasta p−1 no es una forma factible de contar puntos, ya que requeriría O(p) pasos, y esto puede ser “difícil” si p es un número primo largo.

Por suerte, hay un algoritmo más rápido para calcular el orden: el algoritmo de Schoof’s. No vamos a entrar en detalles sobre este algoritmo — lo que importa es que resuelve el orden de un grupo en tiempo polinómico, que es lo que necesitamos.

Multiplicación escalar y subgrupos cíclicos

Podemos definir una multiplicación como:

Y, una vez más, podemos usar el double and add algorithm para calcular una multiplicación en O(logn) pasos (o O(k), donde k es el número de bits de n). Aquí tenéis una herramienta interactiva para multiplicaciones escalares.

La multiplicación de puntos en una curva elíptica restringida a Fp tiene una propiedad interesante. Usad en la herramienta interactiva la curva y el punto P=(3,6). Ahora calcula todos los múltiplos de P:

curvas elipticas discretas modular
Los múltiplos de P=(3,6) son solo 5 puntos distintos (0, P, 2P, 3P, 4P) que se repiten cíclicamente. Es muy fácil observar el parecido entre la multiplicación escalar y la suma en la aritmética modular.
  • 0P=0
  • 1P=(3,6)
  • 2P=(80,10)
  • 3P=(80,87)
  • 4P=(3,91)
  • 5P=0
  • 6P=(3,6)
  • 7P=(80,10)
  • 8P=(80,87)
  • 9P=(3,91)

Dos deducciones rápidas: los múltiplos de P son solo cinco (los demás puntos de la curva no participan) y se repiten cíclicamente. Así que podemos escribir:

  • 5kP=0
  • (5k+1)P=P
  • (5k+2)P=2P
  • (5k+3)P=3P
  • (5k+4)P=4P

Para cada número entero k.

Estas 5 ecuaciones se pueden “comprimir” en una sola, gracias al operador “módulo”: .

Además podemos verificar que estos cinco puntos cumplen la propiedad de clausura de la suma. Esto significa: sin importar si sumo 0, P, 2P, 3P or 4P, el resultado siempre debería ser uno de estos 5 puntos. Y una vez más, los demás puntos de la curva elíptica no aparecen.

Esto mismo vale para cualquier punto, y no solo P=(3,6). De hecho, si tomamos un punto P genérico:

Lo que significa: si sumamos dos múltiplos de P, obtenemos como resultado otro múltiplo de P (porque los múltiplos de P cumplen la propiedad de clausura de la suma).

Esto es suficiente para probar que el conjunto de múltiplos de P es un subgrupo cíclico del grupo formado por la curva elíptica.

Un “subgrupo” es un grupo formado por un subconjunto de otro grupo. Un “subgrupo cíclico” es un subgrupo cuyos elementos se repiten cíclicamente, como hemos demostrado en el ejemplo anterior.

El punto P se llama generador o punto base del subgrupo cíclico.

Los subgrupos cíclicos son los fundamentos sobre los que se construye criptografía elíptica y otros criptosistemas. Veremos porque en el siguiente artículo.

Orden del subgrupo

Ahora tenemos que averiguar cuál es el orden de un subgrupo generado por un punto P (o, de manera equivalente, cual es el orden de P). Para responder a esta pregunta no podemos usar el algoritmo de Schoof, porque ese algoritmo solo funciona en curvas elípticas completas, no en subgrupos. Antes de asaltar el problema necesitamos saber dos pequeñas cosas más:

  • Hasta ahora, hemos definido el orden cómo el número de puntos de un grupo. Esta definición es aún correcta, pero dentro de un subgrupo cíclico podemos dar otra definición: el orden de P es el número entero positivo n más pequeño posible de manera que nP=0. Por ejemplo, si veis el caso del ejemplo anterior, nuestro subgrupo de orden 5 tenía 5 puntos y satisfacía la condición 5P=0.
  • El orden de P está relacionado con el orden de la curva elíptica por el teorema de Lagrange, que establece que el orden de un subgrupo es un divisor del orden del grupo al que pertenece. En otras palabras, si una curva elíptica contiene N puntos y uno de sus subgrupos contiene n puntos, entonces n es divisor de N.

Con esto que acabamos de aprender, tenemos una forma de averiguar el orden de un subgrupo con punto base P:

  1. Calcular el orden de la curva elíptica N usando el algoritmo de Schoof’s.
  2. Calcular todos los divisores de N.
  3. Para cada divisor n de N, calcula nP.
  4. La n más pequeña que cumpla nP=0 es el orden del subgrupo.

Ejemplos

Por ejemplo, la curva  en el campo  tiene un orden N=42. Sus subgrupos podrán tener un orden n=1, 2, 3, 6, 7, 14, 21 o 42. Si probamos P=(2,3) podemos ver que P≠0, 2P≠0, …, 7P=0, luego el orden de P es n=7.

Sabed que es importante usar el divisor más pequeño posible, y no uno al azar. Si hubiéramos cogido uno al azar podríamos haber elegido n=14. 14P=0 pero 14 no es el orden del subgrupo, sino uno de sus múltiplos.

Otro ejemplo: la curva definida por la ecuación  sobre el campo  tiene un orden N=37, que es primo. Sus subgrupos solo podrán tener orden n=1 o 37. Como seguro que habrás adivinado, cuando n=1, el subgrupo incluye un único punto: el punto ideal. Cuando n=N, el subgrupo contiene todos los puntos de la curva elíptica.

Elegir un punto base

Siempre nos interesan subgrupos con órdenes altos. Así que generalmente elegiremos una curva elíptica, calcularemos su orden (N), elegiremos un divisor alto para el subgrupo (n) y por último buscaremos un punto base adecuado.

No elegiremos un punto base y calcularemos su orden, sino lo contrario: primero elegiremos un orden suficientemente alto y luego encontraremos un punto base adecuado. ¿Cómo hacemos esto?

Antes, tenemos que presentaros un nuevo término. El teorema de Lagrange implica que el número h=N/n siempre es un número entero (porque n es un divisor de N). El número h tiene nombre propio: es el cofactor del subgrupo.

Para cualquier punto de la curva elíptica tenemos NP=0. Esto pasa porque N (orden del grupo) es múltiplo de cualquier candidato a orden del subgrupo (n). Expresando esta definición como formula:

n(hP)=0

Ahora supón que n es un número primo (por razones que se explicarán en el siguiente artículo, siempre preferimos usar número primos como orden del grupo). Esta ecuación, escrita así, nos dice que el punto G=hP genera un subgrupo de orden n (excepto cuando G=hP=0, en cuyo caso el subgrupo tiene orden 1).

Gracias a esto, podemos definir el siguiente algoritmo:

  1. Calcular el orden N de la curva elíptica.
  2. Elegir un orden n del subgrupo. Para que el algoritmo funcione, ese número tiene que ser primo y debe ser divisor de N.
  3. Calcula el cofactor del subgrupo h=N/n.
  4. Elige un punto P en la curva.
  5. Calcula G=hP.
  6. Si G es 0, entonces vuelve al paso 4. Si no acabamos de encontrar un generador de un subgrupo con orden n y cofactor h.

Este algoritmo solo funciona si n es primo. Si n no fuera primo, entonces el orden de G podría ser uno de los divisores de n.

Logaritmo discreto

Cómo ya hicimos con las curvas elípticas continuas, ahora vamos a discutir la pregunta clave: ¿si conocemos P y Q, podemos calcular k para que se cumpla Q=kP?

Este problema, que se conoce como el problema del logaritmo discreto para curvas elípticas, se considera un problema “difícil”, ya que no hay ningún algoritmo conocido que pueda resolverlo en tiempo polinómico. Sin embargo, no hay pruebas matemáticas que aseguren que no puede existir dicho algoritmo.

Este problema también es análogo al problema del logaritmo discreto usado en otros criptosistemas como Digital Signature Algorithm (DSA), intercambio de claves Diffie-Hellman (D-H) y el algoritmo ElGamal — no es una coincidencia que todos tengan el mismo nombre. La única diferencia es que en esos algoritmos utilizamos la exponenciación modular en vez de la multiplicación escalar. Su problema del logaritmo discreto se puede resumir así: si conocemos a y b, ¿podemos calcular k para que se cumpla ?

Ambos problemas son “discretos” porque implican conjuntos finitos (más concretamente, subgrupos cíclicos). Y son “logaritmos” porque son análogos a los logaritmos ordinarios.

seguridad criptografia curvas elipticas

Lo que hace interesante a la criptografía de curva elíptica es que, a día de hoy, el logaritmo discreto para las curvas elípticas parece “más difícil” en comparación a otros criptosistemas. Esto implica que se necesita que k tenga menos bits para conseguir el mismo nivel de seguridad que en otros sistemas, como veremos con más detalle en la cuarta entrega de esta serie de artículos.

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

La tercera entrega de esta serie de artículos sobre criptografía de curva elíptica será sobre 2 algoritmos concretos, ECDH y ECDSA. Es la parte más interesante de la serie, si has llegado hasta aquí, ¡no te la pierdas!

Lee el siguiente artículo de la serie »

The following two tabs change content below.
Ingeniero mecánico, redactor e inversor FinTech. Apasionado del mundo de las criptodivisas y las aplicaciones de las diferentes blockchains.

Latest posts by Fernando Gomez (see all)

Be First to Comment

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *