Curva de Edwards

Curvas de Edwards de la ecuación ^x² + y² = 1 + d · x² · y² ^sobrelos 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ñalando varias ventajas de la forma de Edwards en comparación con la forma de Weierstrass, más conocida . ^[¹^]

Definición

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

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

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

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 algebraica una vez que se elige un punto 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 grupo

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

Cada curva de Edwards $x^{2}+y^{2}=1+dx^{2}y^{2}$ sobre el campo K con característica distinta de 2 con $d\neq 1$ es birracionalmente equivalente a una curva elíptica sobre el mismo campo: $(1/e)v^{2}=u^{3}+(4/e-2)u^{2}+u$ , dónde $e=1-d,u={\frac {1+y}{1-y}},v={\frac {2(1+y)}{x(1-y)}}$ y el punto $P=(0,1)$ se mapea al infinito O. Este mapeo birracional induce un grupo en cualquier curva de Edwards.

Ley de adición de Edwards

En cualquier curva elíptica, la suma de dos puntos viene dada por 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 $(x_{1},y_{1})$ y $(x_{2},y_{2})$ viene dado por la fórmula

(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)\,

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

Si d no es un cuadrado en K y $\{(x_{1},y_{1}),(x_{2},y_{2})\}\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}^{2}$ , entonces no hay puntos excepcionales: los denominadores $1+dx_{1}x_{2}y_{1}y_{2}$ y $1-dx_{1}x_{2}y_{1}y_{2}$ son siempre distintos de cero. Por lo tanto, la ley de suma de Edwards es 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, sin excepción para el elemento neutro, sin 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.

Si d es un cuadrado en K , entonces la misma operación puede tener puntos excepcionales, es decir, puede haber pares de puntos. $(x_{1},y_{1}),(x_{2},y_{2})\in \{(x,y)|x^{2}+y^{2}=1+dx^{2}y^{2}\}$ de tal manera que uno de los denominadores se convierte en cero: o $1+dx_{1}x_{2}y_{1}y_{2}=0$ o $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 es fuertemente unificada , es decir, también se puede usar 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 :

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

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

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

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

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

Para comprender mejor el concepto de "adición" de puntos en una curva, un buen ejemplo lo proporciona el grupo clásico de círculos :

toma el círculo de radio 1

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

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

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

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

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

{\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 }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 forma, la fórmula de suma para puntos en el círculo de radio 1 es:

{\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 en curvas de Edwards

Los puntos de una curva elíptica forman un grupo abeliano : se pueden sumar puntos y tomar múltiplos enteros de un mismo punto. Cuando una curva elíptica se describe mediante una ecuación cúbica no singular , 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 recta que pasa por P y Q.

El mapeo birracional entre una curva de Edwards y la curva elíptica cúbica correspondiente transforma las líneas rectas en secciones cónicas ^{[ 3 ].} $Axy+Bx+Cy+D=0$ En otras palabras, para las curvas de Edwards los tres puntos $P$ , $Q$ y $-(P+Q)$ yacen sobre una hipérbola .

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

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

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

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

En el caso de duplicar un punto $P=(x,y)$ el punto inverso $-2P$ se encuentra en la cónica que toca la curva en el punto $P$ Los coeficientes de la forma cuadrática que define la cónica son (salvo escalares ):

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

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

$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 suma de Edwards originales, la ecuación de la curva se puede escribir en coordenadas proyectivas como:

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

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

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

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

dónde

$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})$

$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})$

$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 puede calcular de manera más eficiente ^{[ 4 ]} en la forma extendida de Edwards. $(X:Y:Z:T)$ , dónde $T=XY/Z$ :

$(X_{3}:Y_{3}:Z_{3}:T_{3})=(X_{1}:Y_{1}:Z_{1}:T_{1})+(X_{2}:Y_{2}:Z_{2}:T_{2})$

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

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

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

Duplicación

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

Duplicar un punto $P=(x,y)$ :

${\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 función de la ecuación de la curva. $x^{2}+y^{2}=1+dx^{2}y^{2}$ . Se logra una mayor aceleración mediante computación $2xy$ como $(x+y)^{2}-x^{2}-y^{2}$ Esto reduce el costo de duplicar en coordenadas homomórficas a 3 M + 4 S + 3 C + 6 a , mientras que la suma general cuesta 10 M + 1 S + 1 C + 1 D + 7 a . Aquí M son las multiplicaciones de campo, S son las elevaciones al cuadrado de campo, D es el costo de multiplicar por el parámetro de curva d , y a es la suma de campo.

Ejemplo de duplicación

Como en el ejemplo anterior para la ley de adición, consideremos la curva de Edwards con d=2:

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

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

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

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

El punto obtenido al duplicar P es, por lo tanto, $P_{2}=(0,-1)$ .

Adición mixta

La suma mixta se da cuando se sabe que Z ₂ es igual a 1. En tal caso, A = Z ₁^. Z ₂ 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 = Z ₁²

C = X ₁ . X ₂

D = Y ₁^. Y ₂

E=d ^. C ^. D

F=BE

G=B+E

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

Y ₃ = A ^. G ^. (DC)

Z ₃ =C ^. F ^. G

Triplicar

La triplicación se puede realizar 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

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 Edwards estándar. 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 se debe preferir el primero. ^{[ 5 ]} Usando las fórmulas de suma 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:

$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$

$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$

Entonces, $3P 1 =(-1,0)=P- 1$ . 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=X₁²

B=Y₁²

C=(2Z₁)²

D=A+B

E=D²

F=2D.(A-B)

G=E-B.C

H=E-A.C

I=F+H

J=F-G

X₃=G.J.X1

Y₃=H.I.Y1

Z₃=I.J.Z1

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 corresponden al punto afín ( Z / X , Z / Y ) en la curva de Edwards x ² + y ² = 1 + dx ²y ² con XYZ ≠ 0.

A diferencia de las coordenadas Edwards estándar, las coordenadas Edwards invertidas no cuentan con fórmulas de suma completas: algunos puntos, como el elemento neutro, deben tratarse por separado. Sin embargo, las fórmulas de suma conservan la ventaja de una fuerte unificación: pueden utilizarse sin modificaciones 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 obtener más información sobre el tiempo de ejecución de las operaciones con estas coordenadas, consulte: http://hyperelliptic.org/EFD/g1p/auto-edwards.html

Véase también

Curva de Edwards retorcida

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

↑ Bernstein, Daniel; Lange, Tanja (3 de marzo de 2014), Cómo diseñar un sistema de firma de curva elíptica
1 2 Daniel J. Bernstein, Tanja Lange, pág. 3, Suma y duplicación más rápidas en curvas elípticas
↑ Christophe Arene; Tanja Lange; Michael Naehrig; Christophe Ritzenthaler (2009). "Cálculo más rápido del emparejamiento de Tate" . arXiv : 0904.0854 . Bibcode : 2009arXiv0904.0854A . Consultado el 28 de febrero de 2010 .
↑ Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter y Ed Dawson. Curvas de Edwards retorcidas: una revisión. En ASIACRYPT 2008, páginas 326–343, 2008.
↑ Bernstein et al., Optimización de la multiplicación escalar simple de curvas elípticas de doble base
↑ Daniel J. Bernstein. Tanja Lange, pág. 2, Coordenadas de Edward invertidas
↑ 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),Suma 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", Bulletin of the American Mathematical Society , 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
DJ Bernstein, P. Birkner. T. Lange, C. Peters,Optimización de la multiplicación escalar simple de curva elíptica de doble base(PDF){{citation}}: CS1 maint: varios nombres: lista de autores ( enlace )
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

[1] Bernstein, Daniel; Lange, Tanja (3 de marzo de 2014), Cómo diseñar un sistema de firma de curva elíptica

[BernsteinLange-2] 1 2 Daniel J. Bernstein, Tanja Lange, pág. 3, Suma 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 de Tate" . arXiv : 0904.0854 . Bibcode : 2009arXiv0904.0854A . Consultado el 28 de febrero de 2010 .

[Twisted_Edwards_curves_revisited-4] Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter y Ed Dawson. Curvas de Edwards retorcidas: una revisión. En ASIACRYPT 2008, páginas 326–343, 2008.

[5] Bernstein et al., Optimización de la multiplicación escalar simple de curvas elípticas de doble base

[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

[

[ 2 ]

[ 3 ].

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]