sobre un campo perfecto (todo polinomio irreducible sobre este campo tenga raíces diferentes) para poder hablar de aplicaciones criptográficas.
Estos campos perfectos por excelencia en criptografía son $latex \mathbb{F}_q$.
Vamos a definir algunas cosas para clasificarlas, ya que anteriormente nos habíamos dedicado a estudiar cada curva por separado, pero ahora queremos considerar TODAS las curvas elípticas sobre un campo $latex \mathbb{K}$ , y ver cuáles son isomorfas, y ver cada clase de curvas isomorfas como la misma curva, como un sólo punto, este espacio es una espacio modular, y generalmente es estudiado como un esquema.
Algo interesante es que en las curvas elípticas es que este espacio tiene dimensión 1, y de hecho es una linea topológicamente hablando.
Como sabemos, una curva elíptica tiene una estructura algebraica y una estructura geométrica, las curvas elípticas son el caso más simple de una variedad abeliana, éstas tienen dimensión 1 (Es decir, al considerar su anillo de coordenadas, su dimensión de Krull es 1, lo cual se traduce a que la cadena más grande de ideales por contención que se puede construir $latex \lbrace J_i \rbrace$ es de altura 1 por lo que $latex J_0 \subset J_1 \subset J_2$ tenemos que $latex J_1 = J_2$ lo que hace al anillo Noetheriano.
Vamos a explorar un poco lo que es una curva elíptica desde el punto de vista más formal, y construiremos relaciones de éstas, clasificaciones, y exploraremos cómo se comporta el anillo de morfismos de la curva en si misma, así como la relación que hay entre la traza y determinante de ciertos endomorfismos con el subgrupo de torsión de la curva en cuestión.
Curva suave de género 1, entonces es elíptica
Todas las curvas de género 1 son elípticas, como lo pueden ver en este post via el teorema de Riemann-Roch , y la construcción de la ecuación en la forma de Weierstrass ahora redefiniremos de una curva elíptica, recordemos que en la estructura algebraica de la curva siempre hay un punto distinguido que nos sirve como identidad visto como variedad abeliana, llamémoslo $latex \mathcal{O}$ , entonces si tenemos que una curva $latex E$ es suave de género g=1 y proyectiva , entonces por el teorema de Riemann-Roch tenemos que si $latex n>2g-2=0$ tenemos que $latex \mathcal{L}(n0)=n-g+2=n$ si $latex n=2$ y $latex n=3$ podemos encontrar dos funciones $latex x,y\in \mathbb{K}(E)$ que tienen exactamente 2 polos en $latex \mathcal{O}$ y $latex y$ tiene 3 polos en $latex \mathcal{O}$ , ahora si $latex n=6$, obtenemos una base para el espacio vectorial $latex \mathcal{L}(6\mathcal{O})$ la cual es $latex \lbrace 1,x,x^2,x^3,y,y^2,xy \rbrace$
La cual nos da la forma usual de la curva elíptica en la forma de Weierstrass como todos la conocemos.
$latex y^2 + f_1xy+f_3y = x^3+f_2x^2 + f_4x + f_6$
tal que $latex f_i \in \mathbb{K}$
Aquí fuimos de álgebra directamente a geometría.
Ahora, ya para geometrizar esto por completo, considera:
$latex \Phi: E \rightarrow \mathbb{P}^{2}_{\mathbb{K}}$
$latex (x,y) \mapsto [x:y:1]$
Ahora, también por lo anterior y Riemann-Roch tenemos que $latex [\mathbb{K}(E):\mathbb{K}(x)]=2$ y que $latex [\mathbb{K}(E):\mathbb{K}(y)]=3$ lo cual implica que $latex [\mathbb{K}(E):\mathbb{K}(x,y)]=1$, por lo que $latex \Phi$ tiene grado 1, como por hipótesis tenemos que $latex E$ es suave, sabemos que su discriminante $latex \Delta\neq 0$ , es decir $latex \Phi(\mathcal{O})=[0:1:0]=\infty$ es el punto al infinito.
Isogenias
La palabra "isogenia" no me gusta, pero no sé cómo traducirla, en inglés se dice "isogeny" , pero bueno, hay poca literatura en español sobre curvas isógenas (o no he buscado bien... o no he buscado más bien en español).
Lo que queremos hacer ahora es definir homomorfismos entre curvas elípticas, es decir queremos comenzar a compararlas de tal manera que ésta comparación respete sus propiedades geometricas y algebraicas.
Sean $latex E$ y $latex F$ dos curvas elípticas sobre $latex \mathbb{K}$ , una isogenia es un mapeo racional $latex \alpha: E\rightarrow F$ que induce homomorfismo de grupos de $latex E(\mathbb{K})$ y $latex F(\mathbb{K})$ (es decir entre los grupos abelianos inducidos por la curva elíptica)
Para entender esta definición, como ya lo había definido en el post antes citado en este post, vamos a redefinir lo que es un campo de funciones de una curva proyectiva en general para saber qué es un mapeo racional.
Sea $latex C(\mathbb{K})$ una curva proyectiva definida por $latex f(x,y,z)=0$ donde $latex f\in \mathbb{K}[x,y,z]$ es irreducible en $latex f\in \bar{\mathbb{K}}[x,y,z]$.
El campo de funciones $latex \mathbb{K}(C)$ son las funciones $latex g/h$ tal que
$latex g,h$ polinomios homogéneos del anillo $latex \mathbb{K}[x,y,z]$ de mismo grado
$latex h\notin (f)$ (el ideal generado por f)
$latex g_1/h_1$ y $latex g_2/h_2$ son equivalentes cuando $latex g_1h_2-g_2h_1 \in (f)$
Si te da miedo lo proyectivo, aquí te dejo la definición afín, pero debes trabajar proyectivamente, aquí te dejo un post anterior sobre el espacio proyectivo.
$latex \mathbb{K}(C)=Frac(\mathbb{K}[C])=Frac(\mathbb{K}[x,y]/(f))$
Decimos que un mapeo racional entre dos curvas proyectivas
$latex \Phi: E \rightarrow F$
$latex P\mapsto [\phi_x(P):\phi_y(P):\phi_z(P)]$
Tal que $latex \phi_i \in \mathbb{K}(E)$
Decimos que el mapeo es regular en $latex P\in E(\bar{\mathbb{K}})$ (puntos de E con coordenadas en la cerradura del campo) si existe $latex g\in\bar{\mathbb{K}}(E)$ tal que $latex [g\phi_x(P):g\phi_y(P):g\phi_z(P)]$ está bien definida y no todos son coordenada 0 ($latex [0:0:0] \notin \mathbb{P}^2$).
Si un mapeo es regular en todos los puntos, decimos que es un morfismo , puede verse en el libro Advanced topics in the arithmetic of elliptic curves (Silverman) que si $latex E$ es suave proyectiva, entonces todo mapeo racional de $latex E$ a una curva proyectiva $latex F$ es un morfismo.
Tambien decimos que un isomorfismo entre curvas elípticas es una isogenia invertible.
Como ejemplos que pueden trabajar en casa, consideren los mapeos sobre una curva $latex E$ sobre el campo $latex \mathbb{F_q}$ con $latex q=p^n$
$latex P\mapsto 2P$
Pueden demostrar que eso realmente es una isogenia
También
$latex \pi:E \rightarrow E$
$latex [x:y,z] \mapsto [x^q:y^q:z^q]$
Donde este mapeo es el endomorfismo de Frobenius y tenemos que
$latex \hat{\pi}:\mathbb{F}_q \rightarrow \mathbb{F}_q$
$latex x\mapsto x^p$
Este mapeo es muy importante , ya que es un automorfismo, y tenemos que
$latex \pi(\mathbb{F}_q)$ deja fijos a los elementos $latex \mathbb{F}_p$
Ahora queremos representar explícitamente las isogenias entre curvas elípticas.
Lema: Si $latex E$ y $latex F$ son curvas elípticas sobre $latex \mathbb{K}$ en su forma estándar de Weierstrass (como en los ejemplos) y si $latex \alpha$ es una isogenia no trivial, entonces tiene la siguiente forma:
$latex \alpha(x,y)=\Big( \frac{u(x)}{v(x)} , \frac{s(x)}{t(x)}y \Big )$
donde
$latex u,v,s,t \in \bar{\mathbb{K}}[x]$
y las fracciones están reducidas (numerador y cocientes son primos relativos)
Esto es fácil demotrarlo, te dejo los hints porque es mucha talacha para que tú lo hagas.
Considera lo que ya sabemos, supón que $latex \alpha$ está definido por el mapeo racional $latex [\alpha_x:\alpha_y:\alpha_z]$, y considera para todo punto afín
$latex [x:y:1] \in E(\bar{\mathbb{K}})$
$latex \alpha(x,y)=\Big ( r_1(x,y), r_2(x,y) \Big )$ donde $latex r_1(x,y)=\alpha_x(x,y,1)/\alpha_z(x,y,1)$ y $latex r_2(x,y)=\alpha_y(x,y,1)/\alpha_z(x,y,1)$
utilizando la relación de $latex E$ que ya conoces entre $latex x,y$ que es $latex y^2=x^3+ax+b$ elimina los factores $latex y^n$ y reescribe $latex r_1(x,y)=\frac{p_1(x)+p_2(x)y}{p_3(x)+p_4(x)y}$, multiplica el numerador y denominador por $latex p_3(x)-p_4(x)y$ y vuelve a reducir los $latex y^n$
Eso te dara otra versión de $latex \alpha$ que también tiene $latex y$, pero considera la simetría de la curva y el inverso de los puntos... sabes que $latex \alpha(x,-y)=-\alpha(x,y)$ por lo que deben haber cosas que se hagan 0, el argumento en $latex \alpha_y$ es similar.
El grado de una isogenia se define bajo esta representación tan cómoda como $latex \partial(\alpha):=max\lbrace u,v\rbrace$, y decimos que la isogenia $latex \alpha$ es separable si la derivada de $latex \frac{u}{v}$ NO es la función 0
El grado jugara un papel importante para despues definir otras cosas y jugar con la funcion zeta elíptica y el teorema de Hasse.
Corolario-Definición
Si $latex \alpha(x,y)$ es una isogenia como en el lema pasado, $latex v,t$ tienen las mismas raíces, y justamente estas raíces corresponden al kernel de $latex \alpha$
Teorema-Definición: Sea $latex \alpha: E\rightarrow F$ una isogenia con $latex \partial(\alpha)=n$ separable, entonces existe una única isogenia $latex \hat\alpha:F\rightarrow E$ tal que $latex \hat\alpha \circ \alpha = [n]$ , y le llamamos isogenia dual de $latex \mathbb{\alpha}$
Cosas que se pueden demostrar es que si $latex \alpha:E\rightarrow F$ y $latex \beta:E\rightarrow F$ entonces $latex \hat{\alpha+\beta}=\hat\alpha+\hat\beta$ y que $latex \alpha + \hat\alpha = 1 + \partial(\alpha)-\partial(1-\alpha)$, lo cual nos lleva a que definamos la traza de un endomorfismo
$latex tr(\alpha)=tr(\hat\alpha)=\alpha+\hat\alpha$
Nota que tenemos que $latex \alpha\cdot \hat\alpha=[\partial(\alpha)]$ (en la misma curva elíptica) por lo que $latex \partial(\hat\alpha) = \partial(\alpha)$
Lo anterior nos lleva a un teorema importante que nos relaciona con un polinomio cuadrático cada endomorfismo.
Teorema:
Sea $latex \alpha \in End_\mathbb{K}(E)$ , entonces $latex \alpha$ y $latex \hat\alpha$ son raíces del polinomio característico
$latex \xi(\lambda)=\lambda^2 - (tr\alpha)\lambda + \partial(\alpha) = 0$
Esto es muy fácil de probar
$latex \alpha^2 -(tr\alpha)\alpha+\partial(\alpha)=\alpha^2 - (\alpha+\hat\alpha)\alpha + \hat\alpha\alpha = 0$ lo mismo para $latex \hat\alpha$.
Ahora... como última parte de esta sección, consideremos el campo de caracteristica p y vamos a restringir los endomorfismos al subgrupo de torsión de la curva elíptica, es decir, sólo los evaluaremos en elementos de $latex E[n]$
y si $latex \alpha \in latex End(E)_\mathbb{K}$ a la restricción de $latex \alpha\mid_{E[n]}$ la redefiniremos como:
$latex \alpha_n$
Esta $latex \alpha_n$ es un endomorfismo del subgrupo abeliano $latex E[n]$ ya que $latex \alpha$ es un morfismo y manda puntos de torsión a puntos de torsión y como vimos anteriormente:
$latex E[n] \cong \mathbb{Z}/n\mathbb{Z} \oplus \mathbb{Z}/n\mathbb{Z}$, considera una base para $latex E[n]$ , llámale $latex (P_1,P_2)$
entonces podemos representar en forma de matriz a $latex \alpha_n=\begin{pmatrix}a&b\\c&d\end{pmatrix}$ donde $latex a,b,c,d \in \mathbb{Z}/n\mathbb{Z}$ y $latex \alpha(P_1)=aP_1\oplus cP_2$ y $latex \alpha(P_2)=bP_1+dP_2$ , la representación de la matriz depende de la base, pero la traza $latex tr \alpha_n$ y $latex det \alpha_n$ no.
Lo que nos deja con este teorema que es MUY importante, ya que es la conexión más importante que hay entre los endomorfismos y las restricciónes a $latex E[n]$
Teorema:
Sea $latex \alpha \in End_\mathbb{K}(E)$ con $latex E$ elíptica sobre $latex \mathbb{K}$ y sea $latex n$ un número positivo primo relativo a la característica de $latex \mathbb{K}$
entonces:
$latex tr \alpha \equiv tr \alpha_n \bmod n$ y $latex \partial(\alpha) \equiv det(\alpha_n) mod n$
Con esto ya estamos bien equipados.
j-Invariante
Ahora, ya que sabemos que todas las curvas de género 1 son elípticas, hay una manera de clasificarlas muy eficientemente, consideremos $latex \mathcal{E}$ como el espacio de todas las curvas elípticas sobre $latex \mathbb{K}$ , entonces existe una función
$latex j: \mathcal{E} \rightarrow \mathbb{K}$
Llamada j-invariante que cumple que:
$latex j(E)=j(F)\Leftrightarrow E \cong F$ sobre $latex \bar{\mathbb{K}}$
Se ha demostrado que la función $latex j$ es suprayectiva, por lo que $latex \mathbb{K}$ es el espacio modular de dimensión 1y tenemos que las fibras $latex j^{-1}(x)$ son clases de $latex \bar{\mathbb{K}}$-isomorfismos de curvas elípticas definidas sobre $latex \mathbb{K}$
Las curvas elípticas que generalmente usamos en criptografía son de la forma
$latex E:=y^2 - x^3 - px -q $
Por lo que podemos expresar el j-invariante de manera más reducida como:
$latex j(E)=1728 \frac{4p^3}{4p^3+27q^2}$
Torsiones cuadráticas de curvas elípticas
Aquí no voy a entrar tanto en detalle porque tengo poca experiencia pero es importante.
Imagina que tenemos las curvas $latex E$ y $latex F$ definids sobre $latex \mathbb{K}$ tal que existe un isomorfismo $latex E\rightarrow F$ sobre $latex \bar{\mathbb{K}}$ pero no sobre $latex \mathbb{K}$ , decimos en este caso que $latex E$ y $latex F$ son torsiones.
Ejemplo:
Considera las curvas $latex E:y^2=x^3+11664$ y $latex F:y^2=x^3+1$
Ambas suaves y lindas definidas sobre $latex \mathbb{Q}$ , estas curvas NO pueden ser isomorfas sobre $latex \mathbb{Q}$ ya que $latex F$ tiene un punto de orden 2 $latex (-1,0)$ y $latex E$ no tienen ningun punto de orden 2 (el punto de orden 2 en este caso como son simetricas son el eje x , tendria que se un punto de weierstrass, lo cual implica que x=0 por lo que $latex y\notin \mathbb{Q}$)
Pero ahora considera las curvas en la extensión cuadrática $latex \mathbb{Q}(\sqrt{2})$,
aquí podemos definir el isomorfismo:
$latex \Psi: E \rightarrow F$
$latex (x,y) \mapsto (2^3 3^6 \sqrt{2}\cdot x , 2^2 3^3\cdot y)$
Por lo que decimos que $latex E$ y $latex F$ son twists cuadráticos.
Por lo anterior... deberían de tener el mismo j-invariante, el cual es claramente 0, por lo que todas las curvas existentes con j-invariante 0 , serán isomorfas a estas que ejemplificamos en alguna extensión del campo en el que estén trabajando.
Subgrupo de torsión y endomorfismo de una curva elíptica
Sabemos que el mapeo que manda a multiplicar por $latex [n]$ los puntos de una curva $latex E$ es un morfismo, al kernel de este mapeo le llamamos subgrupo de torsión y lo denotamos como $latex E[n]$ , y tenemos el siguiente teorema cuando $latex K$ tiene caracteristica p
$latex E[n]\cong \mathbb{Z}/n\mathbb{Z}\oplus \mathbb{Z}/n\mathbb{Z}$ si $latex p=0$ o $latex p\ndiv n$
o
$latex E[n]\cong \mathbb{Z}/n\mathbb{Z}$ o $latex \lbrace 0\rbrace 0$ si $latex p>0$ y $latex n=p^m$
Qué corolario de este teorema pueden deducir de $latex E[p]$ ?
Pero lo que diremos es que en un campo de caracteristica positiva , si $latex E[p]\cong \mathbb{Z}/p\mathbb{Z}$ le llamamos a la curva $latex E$ ordinaria, y si es $latex E[p]\cong \lbrace 0\rbrace $ supersingular.
Ahora, aquí el anillo de Endomorfismos de la curva $latex E$ los denotamos como $latex End_\mathbb{K}(E)$
y tenemos que las isogenias $latex \alpha:E\rightarrow E$ son endomorfismos, y forman un anillo
bajo las siguientes operaciones
$latex \alpha,\beta \in End_\mathbb{K}(E)$
$latex (\alpha + \beta)(P)=\alpha(P)\oplus\beta(P)$
$latex (\alpha\cdot \beta)(P)=(\alpha \circ \beta)(P)$
Tenemos que ahora con esto podemos construir una infinidad de elementos ya que $latex [n] \ in End_\mathbb{K}(E)$
esto debería ser para ustedes pero lo pongo.
$latex (\alpha\cdot [n])(P)=\alpha(nP)=\alpha(\bigoplus_{i=1}^n {P}) = \bigoplus_{i=1}^n { \alpha(P) }=n\alpha(P)=([n]\cdot \alpha(P)$
Esto nos dice que $latex \mathbb{Z}$ es un subanillo de $latex End_\mathbb{K}(E)$ , lo puedes observar viendo como se comporta la composición y la suma de $latex [n]$ y $latex [m]$ , verás que forman un anillo esos endomorfismos y son isomorfos a $latex \mathbb{Z}$
Este anillo de endomorfismos no sólo tiene a $latex \mathbb{Z}$ , como vimos, también está el endomorfismo $latex \pi$ de Frobenius (con $latex \mathbb{K}$ de caracteristica p>0 como el caso de criptografía) y pues por lo tanto todas las composiciones y sumas de éste con los isomorfos a $latex \mathbb{Z}$ cuando la curva $latex E$ es supersingular, este anillo de endomorfismos se comporta como un álgebra de cuaternios y no es conmutativo.
Espero les haya interesado, cualquier duda o corrección háganmela saber
Eduardo Ruíz Duarte (beck)
Twitter: @toorandom
No comments:
Post a Comment