Curva de Edwards

Curvas de Edwards de la ecuación x ²  +  y ²  = 1 +  d  · x ² · y ² sobre los números reales para d  = −300 (rojo), d  = − √ 8 (amarillo) y d  = 0,9 (azul)

En matemáticas , las curvas de Edwards son una familia de curvas elípticas estudiadas por Harold Edwards en 2007. El concepto de curvas elípticas sobre cuerpos finitos se utiliza ampliamente en criptografía de curvas elípticas . Daniel J. Bernstein y Tanja Lange desarrollaron aplicaciones de las curvas de Edwards a la criptografía : señalaron varias ventajas de la forma de Edwards en comparación con la forma de Weierstrass más conocida ^[1] .

Definición

La ecuación de una curva de Edwards sobre un campo K que no tiene característica 2 es:

${\displaystyle x^{2}+y^{2}=1+d\ x^{2}y^{2}\,}$

para algún escalar . También la siguiente forma con parámetros c y d se denomina curva de Edwards: ${\displaystyle d\in K\setminus \{0,1\}}$

${\displaystyle x^{2}+y^{2}=c^{2}(1+d\ x^{2}y^{2})\,}$

donde c ,  d  ∈  K con cd (1 −  c ⁴ · d ) ≠ 0.

Toda curva de Edwards es birracionalmente equivalente a una curva elíptica en forma de Montgomery y, por lo tanto, admite una ley de grupo algebraico una vez que se elige un punto para que sirva como elemento neutro. Si K es finito, entonces una fracción considerable de todas las curvas elípticas sobre K se pueden escribir como curvas de Edwards. A menudo, las curvas elípticas en forma de Edwards se definen con c = 1, sin pérdida de generalidad. En las siguientes secciones, se supone que c = 1.

La ley de grupos

(Véase también la ley del grupo de curvas de Weierstrass )

Toda curva de Edwards sobre el cuerpo K con característica distinta de 2 con es biracionalmente equivalente a una curva elíptica sobre el mismo cuerpo: , donde y el punto se mapea al infinito O . Esta aplicación biracional induce un grupo en cualquier curva de Edwards. ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$ ${\displaystyle d\neq 1}$ ${\displaystyle (1/e)v^{2}=u^{3}+(4/e-2)u^{2}+u}$ ${\displaystyle e=1-d,u={\frac {1+y}{1-y}},v={\frac {2(1+y)}{x(1-y)}}}$ ${\displaystyle P=(0,1)}$

Ley de adición de Edwards

En cualquier curva elíptica, la suma de dos puntos se da mediante una expresión racional de las coordenadas de los puntos, aunque en general puede ser necesario utilizar varias fórmulas para cubrir todos los pares posibles. Para la curva de Edwards, tomando como elemento neutro el punto (0, 1), la suma de los puntos y se da mediante la fórmula ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (x_{2},y_{2})}$

${\displaystyle (x_{1},y_{1})+(x_{2},y_{2})=\left({\frac {x_{1}y_{2}+x_{2}y_{1}}{1+dx_{1}x_{2}y_{1}y_{2}}},{\frac {y_{1}y_{2}-x_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}\right)\,}$

El opuesto de cualquier punto es . El punto tiene orden 2 y los puntos tienen orden 4. En particular, una curva de Edwards siempre tiene un punto de orden 4 con coordenadas en K . ${\displaystyle (x,y)}$ ${\displaystyle (-x,y)}$ ${\displaystyle (0,-1)}$ ${\displaystyle (\pm 1,0)}$

Si d no es un cuadrado en K y , entonces no hay puntos excepcionales: los denominadores y son siempre distintos de cero. Por lo tanto, la ley de adición de Edwards está completa cuando d no es un cuadrado en K . Esto significa que las fórmulas funcionan para todos los pares de puntos de entrada en la curva de Edwards sin excepciones para la duplicación, ninguna excepción para el elemento neutro, ninguna excepción para los negativos, etc. ^[2] En otras palabras, está definida para todos los pares de puntos de entrada en la curva de Edwards sobre K y el resultado da la suma de los puntos de entrada. ${\displaystyle \{(x_{1},y_{1}),(x_{2},y_{2})\}\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}^{2}}$ ${\displaystyle 1+dx_{1}x_{2}y_{1}y_{2}}$ ${\displaystyle 1-dx_{1}x_{2}y_{1}y_{2}}$

Si d es un cuadrado en K , entonces la misma operación puede tener puntos excepcionales, es decir, puede haber pares de puntos tales que uno de los denominadores se convierta en cero: o bien . ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}}$ ${\displaystyle 1+dx_{1}x_{2}y_{1}y_{2}=0}$ ${\displaystyle 1-dx_{1}x_{2}y_{1}y_{2}=0}$

Una de las características atractivas de la ley de adición de Edwards es que está fuertemente unificada , es decir, también se puede utilizar para duplicar un punto, lo que simplifica la protección contra ataques de canal lateral . La fórmula de adición anterior es más rápida que otras fórmulas unificadas y tiene la fuerte propiedad de completitud ^[2].

Ejemplo de ley de adición :

Considere la curva elíptica en la forma de Edwards con d = 2

${\displaystyle {\displaystyle }x^{2}+y^{2}=1+2x^{2}y^{2}}$

y el punto sobre él. Es posible demostrar que la suma de P ₁ con el elemento neutro (0,1) da de nuevo P ₁ . En efecto, utilizando la fórmula dada anteriormente, las coordenadas del punto dado por esta suma son: ${\displaystyle P_{1}=(1,0)}$

${\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1+2x_{1}x_{2}y_{1}y_{2}}}=1}$

${\displaystyle y_{3}={\frac {y_{1}y_{2}-x_{1}x_{2}}{1-2x_{1}x_{2}y_{1}y_{2}}}=0}$

Un análogo en el círculo

Grupo de reloj

Para comprender mejor el concepto de “suma” de puntos en una curva, un buen ejemplo lo da el grupo circular clásico:

toma el circulo de radio 1

${\displaystyle {\displaystyle }x^{2}+y^{2}=1}$

y consideremos dos puntos P ₁ =(x ₁ ,y ₁ ), P ₂ =(x ₂ ,y ₂ ) sobre él. Sean α ₁ y α ₂ los ángulos tales que:

${\displaystyle {\displaystyle }P_{1}=(x_{1},y_{1})=(\sin {\alpha _{1}},\cos {\alpha _{1}})}$

${\displaystyle {\displaystyle }P_{2}=(x_{2},y_{2})=(\sin {\alpha _{2}},\cos {\alpha _{2}})}$

La suma de P ₁ y P ₂ viene dada, pues, por la suma de "sus ángulos". Es decir, el punto P ₃ =P ₁ +P ₂ es un punto de la circunferencia con coordenadas (x ₃ ,y ₃ ), donde:

${\displaystyle {\displaystyle }x_{3}=\sin({\alpha }_{1}+{\alpha }_{2})=\sin {\alpha }_{1}\cos {\alpha }_{2}+\sin {\alpha }_{2}\cos {\alpha }_{1}=x_{1}y_{2}+x_{2}y_{1}}$

${\displaystyle {\displaystyle }y_{3}=\cos({\alpha }_{1}+{\alpha }_{2})=\cos {\alpha }_{1}\cos {\alpha }_{2}-\sin {\alpha }_{1}\sin {\alpha }_{2}=y_{1}y_{2}-x_{1}x_{2}.}$

De esta manera, la fórmula de adición de puntos en el círculo de radio 1 es:

${\displaystyle {\displaystyle }(x_{1},y_{1})+(x_{2},y_{2})=(x_{1}y_{2}+x_{2}y_{1},y_{1}y_{2}-x_{1}x_{2})}$.

Adición a las curvas de Edwards

Suma de dos puntos de la curva de Edwards con d = -30

Duplicar un punto en la curva de Edwards con d=-30

Los puntos de una curva elíptica forman un grupo abeliano: se pueden sumar puntos y tomar múltiplos enteros de un único punto. Cuando una curva elíptica se describe mediante una ecuación cúbica no singular, entonces la suma de dos puntos P y Q , denotada P  +  Q , está directamente relacionada con el tercer punto de intersección entre la curva y la línea que pasa por P y Q .

La aplicación biracional entre una curva de Edwards y la curva elíptica cúbica correspondiente convierte las líneas rectas en secciones cónicas ^[3] . En otras palabras, para las curvas de Edwards los tres puntos , y se encuentran en una hipérbola . ${\displaystyle Axy+Bx+Cy+D=0}$ ${\displaystyle P}$ ${\displaystyle Q}$ ${\displaystyle -(P+Q)}$

Dados dos puntos distintos de no identidad , los coeficientes de la forma cuadrática son (hasta escalares): ${\displaystyle P_{1}=(x_{1},y_{1}),P_{2}=(x_{2},y_{2}),P_{1}\neq P_{2}}$

${\displaystyle A=(x_{1}-x_{2})+(x_{1}y_{2}-x_{2}y_{1})}$,

${\displaystyle B=(x_{2}y_{2}-x_{1}y_{1})+y_{1}y_{2}(x_{2}-x_{1})}$,

${\displaystyle C=x_{1}x_{2}(y_{1}-y_{2}),D=C}$

En el caso de la duplicación de un punto, el punto inverso se encuentra en la cónica que toca la curva en el punto . Los coeficientes de la forma cuadrática que define la cónica son (hasta escalares ^{[ aclaración necesaria ]} ): ${\displaystyle P=(x,y)}$ ${\displaystyle -2P}$ ${\displaystyle P}$

${\displaystyle A=dx^{2}y-1}$,

${\displaystyle B=y-x^{2}}$,

${\displaystyle C=x(1-y),D=C}$

Coordenadas homogéneas proyectivas

En el contexto de la criptografía, se utilizan coordenadas homogéneas para evitar las inversiones de campo que aparecen en la fórmula afín. Para evitar las inversiones en las fórmulas de adición originales de Edwards, la ecuación de la curva se puede escribir en coordenadas proyectivas como:

${\displaystyle (X^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}$.

Un punto proyectivo corresponde al punto afín en la curva de Edwards. ${\displaystyle (X:Y:Z)}$ ${\displaystyle (X/Z:Y/Z)}$

El elemento identidad está representado por . El inverso de es . ${\displaystyle (0:1:1)}$ ${\displaystyle (X:Y:Z)}$ ${\displaystyle (-X:Y:Z)}$

La fórmula de adición en coordenadas homogéneas viene dada por: ${\displaystyle (X_{1}:Y_{1}:Z_{1})+(X_{2}:Y_{2}:Z_{2})=(X_{3}:Y_{3}:Z_{3})}$

dónde

${\displaystyle X_{3}=Z_{1}Z_{2}(X_{1}Y_{2}+X_{2}Y_{1})(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})}$

${\displaystyle Y_{3}=Z_{1}Z_{2}(Y_{1}Y_{2}-X_{1}X_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})}$

${\displaystyle Z_{3}=(Z_{1}^{2}Z_{2}^{2}-dX_{1}X_{2}Y_{1}Y_{2})(Z_{1}^{2}Z_{2}^{2}+dX_{1}X_{2}Y_{1}Y_{2})}$

Algoritmo

La suma de dos puntos en la curva de Edwards se podría calcular de manera más eficiente ^[4] en la forma extendida de Edwards , donde : ${\displaystyle (X:Y:Z:T)}$ ${\displaystyle T=XY/Z}$ ${\displaystyle (X_{3}:Y_{3}:Z_{3}:T_{3})=(X_{1}:Y_{1}:Z_{1}:T_{1})+(X_{2}:Y_{2}:Z_{2}:T_{2})}$

${\displaystyle A=X_{1}X_{2};B=Y_{1}Y_{2};C=dT_{1}T_{2};D=Z_{1}Z_{2};}$

${\displaystyle E=(X_{1}+Y_{1})(X_{2}+Y_{2})-A-B;F=D-C;G=D+C;H=B-A;}$

${\displaystyle X_{3}=E\cdot F;Y_{3}=G\cdot H;Z_{3}=F\cdot G;T_{3}=E\cdot H;}$

Duplicación

La duplicación se puede realizar con exactamente la misma fórmula que la suma. La duplicación se refiere al caso en el que las entradas ( x ₁ ,  y ₁ ) y ( x ₂ ,  y ₂ ) son iguales.

Duplicar un punto : ${\displaystyle P=(x,y)}$

${\displaystyle {\begin{aligned}(x,y)+(x,y)&=\left({\frac {2xy}{1+dx^{2}y^{2}}},{\frac {y^{2}-x^{2}}{1-dx^{2}y^{2}}}\right)\\[6pt]&=\left({\frac {2xy}{x^{2}+y^{2}}},{\frac {y^{2}-x^{2}}{2-x^{2}-y^{2}}}\right)\end{aligned}}}$

Los denominadores se simplificaron en base a la ecuación de la curva . Se logra una mayor aceleración al calcular como . Esto reduce el costo de duplicar en coordenadas homomórficas a 3 M  + 4 S  + 3 C  + 6 a , mientras que la adición general cuesta 10 M  + 1 S  + 1 C  + 1 D  + 7 a . Aquí M son las multiplicaciones de campo, S son los cuadrados de campo, D es el costo de multiplicar por el parámetro de curva d y a es la adición de campo. ${\displaystyle x^{2}+y^{2}=1+dx^{2}y^{2}}$ ${\displaystyle 2xy}$ ${\displaystyle (x+y)^{2}-x^{2}-y^{2}}$

Ejemplo de duplicación

Al igual que en el ejemplo anterior para la ley de la adición, considere la curva de Edwards con d=2:

${\displaystyle x^{2}+y^{2}=1+2x^{2}y^{2}}$

y el punto . Las coordenadas del punto son: ${\displaystyle P=(1,0)}$ ${\displaystyle P_{2}=2P_{1}}$

${\displaystyle x_{2}={\frac {2xy}{x^{2}+y^{2}}}=0}$

${\displaystyle y_{2}={\frac {y^{2}-x^{2}}{2-(x^{2}+y^{2})}}=-1}$

El punto obtenido al duplicar P es entonces . ${\displaystyle P_{2}=(0,-1)}$

Adición mixta

La adición mixta es el caso cuando se sabe que Z ₂ es 1. En tal caso, A = Z ^1. _Z 2 _se puede eliminar y el costo total se reduce a 9 M + 1 S + 1 C + 1 D + 7 a

Algoritmo

A= Z ₁ ^. Z ₂ // en otras palabras, A= Z ₁

^B = _Z12

C _{= X1.X2}​

_D = _Y1.Y2^​​

^E = ^d.C.D​​

F=SER

Sol = Si + Mi

X ₃ = A ^. F((X _I +Y ₁ ) ^. (X ₂ +Y ₂ )-CD)

Y3 = ^A.G. ( ^CC )_​

Z3 = ^C.F.G_​​^​​

Triplicando

La triplicación se puede hacer duplicando primero el punto y luego sumando el resultado a sí mismo. Aplicando la ecuación de la curva como en la duplicación, obtenemos

${\displaystyle 3(x_{1},y_{1})=\left({\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2y_{1})^{2}}{4(x_{1}^{2}-1)x_{1}^{2}-(x_{1}^{2}-y_{1}^{2})^{2}}}x_{1},{\frac {(x_{1}^{2}+y_{1}^{2})^{2}-(2x_{1})^{2}}{-4(y_{1}^{2}-1)y_{1}^{2}+(x_{1}^{2}-y_{1}^{2})^{2}}}y_{1}\right).\,}$

Hay dos conjuntos de fórmulas para esta operación en coordenadas estándar de Edwards. El primero cuesta 9 M  + 4 S mientras que el segundo necesita 7 M  + 7 S. Si la relación S/M es muy pequeña, específicamente por debajo de 2/3, entonces el segundo conjunto es mejor mientras que para relaciones mayores es preferible el primero. ^[5] Utilizando las fórmulas de adición y duplicación (como se mencionó anteriormente) el punto ( X ₁  :  Y ₁  :  Z ₁ ) se calcula simbólicamente como 3( X ₁  :  Y ₁  :  Z ₁ ) y se compara con ( X ₃  :  Y ₃  :  Z ₃ )

Ejemplo de triplicación

Dada la curva de Edwards con d=2, y el punto P ₁ =(1,0), el punto 3P ₁ tiene coordenadas:

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

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

Por lo tanto, 3P ₁ =(-1,0)=P- ₁ . Este resultado también se puede encontrar considerando el ejemplo de duplicación: 2P ₁ =(0,1), por lo que 3P ₁ = 2P ₁ + P ₁ = (0,-1) + P ₁ = -P ₁ .

Algoritmo

^A = _X12

^B = _Y12

C=(2Z ₁ ) ²

D=A+B

E= ^D2

F=2D.(AB)

G=EB.C

H=EA.C

Yo = F + H

J=FG

X3 = _GJX1

Y3 ₌ HOLA1

Z3 = _IJZ1

Esta fórmula cuesta 9 M  + 4 S

Coordenadas de Edwards invertidas

Bernstein y Lange introdujeron un sistema de coordenadas aún más rápido para curvas elípticas llamado coordenadas de Edward invertidas ^[6] en el que las coordenadas ( X  :  Y  :  Z ) satisfacen la curva ( X ²  +  Y ² ) Z ²  = ( dZ ⁴  +  X ² Y ² ) y corresponde al punto afín ( Z / X ,  Z / Y ) en la curva de Edwards x ²  +  y ²  = 1 +  dx ² y ² con XYZ ≠ 0.

Las coordenadas de Edwards invertidas , a diferencia de las coordenadas de Edwards estándar, no tienen fórmulas de adición completas: algunos puntos, como el elemento neutro, deben manejarse por separado. Pero las fórmulas de adición aún tienen la ventaja de una fuerte unificación: se pueden usar sin cambios para duplicar un punto.

Para obtener más información sobre las operaciones con estas coordenadas, consulte http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html

Coordenadas extendidas para curvas de Edward

Existe otro sistema de coordenadas con el que se puede representar una curva de Edwards. Estas nuevas coordenadas se denominan coordenadas extendidas ^[7] y son incluso más rápidas que las coordenadas invertidas. Para más información sobre el coste-tiempo requerido en las operaciones con estas coordenadas, consulte: http://hyperelliptic.org/EFD/g1p/auto-edwards.html

Véase también

• Curva de Edwards torcida

Para obtener más información sobre el tiempo de ejecución requerido en un caso específico, consulte la Tabla de costos de operaciones en curvas elípticas .

Notas

1. Bernstein, Daniel; Lange, Tanja (3 de marzo de 2014), Cómo diseñar un sistema de firma de curva elíptica
2. Daniel. J. Bernstein , Tanja Lange, pág. 3, Adición y duplicación más rápidas en curvas elípticas
3. Christophe Arene; Tanja Lange; Michael Naehrig; Christophe Ritzenthaler (2009). "Cálculo más rápido del emparejamiento Tate". arXiv : 0904.0854 . Código Bibliográfico :2009arXiv0904.0854A . Consultado el 28 de febrero de 2010 .
4. Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter y Ed Dawson. Revisitando las curvas de Edwards torcidas . En ASIACRYPT 2008, páginas 326–343, 2008
5. Bernstein et al., Optimización de la multiplicación de un solo escalar de curva elíptica de base doble
6. Daniel J. Bernstein. Tanja Lange, pág. 2, coordenadas de Edward invertidas
7. H. Hisil, KK Wong, G. Carter, E. Dawson Operaciones de grupo más rápidas en curvas elípticas

Referencias

• Bernstein, Daniel ; Lange, Tanja (2007), Adición y duplicación más rápidas en curvas elípticas (PDF)
• Edwards, Harold M. (9 de abril de 2007), "Una forma normal para curvas elípticas", Boletín de la Sociedad Matemática Americana , 44 (3): 393–422, doi : 10.1090/s0273-0979-07-01153-6 , ISSN  0002-9904
• Operaciones de grupo más rápidas en curvas elípticas , H. Hisil, KK Wong, G. Carter, E. Dawson
• DJBernstein, P. Birkner, T. Lange, C. Peters, Optimización de la multiplicación de un único escalar con curva elíptica de base doble (PDF){{citation}}: CS1 maint: multiple names: authors list (link)
• Washington, Lawrence C. (2008), Curvas elípticas: teoría de números y criptografía , Matemáticas discretas y sus aplicaciones (2.ª ed.), Chapman & Hall/CRC, ISBN 978-1-4200-7146-7
• Bernstein, Daniel ; Lange, Tanja , Coordenadas de Edwards invertidas (PDF)

Enlaces externos

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-edwards.html