Curvas elípticas – ¿Qué son y que propiedades tienen?

Criptomanía | Introducción formal a la Criptografía de Curva Elíptica. Curvas elípticas: qué son y propiedades. Sigue leyendo para saber más.

Este artículo es la primera 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? (el artículo actual)
  2. Curvas elípticas: cuerpos finitos y logaritmo discreto
  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

Quiero recordar que para poder aprovechar al máximo esta serie de artículos sobre criptografía de curva elíptica necesitas unos conocimientos previos. Puedes conseguir todos los conocimientos previos necesarios leyendo los siguientes artículos de Criptomanía:

¿Listo? ¡Empecemos!

Curvas Elípticas

Primero: ¿qué es una curva elíptica? Wolfram MathWorld ofrece una excelente y más que completa definición. Pero para nuestro objetivo, una curva elíptica se reduce al conjunto de puntos que satisfacen la ecuación:

dónde  (esto es necesario para excluir curvas singulares).

Además necesitamos “un punto impropio” (punto del infinito) que llamaremos “identidad” y denominaremos con el símbolo 0 (cero)

ejemplos curvas elipticas
Distintas formas para diferentes curvas elípticas (b=1, y a toma valores desde a=2 hasta a=-3).
ejemplos excepciones curvas elipticas
Tipos de singularidades: en la izquierda una curva con una cúspide (y^2=x^3). En la derecha, una curva que se corta a si misma (y^2=x^3−3x+2). Ninguna de ellas es una curva elíptica válida.

Dependiendo del valor de a y b, las curvas elípticas tomarán distintas formas en el plano. Como se puede ver fácilmente, las curvas elípticas son simétricas sobre el eje x.

Si queremos tener en cuenta el “punto impropio” podemos refinar nuestra definición de las curvas elípticas así:

Grupos

Un grupo en matemáticas es un “conjunto de elementos” para los que hemos definido una operación binaria. Normalmente esta operación la llamamos “suma” y la indicamos con el símbolo “+”.

Para que el conjunto G sea un grupo, la suma debe respetar las siguientes cuatro propiedades:

  1. Clausura lineal: Si a y b son parte de G, entonces a+b forma también parte de G;
  2. Propiedad asociativa: ;
  3. Elemento neutro o identidad 0 de forma que ;
  4. Todo elemento tiene un elemento simétrico inverso. Esto quiere decir que por cada “a” existe “b” de forma que .

Si se cumple un quinto requisito:

  1. Propiedad conmutativa: ,

Entonces el grupo es lo que llamamos un grupo abeliano.

Con la noción extendida de una suma, los números enteros () es un grupo (de hecho, es un grupo abeliano). Sin embargo, los números naturales () no son un grupo, ya que el requisito número 4 no es cumplido.

“Agrupar” los números es buena idea, porque si podemos demostrar que esos 4 requisitos se cumplen, obtendremos otras “propiedades gratis”.

Por ejemplo, la identidad o elemento neutro es único; también los inversos son únicos, lo que significa que por cada elemento a existe solo un elemento b que cumpla  (y podemos escribir ).

De manera directa o indirecta, estas propiedades de los grupos van a ser muy importantes para nosotros más adelante.

Propiedades de grupo de las curvas elípticas

Podemos hacer un grupo a partir de las curvas elípticas. Específicamente:

  • Los elementos de un grupo son los puntos de una curva elíptica;
  • El elemento neutro es el “punto impropio” 0;
  • El inverso de un punto P es el punto simétrico respecto al eje x;
  • La operación de la “suma” sigue esta estructura: dados tres puntos alineados y distintos de 0, P, Q y R, su suma es .
tres puntos alineados curvas elipticias
La suma de los tres puntos alineados es 0.

Notad que para esto solo necesitamos tres puntos alineados, sin importar el orden. Esto significa que si P, Q y R están alineados, entonces . De esta forma acabamos de “demostrar” que nuestro operador “+” cumple ambas propiedades: asociativa y conmutativa. Es un grupo abeliano.

Hasta aquí todo bien. Pero, ¿cómo operamos la suma de dos puntos arbitrarios?

Suma geométrica

Gracias al hecho de que estamos en un grupo abeliano, podemos reescribir como .

Esta ecuación, en esta forma, nos permite dilucidar un método geométrico para calcular la suma entre dos puntos P y Q: si dibujamos una línea que pase sobre P y Q, esta línea intersectará un con la curva en un tercer punto, R (esto ya está implícito en el hecho de que P, Q y R están alineados). Si calculamos la inversa de este punto, −R, hemos calculado el resultado de P+Q.

suma geometrica curvas elipticas
Dibuja la línea que corta la curva en P y Q. La línea intersecta la curva en un tercer punto R. El punto simétrico, −R, es el resultado de la operación de suma P+Q.

Excepciones

Este método de resolución geométrico funciona, pero existen excepciones:

  • ¿Qué pasa si  or ? No podemos dibujar ninguna línea (0 no está en el plano xy). Pero dado que hemos definido 0 como elemento neutro,  and , para cualquier P y Q.
  • ¿Qué pasa si ? En este caso, la línea que cruza los dos puntos es vertical y no intersecta en un tercer punto. Pero si P es la inversa de Q, entonces a partir de la definición de inverso.
  • ¿Qué pasa si ? En este caso, hay infinitas líneas ya que hay un solo punto de intersección con la curva. Aquí las cosas se ponen complicadas. Pero consideremos un punto . ¿Qué pasa si poco a poco acercamos Q′ a P?
animation suma puntos curvas elipticas
Cuando Q tiende a P, la línea que cruza ambos es tangente a la curva. Podemos decir que P+P=−R, dónde R es el punto de intersección entre la curva y la línea tangente a la curva en P.
  • ¿Qué pasa si , pero no hay tercer punto R? Es un caso muy similar al anterior. De hecho, la línea que pasa por P y Q en este caso también es tangente a la curva.
    animation-tangent-line curvas elipticas
    Si nuestra línea intersecta solo en dos puntos,es tangente a la curva. Podemos observar que entonces la suma de ambos puntos es simétrica a uno de ellos.

    Asumamos que P es el punto de tangencia. En el caso anterior, habríamos escrito . Esa ecuación ahora es . Por otro lado, si el punto de tangencia fuera Q, la ecuación correcta sería .

Nuestra suma geométrica cubre ahora todos los casos. Con lápiz y regla podemos dos o más puntos de cualquier curva elíptica. Echa un vistazo a esta herramienta interactiva para hacer sumas en curvas elípticas

Suma algebraica

Si queremos que un ordenador opere sumas de puntos, necesitamos convertir el método geométrico en un método algebraico. Transformar las reglas descritas arriba en un conjunto de ecuaciones puede parecer simple, pero es tedioso porque requiere resolver ecuaciones cúbicas. Por esa razón en este apartado no desarrollaremos los cálculos, enseñando solo resultados.

Primero, vamos a librarnos de los casos más molestos. Ya sabemos que . Así que, en nuestras ecuaciones, vamos a evitar estos dos casos y solo consideraremos dos puntos distintos de cero y no simétricos  y .

Si P y Q son distintos (), entonces la línea que cruza ambos tiene una pendiente:

La intersección de esta línea en la curva elíptica es un tercer punto :

O, de manera equivalente:

Luego,  (prestad atención a los signos y recordad que ).

Si quisiéramos comprobar si este resultado es correcto, tendríamos que comprobar si R pertenece a la curva y si P, Q y R están alineados. Comprobar que los puntos están alineados es trivial, pero comprobar si R pertenece a la curva no lo es. Necesitamos resolver ecuaciones cúbicas, que no es fácil en absoluto.

En cambio, probemos con un ejemplo: de acuerdo con la herramienta online anterior, dado  y  en la curvas , su suma es .

Veamos si nuestras ecuaciones están de acuerdo:

¡Sí, es correcto!

Daos cuenta que estas ecuaciones funcionan incluso si o P o Q es un punto de tangencia. Intentemoslo con .

Hemos obtenido el resultado , el mismo que nos demuestra la herramienta online.

Excepciones

El caso  necesita que se trate de manera diferente: las ecuaciones de  e  son las mismas, pero ya que , necesitamos una ecuación distinta para la pendiente (la anterior ecuación devolvería como resultado la indeterminación ):

Ved que, como cabía esperar, esta expresión para la pendiente m es la primera derivada de:

* despejada de la ecuación general de una curva elíptica

Para probar la validez de este resultado debería ser suficiente con comprobar que R pertenece a la curva y que la línea que la cruza a través de P y R tiene solo dos intersecciones con esta.

Una vez más, para ahorrarnos tediosas operaciones matemáticas, vamos a usar un ejemplo: .

Y obtenemos el resultado . ¡Correcto!

Multiplicación escalar

Además de la suma, podemos definir otra operación: multiplicación escalar:

Donde n es un número natural. También hay una herramienta visual para multiplicaciones escalares, en caso de que queráis hacer pruebas con ella.

Descrito de esta forma, puede parecer que calcular  requiere n sumas. Si tiene  dígitos binarios, entonces nuestro algoritmo sería , lo que no es nada bueno (tiempo exponencial). Pero existen algoritmos mucho más rápidos.

Uno de ellos es el algoritmo “double and add”. Su funcionamiento se puede explicar mejor con un ejemplo.

Tomemos . Su representación en binario es . Esta representación binaria se puede convertir en una suma de potencias de 2:

(Hemos tomado cada digito binario de y lo hemos multiplicado por una potencia de 2.)

En vista de esto, también podemos decir que:

Entonces, lo que haría el algoritmo “double and add”  para resolver es:

  • Coger P.
  • Duplicar P, para obtener 2P.
  • Sumar 2P a P (para calcular el resultado de ).
  • Duplicar 2P, para obtener .
  • Sumar a nuestro resultado (para calcular .
  • Duplica  para calcular .
  • No hace nada con  (el factor que le acompañaba era 0).
  • Duplica para obtener .
  • Súmar al resultado acumulado (para conocer ).

Al final, con el algoritmo double and add, podemos calcular  en solo 7 “duplicaciones” y 4 sumas. La cantidad de operaciones no ha crecido dramáticamente al calcular  respecto a 

Si duplicar y sumar son ambas operaciones (tiempo lineal o problema “muy fácil”) entonces este algoritmo es  (tiempo logarítmico) lo que no está nada mal. Por supuesto, ¡mucho mejor que el algoritmo inicial  (tiempo exponencial o “muy difícil”)!

Logaritmo

Dado n y P, tenemos al menos un algoritmo para calcular en un “tiempo polinómico” .

¿Pero y que pasa para hacer la operación contraria? ¿Qué pasa si conocemos Q y P y necesitamos averiguar n?

Este problema es conocido como el problema del logaritmo. Y lo llamamos “logaritmo” en vez de “división” por uniformidad con otros criptosistemas (donde en vez de multiplicación, tenemos exponenciación)

No es de dominio público ningún algoritmo “fácil” para el problema del logaritmo, sin embargo, jugar con ejemplos sirve para ver algunos patrones.

Si experimentáramos lo suficiente, probablemente podríamos encontrar más patrones que eventualmente pudieran llevarnos a desarrollar un algoritmo para resolver de manera relativamente eficiente un logaritmo en una curva elíptica.

Pero hay una variante del problema del logaritmo: “el problema del logaritmo discreto”. Cómo veremos en el siguiente artículo, si reducimos el dominio de nuestras curvas elípticas, las multiplicaciones escalares siguen siendo “fáciles”, mientras que el logaritmo discreto se convierte en un problema “difícil”.

Esta dualidad es el elemento clave de la criptografía de curva elíptica.

Seguimos en el próximo artículo…

Esto es todo por este artículo, espero que lo hayáis disfrutado.

En el siguiente artículo descubriremos los campos finitos y el problema del logaritmo discreto, junto con ejemplos y herramientas para hacer pruebas. Si te interesa saber más, ¡sigue leyendo!

Lee el siguiente artículo »

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 *