Curva de Montgomery

Tipo de curva elíptica

En matemáticas , la curva de Montgomery es una forma de curva elíptica introducida por Peter L. Montgomery en 1987, ^[1] diferente de la forma habitual de Weierstrass . Se utiliza para ciertos cálculos y, en particular, en diferentes aplicaciones de criptografía .

Definición

Una curva de Montgomery de ecuación ${\textstyle {\frac {1}{4}}y^{2}=x^{3}+{\frac {5}{2}}x^{2}+x}$

Una curva de Montgomery sobre un campo K se define mediante la ecuación

${\displaystyle M_{A,B}:By^{2}=x^{3}+Ax^{2}+x}$

para cierto A , B ∈ K y con B ( A ² − 4) ≠ 0 .

Generalmente esta curva se considera sobre un cuerpo finito K (por ejemplo, sobre un cuerpo finito de q elementos , K = F _q ) con característica distinta de 2 y con A ≠ ±2 y B ≠ 0 , pero también se consideran sobre los racionales con las mismas restricciones para A y B .

Aritmética de Montgomery

Es posible realizar algunas "operaciones" entre los puntos de una curva elíptica: "sumar" dos puntos consiste en encontrar un tercero tal que ; "duplicar" un punto consiste en calcular (Para más información sobre operaciones ver La ley de grupo ) y más abajo. ${\displaystyle P,Q}$ ${\displaystyle R}$ ${\displaystyle R=P+Q}$ ${\displaystyle [2]P=P+P}$

Un punto en la curva elíptica en la forma de Montgomery se puede representar en coordenadas de Montgomery , donde son coordenadas proyectivas y para . ${\displaystyle P=(x,y)}$ ${\displaystyle By^{2}=x^{3}+Ax^{2}+x}$ ${\displaystyle P=(X:Z)}$ ${\displaystyle P=(X:Z)}$ ${\displaystyle x=X/Z}$ ${\displaystyle Z\neq 0}$

Nótese que este tipo de representación para un punto pierde información: de hecho, en este caso, no hay distinción entre los puntos afines y porque ambos están dados por el punto . Sin embargo, con esta representación es posible obtener múltiplos de puntos, es decir, dado , calcular . ${\displaystyle (x,y)}$ ${\displaystyle (x,-y)}$ ${\displaystyle (X:Z)}$ ${\displaystyle P=(X:Z)}$ ${\displaystyle [n]P=(X_{n}:Z_{n})}$

Ahora, considerando los dos puntos y : su suma está dada por el punto cuyas coordenadas son: ${\displaystyle P_{n}=[n]P=(X_{n}:Z_{n})}$ ${\displaystyle P_{m}=[m]P=(X_{m}:Z_{m})}$ ${\displaystyle P_{m+n}=P_{m}+P_{n}=(X_{m+n}:Z_{m+n})}$

${\displaystyle X_{m+n}=Z_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})+(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}$

${\displaystyle Z_{m+n}=X_{m-n}((X_{m}-Z_{m})(X_{n}+Z_{n})-(X_{m}+Z_{m})(X_{n}-Z_{n}))^{2}}$

Si , entonces la operación se convierte en una "duplicación"; las coordenadas de están dadas por las siguientes ecuaciones: ${\displaystyle m=n}$ ${\displaystyle [2]P_{n}=P_{n}+P_{n}=P_{2n}=(X_{2n}:Z_{2n})}$

${\displaystyle 4X_{n}Z_{n}=(X_{n}+Z_{n})^{2}-(X_{n}-Z_{n})^{2}}$

${\displaystyle X_{2n}=(X_{n}+Z_{n})^{2}(X_{n}-Z_{n})^{2}}$

${\displaystyle Z_{2n}=(4X_{n}Z_{n})((X_{n}-Z_{n})^{2}+((A+2)/4)(4X_{n}Z_{n}))}$

La primera operación considerada arriba ( suma ) tiene un coste temporal de 3 M +2 S , donde M denota la multiplicación entre dos elementos generales del campo en el que está definida la curva elíptica, mientras que S denota el cuadrado de un elemento general del campo.

La segunda operación (duplicación) tiene un costo de tiempo de 2 M  + 2 S  + 1 D , donde D denota la multiplicación de un elemento general por una constante ; observe que la constante es , por lo que puede elegirse para tener una  D pequeña . ${\displaystyle (A+2)/4}$ ${\displaystyle A}$

Algoritmo y ejemplo

El siguiente algoritmo representa la duplicación de un punto en una curva elíptica en la forma de Montgomery. ${\displaystyle P_{1}=(X_{1}:Z_{1})}$

Se supone que . El costo de esta implementación es 1M + 2S + 1*A + 3add + 1*4. Aquí M denota las multiplicaciones requeridas, S indica los cuadrados y a se refiere a la multiplicación por A. ${\displaystyle Z_{1}=1}$

${\displaystyle XX_{1}=X_{1}^{2}\,}$

${\displaystyle X_{2}=(XX_{1}-1)^{2}\,}$

${\displaystyle Z_{2}=4X_{1}(XX_{1}+aX_{1}+1)\,}$

Ejemplo

Sea un punto de la curva . En coordenadas , con , . ${\displaystyle P_{1}=(2,{\sqrt {3}})}$ ${\displaystyle 2y^{2}=x^{3}-x^{2}+x}$ ${\displaystyle (X_{1}:Z_{1})}$ ${\displaystyle x_{1}=X_{1}/Z_{1}}$ ${\displaystyle P_{1}=(2:1)}$

Entonces:

${\displaystyle XX_{1}=X_{1}^{2}=4\,}$

${\displaystyle X_{2}=(XX_{1}-1)^{2}=9\,}$

${\displaystyle Z_{2}=4X_{1}(XX_{1}+AX_{1}+1)=24\,}$

El resultado es el punto tal que . ${\displaystyle P_{2}=(X_{2}:Z_{2})=(9:24)}$ ${\displaystyle P_{2}=2P_{1}}$

Suma

Dados dos puntos , sobre la curva de Montgomery en coordenadas afines, el punto representa, geométricamente , el tercer punto de intersección entre y la recta que pasa por y . Es posible hallar las coordenadas de , de la siguiente manera: ${\displaystyle P_{1}=(x_{1},y_{1})}$ ${\displaystyle P_{2}=(x_{2},y_{2})}$ ${\displaystyle M_{A,B}}$ ${\displaystyle P_{3}=P_{1}+P_{2}}$ ${\displaystyle M_{A,B}}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle (x_{3},y_{3})}$ ${\displaystyle P_{3}}$

1) considérese una recta genérica en el plano afín y déjese pasar por y (imponga la condición), de esta manera, se obtiene y ; ${\displaystyle ~y=lx+m}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle l={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}$ ${\displaystyle m=y_{1}-\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)x_{1}}$

2) intersectar la recta con la curva , sustituyendo la variable en la ecuación de la curva por ; se obtiene la siguiente ecuación de tercer grado : ${\displaystyle M_{A,B}}$ ${\displaystyle ~y}$ ${\displaystyle ~y=lx+m}$

${\displaystyle x^{3}+(A-Bl^{2})x^{2}+(1-2Blm)x-Bm^{2}=0.}$

Como se ha observado anteriormente, esta ecuación tiene tres soluciones que corresponden a las coordenadas de , y . En particular, esta ecuación puede reescribirse como: ${\displaystyle ~x}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle P_{3}}$

${\displaystyle (x-x_{1})(x-x_{2})(x-x_{3})=0}$

3) Comparando los coeficientes de las dos ecuaciones idénticas dadas anteriormente, en particular los coeficientes de los términos de segundo grado, se obtiene:

${\displaystyle -x_{1}-x_{2}-x_{3}=A-Bl^{2}}$.

Por lo tanto, se puede escribir en términos de , , , , como: ${\displaystyle x_{3}}$ ${\displaystyle x_{1}}$ ${\displaystyle y_{1}}$ ${\displaystyle x_{2}}$ ${\displaystyle y_{2}}$

${\displaystyle x_{3}=B\left({\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}\right)^{2}-A-x_{1}-x_{2}.}$

4) Para hallar la coordenada del punto es suficiente sustituir el valor en la recta . Nótese que esto no dará el punto directamente. En efecto, con este método se hallan las coordenadas del punto tal que , pero si se necesita el punto resultante de la suma entre y , entonces es necesario observar que: si y sólo si . Así pues, dado el punto , es necesario hallar , pero esto se puede hacer fácilmente cambiando el signo por la coordenada de . En otras palabras, será necesario cambiar el signo de la coordenada obtenida sustituyendo el valor en la ecuación de la recta. ${\displaystyle ~y}$ ${\displaystyle P_{3}}$ ${\displaystyle x_{3}}$ ${\displaystyle ~y=lx+m}$ ${\displaystyle P_{3}}$ ${\displaystyle ~R}$ ${\displaystyle R+P_{1}+P_{2}=P_{\infty }}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{2}}$ ${\displaystyle R+P_{1}+P_{2}=P_{\infty }}$ ${\displaystyle -R=P_{1}+P_{2}}$ ${\displaystyle ~R}$ ${\displaystyle ~-R}$ ${\displaystyle ~y}$ ${\displaystyle ~R}$ ${\displaystyle ~y}$ ${\displaystyle x_{3}}$

Resumiendo, las coordenadas del punto , son: ${\displaystyle P_{3}=(x_{3},y_{3})}$ ${\displaystyle P_{3}=P_{1}+P_{2}}$

${\displaystyle x_{3}={\frac {B(y_{2}-y_{1})^{2}}{(x_{2}-x_{1})^{2}}}-A-x_{1}-x_{2}}$

${\displaystyle y_{3}={\frac {(2x_{1}+x_{2}+A)(y_{2}-y_{1})}{x_{2}-x_{1}}}-{\frac {B(y_{2}-y_{1})^{3}}{(x_{2}-x_{1})^{3}}}-y_{1}}$

Duplicación

Dado un punto en la curva de Montgomery , el punto representa geométricamente el tercer punto de intersección entre la curva y la línea tangente a ; por lo tanto, para encontrar las coordenadas del punto es suficiente seguir el mismo método dado en la fórmula de la adición; sin embargo, en este caso, la línea y  =  lx  +  m tiene que ser tangente a la curva en , por lo que, si con ${\displaystyle P_{1}}$ ${\displaystyle M_{A,B}}$ ${\displaystyle [2]P_{1}}$ ${\displaystyle P_{1}}$ ${\displaystyle P_{3}=2P_{1}}$ ${\displaystyle P_{1}}$ ${\displaystyle M_{A,B}:f(x,y)=0}$

${\displaystyle f(x,y)=x^{3}+Ax^{2}+x-By^{2},}$

entonces el valor de l , que representa la pendiente de la recta, viene dado por:

${\displaystyle l=-\left.{\frac {\partial f}{\partial x}}\right/{\frac {\partial f}{\partial y}}}$

por el teorema de la función implícita .

Entonces las coordenadas del punto , son: ${\displaystyle l={\frac {3x_{1}^{2}+2Ax_{1}+1}{2By_{1}}}}$ ${\displaystyle P_{3}}$ ${\displaystyle P_{3}=2P_{1}}$

${\displaystyle {\begin{aligned}x_{3}&=Bl^{2}-A-x_{1}-x_{1}={\frac {B(3x_{1}^{2}+2Ax_{1}+1)^{2}}{(2By_{1})^{2}}}-A-x_{1}-x_{1}\\y_{3}&=(2x_{1}+x_{1}+A)l-Bl^{3}-y_{1}\\&={\frac {(2x_{1}+x_{1}+A)(3{x_{1}}^{2}+2Ax_{1}+1)}{2By_{1}}}-{\frac {B(3{x_{1}}^{2}+2Ax_{1}+1)^{3}}{(2By_{1})^{3}}}-y_{1}.\end{aligned}}}$

Equivalencia con curvas de Edwards torcidas

Sea un campo con característica distinta de 2. ${\displaystyle K}$

Sea una curva elíptica en forma de Montgomery: ${\displaystyle M_{A,B}}$

${\displaystyle M_{A,B}:Bv^{2}=u^{3}+Au^{2}+u}$

con , ${\displaystyle A\in K\smallsetminus \{-2,2\}}$ ${\displaystyle B\in K\smallsetminus \{0\}}$

y sea una curva elíptica en la forma de Edwards torcida: ${\displaystyle E_{a,d}}$

${\displaystyle E_{a,d}\ :\ ax^{2}+y^{2}=1+dx^{2}y^{2},\,}$

con ${\displaystyle a,d\in K\smallsetminus \{0\},\quad a\neq d.}$

El siguiente teorema muestra la equivalencia biracional entre las curvas de Montgomery y la curva de Edwards torcida : ^[2]

Teorema (i) Toda curva de Edwards torcida es biracionalmente equivalente a una curva de Montgomery sobre . En particular, la curva de Edwards torcida es biracionalmente equivalente a la curva de Montgomery donde , y . ${\displaystyle K}$ ${\displaystyle E_{a,d}}$ ${\displaystyle M_{A,B}}$ ${\displaystyle A={\frac {2(a+d)}{a-d}}}$ ${\displaystyle B={\frac {4}{a-d}}}$

El mapa :

${\displaystyle \psi \,:\,E_{a,d}\rightarrow M_{A,B}}$

${\displaystyle (x,y)\mapsto (u,v)=\left({\frac {1+y}{1-y}},{\frac {1+y}{(1-y)x}}\right)}$

es una equivalencia biracional de a , con inversa: ${\displaystyle E_{a,d}}$ ${\displaystyle M_{A,B}}$

${\displaystyle \psi ^{-1}}$: ${\displaystyle M_{A,B}\rightarrow E_{a,d}}$

${\displaystyle (u,v)\mapsto (x,y)=\left({\frac {u}{v}},{\frac {u-1}{u+1}}\right),a={\frac {A+2}{B}},d={\frac {A-2}{B}}}$

Obsérvese que esta equivalencia entre las dos curvas no es válida en todas partes: de hecho, el mapa no está definido en los puntos o de . ${\displaystyle \psi }$ ${\displaystyle v=0}$ ${\displaystyle u+1=0}$ ${\displaystyle M_{A,B}}$

Equivalencia con curvas de Weierstrass

Cualquier curva elíptica puede escribirse en forma de Weierstrass. En particular, la curva elíptica en forma de Montgomery

${\displaystyle M_{A,B}}$: ${\displaystyle By^{2}=x^{3}+Ax^{2}+x,}$

se puede transformar de la siguiente manera: dividir cada término de la ecuación por , y sustituir las variables x e y , por y respectivamente, para obtener la ecuación ${\displaystyle M_{A,B}}$ ${\displaystyle B^{3}}$ ${\displaystyle u={\frac {x}{B}}}$ ${\displaystyle v={\frac {y}{B}}}$

${\displaystyle v^{2}=u^{3}+{\frac {A}{B}}u^{2}+{\frac {1}{B^{2}}}u.}$

Para obtener una forma corta de Weierstrass desde aquí, es suficiente reemplazar u con la variable : ${\displaystyle t-{\frac {A}{3B}}}$

${\displaystyle v^{2}=\left(t-{\frac {A}{3B}}\right)^{3}+{\frac {A}{B}}\left(t-{\frac {A}{3B}}\right)^{2}+{\frac {1}{B^{2}}}\left(t-{\frac {A}{3B}}\right);}$

Finalmente, esto da la ecuación:

${\displaystyle v^{2}=t^{3}+\left({\frac {3-A^{2}}{3B^{2}}}\right)t+\left({\frac {2A^{3}-9A}{27B^{3}}}\right).}$

Por lo tanto, el mapeo se da como

${\displaystyle \psi }$: ${\displaystyle M_{A,B}\rightarrow E_{a,b}}$

${\displaystyle (x,y)\mapsto (t,v)=\left({\frac {x}{B}}+{\frac {A}{3B}},{\frac {y}{B}}\right),a={\frac {3-A^{2}}{3B^{2}}},b={\frac {2A^{3}-9A}{27B^{3}}}}$

Por el contrario, una curva elíptica sobre el campo base en forma de Weierstrass ${\displaystyle \mathbb {F} }$

${\displaystyle E_{a,b}}$: ${\displaystyle v^{2}=t^{3}+at+b}$

se puede convertir a la forma Montgomery si y sólo si tiene orden divisible por cuatro y satisface las siguientes condiciones: ^[3] ${\displaystyle E_{a,b}}$

1. ${\displaystyle z^{3}+az+b=0}$tiene al menos una raíz ; y ${\displaystyle \alpha \in \mathbb {F} }$
2. ${\displaystyle 3\alpha ^{2}+a}$es un residuo cuadrático en . ${\displaystyle \mathbb {F} }$

Cuando se cumplen estas condiciones, entonces tenemos la función ${\displaystyle s=({\sqrt {3\alpha ^{2}+a}})^{-1}}$

${\displaystyle \psi ^{-1}}$: ${\displaystyle E_{a,b}\rightarrow M_{A,B}}$

${\displaystyle (t,v)\mapsto (x,y)=\left(s(t-\alpha ),sv\right),A=3\alpha s,B=s}$.

Véase también

• Curva25519
• Tabla de costos de operaciones en curvas elípticas : información sobre el tiempo de ejecución requerido en un caso específico

Notas

1. Peter L. Montgomery (1987). "Aceleración de los métodos de factorización de Pollard y de curva elíptica". Matemáticas de la computación . 48 (177): 243–264. doi : 10.2307/2007888 . JSTOR  2007888.
2. Daniel J. Bernstein , Peter Birkner, Marc Joye, Tanja Lange y Christiane Peters (2008). "Curvas retorcidas de Edwards". Progresos en criptología - AFRICACRYPT 2008 . Apuntes de conferencias sobre informática. vol. 5023. Springer-Verlag Berlín Heidelberg. págs. 389–405. doi :10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68159-5.{{cite book}}: CS1 maint: multiple names: authors list (link)
3. Katsuyuki Okeya, Hiroyuki Kurumatani y Kouichi Sakurai (2000). Curvas elípticas con la forma Montgomery y sus aplicaciones criptográficas . Criptografía de clave pública (PKC2000). doi : 10.1007/978-3-540-46588-1_17 .{{cite conference}}: CS1 maint: multiple names: authors list (link)

Referencias

• Peter L. Montgomery (1987). "Aceleración de los métodos de factorización de Pollard y de curva elíptica". Matemáticas de la computación . 48 (177): 243–264. doi : 10.2307/2007888 . JSTOR  2007888.
• Daniel J. Bernstein , Peter Birkner, Marc Joye, Tanja Lange y Christiane Peters (2008). "Curvas retorcidas de Edwards". Progresos en criptología - AFRICACRYPT 2008 . Apuntes de conferencias sobre informática. vol. 5023. Springer-Verlag Berlín Heidelberg. págs. 389–405. doi :10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68159-5.{{cite book}}: CS1 maint: multiple names: authors list (link)
• Wouter Castryck; Steven Galbraith; Reza Rezaeian Farashahi (2008). "Aritmética eficiente en curvas elípticas utilizando una representación mixta de Edwards-Montgomery" (PDF) . {{cite journal}}: Requiere citar revista |journal=( ayuda )

Enlaces externos

• Curvas del género 1 sobre campos de características grandes