Matemáticas, Criptografía y otras hierbas

Las curvas elípticas son objetos geométricos con sabor aritmético e increíblemente interesantes por sus diversas aplicaciones y conexiones con problemas teóricos y la criptografía. Si buscas en Google o le preguntas a una IA por cómo se ven, probablemente verás una imagen como esta:

La criptografía de clave pública está basada en problemas matemáticos de difícil solución y las curvas elípticas nos otorgan una de ellas.

Cuerpo de definición

Lo primero es que debemos fijar un espacio donde observarlas. Este espacio vendrá de una estructura algebraica llamada cuerpo, al que denotaremos por $K$. Los ejemplos de cuerpos más conocidos son los números reales $\mathbb{R}$, los complejos $\mathbb{C}$ y los racionales $\mathbb{Q}.$ Algo que caracteriza a los ejemplos anteriores es que si sumamos $1+1+\ldots+1$ las veces que queramos, este resultado jamás será $0$. Estos cuerpos son llamados cuerpos de característica $0$.

Existen otras familias de cuerpos de naturaleza diferente. Cuando cambiamos la aritmética usual por la aritmética modular, obtenemos el conjunto de los enteros módulo $n$ al que denotamos como

Cuando $n$ es un número primo (en tal caso mejor escribimos $p$ en vez de $n$) , el conjunto $\mathbb{Z}_p$ es un cuerpo y tiene $p$ elementos. En este caso, cuando calculamos $1+1+\ldots+1$ $p$ veces, el resultado será 0. Este cuerpo es llamado cuerpo de característica $p$ y lo denotamos como $\mathbb{F}_p$ . También existen cuerpos finitos $\mathbb{F}_{p^n}$ de $p^n$ elementos, cuya construcción se explica en este post

Definiendo una curva elíptica

Una curva elíptica sobre un cuerpo $K$ está definida por una curva no singular de la forma:

donde $a_1,a_2,a_3,a_4,a_6\in K$. A esta expresión se le llama ecuación de Weierstrass generalizada.

¿Qué significa que la curva sea no singular? La ecuación anterior determina un polinomio

luego la curva (o su gráfica) está dada por los puntos

Diremos que una solución $(a,b)$ es singular si

Por lo tanto, que la curva sea no singular quiere decir que la condición anterior no se cumple para ninguno de sus puntos. Geométricamente, significa que la curva no se cruza a sí misma ni tiene puntas. Es decir, es suave.

Si $K$ es un cuerpo de característica distinta de 2 y 3, es posible transformar la ecuación anterior en la Ecuación corta de Weierstrass:

La transformación corresponde a cambios de variables en los cuales se dividen por 2 y 3. Esto no se podría hacer si la curva estuviera definida en un cuerpo del tipo $\mathbb{F}_{2^n}$ o $\mathbb{F}_{3^n}$ pues 2 y 3 serían iguales a 0!

Con todo lo anterior, definimos

Ese punto extra llamado punto en el infinito, tiene su origen en la geometría proyectiva y tiene un rol fundamental cuando veamos la aritmética de la curva.

La geometría

En este post, nos quedaremos con esta definición para una curva elíptica:

donde $a,b$ están en $K$ y verifican que $4a^3+27b^2\neq0$. Esto último asegura que la curva es no singular.

Si la curva está definida sobre $\mathbb{R}$, podría tener una gráfica como las siguientes:

Sin embargo esto cambia cuando la curva está definida sobre un cuerpo finito:

La aritmética

Podemos definir en estas curvas una ley de suma. Así como escuchaste. Más aún, la fórmula para sumar es completamente geométrica.

Supongamos que queremos sumar los puntos $P$ y $Q$ en la curva, de manera de obtener un tercer punto denotado $P+Q$ que también pertenece a la curva.

Comenzamos construyendo la recta que pasa por los puntos $P$ y $Q$:

Esta recta siempre intersecta la curva debido al Teorema de Bézout.

Finalmente, tomamos la recta vertical¹ que pasa por el punto $R’$ en el eje $x$, intersectamos la curva y obtenemos $P+Q$:

Si queremos duplicar un punto, es decir, calcular $S+S$, consideramos la recta tangente a la curva en el punto $S$, intersectamos la recta con la curva y el punto obtenido nuevamente se refleja en el eje $x$:

Lo más interesante es que esta operación suma se comporta bien, es decir, $(E(K),+)$ es un grupo abeliano y el punto en el infinito juega el rol de elemento neutro o cero de la suma.² Este es el sabor aritmético.

Si bien hemos descrito lo anterior en una curva definida en $\mathbb{R}$, el método también vale cuando se trabaja en cuerpos finitos.

Algorítmica de la adición

La base de la definición anterior es el método de la cuerda y la tangente. Pareciera que no es explícito, pero sí lo es. Si consideramos una curva en su ecuación corta de Weierstrass $E\colon y^2=x^3+ax+b$, se tiene lo siguiente:

• Inverso: Dado $P = (x,y)$ en la curva $E$ , su inverso aditivo es $-P(x,y) = (x,-y)$.
• Fórmula de suma: Dado $P = (x_1,y_1)$ y $Q = (x_2,y_2)$ en la curva, donde $P \neq \pm Q$,
  la suma $P+Q = (x_3,y_3)$ es calculada como:
  • $x_3 = \lambda^2 -x_1 – x_2\ y_3 = \lambda (x_1 -x_3) -y_1$
  • $\lambda = \left( \frac{y_2 -y_1}{x_2 – x_1} \right)$
• Fórmula de duplicación: Dado $P= (x,y)$, su duplicación $2P = (x_2,y_2)$ es calculada como:
  • $x_2= \lambda^2 -2x\ y_2= \lambda(x-x_2) -y$
  • $\lambda = \left( \frac{3x^2 + a}{2y} \right)$

Las fórmulas anteriores se obtienen calculando la intersección de la recta que pasa por los puntos y la curva.

Espacio Proyectivo

En las fórmulas anteriores se requiere calcular inversos multiplicativos para obtener el valor de $\lambda$. Esta operación es computacionalmente costosa en el caso de cuerpos finitos; por lo tanto, si queremos, por ejemplo, calcular $k⋅P$, esto crecerá según el tamaño del escalar k. Una forma de evadir estos inversos es regresando al corazón de una de las definiciones de una curva elíptica.

Se define en $K^3\setminus {(0,0,0)}$ la relación de equivalencia

Una clase de equivalencia es denotada por $(X\colon Y\colon Z)$. ³El espacio proyectivo está definido como el conjunto de las clases de equivalencia con esta relación:

Dada $E\colon y^2=x^3+ax+b$ podemos obtener la versión proyectiva⁴ de la curva elíptica con el cambio de variables $x=X/Z$ y $y=Y/Z$ :

Así, un punto $P=(x,y)$ es representado por una tupla en la clase de equivalencia:

y la función inversa está dada por

¿Por qué movernos al espacio proyectivo nos salva de los inversos multiplicativos?

Si tenemos un punto en la curva proyectiva con denominadores en sus coordenadas, podemos multiplicar ese punto por un escalar conveniente y eliminarlos. En el espacio proyectivo, ambos puntos pertenecerán a la misma clase de equivalencia y, por ende, serán iguales. ⁵

Este espacio incluye el punto al infinito del que hablamos antes. Cuando $Z=0$, entonces al reemplazar en la curva tendríamos $X^3=0$, con lo que obtendríamos el punto $\mathcal{O}=(0:1:0).$
Otros modelos de curvas elípticas de interés en criptografía se pueden encontrar aquí: https://hyperelliptic.org/EFD/.

En el siguiente post, se viene un gran tema: curvas elípticas y criptografía.

View this post on Instagram

1. Más general, diríamos la recta que pasa por el punto en el infinito y por $R’.$ ↩︎
2. Washington, L. C. (2008). Elliptic Curves: Number Theory and Cryptography (2a ed.). Chapman and Hall/CRC. ↩︎
3. Existen otras formas de representar los puntos para trabajar en un espacio proyectivo, de manera de aleatorizar las coordenadas y proteger la operación suma de ataques de tipo side channel. Ver, por ejemplo, la sección 3.2.1 del texto de Hankerson,Menezes y Vanstone. ↩︎
4. Otra definición más abstracta: una curva elíptica definida sobre un cuerpo $K$ es una curva de género 1, proyectiva y no singular con un punto distinguido $K$-racional $\mathcal{O}$ (el punto en el infinito). ↩︎
5. Hankerson, D., Menezes, A. J., & Vanstone, S. (2004). Guide to Elliptic Curve Cryptography. Springer Science & Business Media. ↩︎