Curva torcida de Edwards

Una curva de ecuación de Edwards retorcida ${\displaystyle 10x^{2}+y^{2}=1+6x^{2}y^{2}}$

En geometría algebraica , las curvas de Edwards retorcidas son modelos planos de curvas elípticas , una generalización de las curvas de Edwards introducida por Bernstein , Birkner, Joye, Lange y Peters en 2008. ^[1] El conjunto de curvas lleva el nombre del matemático Harold M. Edwards . Las curvas elípticas son importantes en la criptografía de clave pública y las curvas retorcidas de Edwards son el núcleo de un esquema de firma electrónica llamado EdDSA que ofrece alto rendimiento y al mismo tiempo evita problemas de seguridad que han surgido en otros esquemas de firma digital.

Definición

Una curva de Edwards torcida sobre un campo con una característica distinta de 2 (es decir, ningún elemento es su propio inverso aditivo) es una curva plana afín definida por la ecuación: ${\displaystyle E_{E,a,d}}$ ${\displaystyle \mathbb {K} }$

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

donde hay elementos distintos de cero de . ${\displaystyle a,d}$ ${\displaystyle \mathbb {K} }$

Cada curva de Edwards torcida es una torsión de una curva de Edwards . El caso especial no está torcido , porque la curva se reduce a una curva de Edwards ordinaria . ${\displaystyle a=1}$

Cada curva de Edwards torcida es biracionalmente equivalente a una curva elíptica en forma de Montgomery y viceversa. ^[2]

derecho de grupo

Como ocurre con todas las curvas elípticas, también para la curva de Edwards torcida, es posible hacer algunas operaciones entre sus puntos, como sumar dos de ellos o duplicar (o triplicar) uno. Los resultados de estas operaciones son siempre puntos que pertenecen a la propia curva. En las siguientes secciones se dan algunas fórmulas para obtener las coordenadas de un punto resultantes de una suma entre otros dos puntos (suma), o las coordenadas de un punto resultantes de la duplicación de un solo punto en una curva.

Suma sobre curvas retorcidas de Edwards

Sea un campo con característica diferente de 2. Sea y puntos en la curva torcida de Edwards. La ecuación de la curva de Edwards torcida se escribe como; ${\displaystyle \mathbb {K} }$ ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (x_{2},y_{2})}$

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

La suma de estos puntos es : ${\displaystyle (x_{1},y_{1}),(x_{2},y_{2})}$ ${\displaystyle E_{E,a,d}}$

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

El elemento neutro es (0,1) y el negativo de es ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle (-x_{1},y_{1})}$

Estas fórmulas también funcionan para duplicar. Si a es un cuadrado y d es un no cuadrado , estas fórmulas están completas : esto significa que se pueden utilizar para todos los pares de puntos sin excepciones ; por lo que también funcionan para duplicar, y se aceptan elementos neutros y negativos como entradas. ^{[3] [ verificación fallida ]} ${\displaystyle \mathbb {K} }$ ${\displaystyle \mathbb {K} }$

Ejemplo de suma

Dada la siguiente curva de Edwards torcida con a = 3 y d = 2:

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

Es posible sumar los puntos y utilizar la fórmula dada anteriormente. El resultado es un punto P ₃ que tiene coordenadas: ${\displaystyle P_{1}=(1,{\sqrt {2}})}$ ${\displaystyle P_{2}=(1,-{\sqrt {2}})}$

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

${\displaystyle y_{3}={\frac {y_{1}y_{2}-ax_{1}x_{2}}{1-dx_{1}x_{2}y_{1}y_{2}}}=-1.}$

Duplicación en curvas retorcidas de Edwards

La duplicación se puede realizar exactamente con la misma fórmula que la suma. La duplicación de un punto de la curva es: ${\displaystyle (x_{1},y_{1})}$ ${\displaystyle E_{E,a,d}}$

${\displaystyle 2(x_{1},y_{1})=(x_{3},y_{3})}$

dónde

${\displaystyle {\begin{aligned}x_{3}&={\frac {x_{1}y_{1}+y_{1}x_{1}}{1+dx_{1}x_{1}y_{1}y_{1}}}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}\\[6pt]y_{3}&={\frac {y_{1}y_{1}-ax_{1}x_{1}}{1-dx_{1}x_{1}y_{1}y_{1}}}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}.\end{aligned}}}$

Los denominadores al duplicar se simplifican utilizando la ecuación de la curva . Esto reduce la potencia de 4 a 2 y permite un cálculo más eficiente. ${\displaystyle dx^{2}y^{2}=ax^{2}+by^{2}-1}$

Ejemplo de duplicación

Considerando la misma curva de Edwards torcida dada en el ejemplo anterior, con a=3 y d=2, es posible duplicar el punto . El punto 2P ₁ obtenido mediante la fórmula anterior tiene las siguientes coordenadas: ${\displaystyle P_{1}=(1,{\sqrt {2}})}$

${\displaystyle x_{3}={\frac {2x_{1}y_{1}}{ax_{1}^{2}+y_{1}^{2}}}={\frac {2{\sqrt {2}}}{5}},}$

${\displaystyle y_{3}={\frac {y_{1}^{2}-ax_{1}^{2}}{2-ax_{1}^{2}-y_{1}^{2}}}={\frac {1}{3}}.}$

Es fácil ver, con algunos pequeños cálculos, que el punto pertenece a la curva . ${\displaystyle P_{3}=\left({\frac {2{\sqrt {2}}}{5}},{\frac {1}{3}}\right)}$ ${\displaystyle 3x^{2}+y^{2}=1+2x^{2}y^{2}}$

Coordenadas extendidas

Existe otro tipo de sistema de coordenadas con el que se puede representar un punto en las curvas de Edwards torcidas. Un punto en se representa como X , Y , Z , T que satisface las siguientes ecuaciones x  =  X / Z , y  =  Y / Z , xy  =  T / Z . ${\displaystyle (x,y,z)}$ ${\displaystyle ax^{2}+y^{2}=1+dx^{2}y^{2}}$

Las coordenadas del punto ( X : Y : Z : T ) se llaman coordenadas de Edwards torcidas extendidas . El elemento de identidad está representado por (0:1:1:0). El negativo de un punto es (− X : Y : Z : − T ).

Coordenadas Edwards retorcidas invertidas

Las coordenadas del punto se denominan coordenadas de Edwards retorcidas invertidas en la curva con ; este punto al afín en . Bernstein y Lange introdujeron estas coordenadas invertidas, para el caso a=1 y observaron que las coordenadas además ahorran tiempo. ${\displaystyle (X_{1}:Y_{1}:Z_{1})}$ ${\textstyle (X^{2}+aY^{2})Z^{2}=X^{2}Y^{2}+dZ^{4}}$ ${\textstyle X_{1}Y_{1}Z_{1}\neq 0}$ ${\displaystyle (Z_{1}/X_{1},Z_{1}/Y_{1})}$ ${\displaystyle E_{E,a,d}}$

Coordenadas proyectivas de Edwards retorcidas

La ecuación para la curva proyectiva de Edwards torcida se da como: Para Z ₁  ≠ 0 el punto (X ₁ :Y ₁ :Z ₁ ) representa el punto afín ( x ₁ =  X ₁ / Z ₁ , y ₁ = Y ₁ / Z ₁ ) en E _{E , a , re} . ${\displaystyle (aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}$

Expresar una curva elíptica en la forma retorcida de Edwards ahorra tiempo en aritmética, incluso cuando la misma curva se puede expresar en la forma de Edwards.

Suma en curvas torcidas proyectivas

La suma en una curva proyectiva de Edwards torcida viene dada por

(X ₃ :Y ₃ :Z ₃ ) = (X ₁ :Y ₁ :Z ₁ ) + (X ₂ :Y ₂ :Z ₂ )

y cuesta 10 multiplicaciones + 1 cuadratura + 2 D + 7 sumas , donde las 2 D son una multiplicación por a y una por d .

Algoritmo

A = Z ₁ · Z ₂ ,

B = Un ²

C = X ₁ · X ₂

D = Y ₁ · Y ₂

E = dC·D

F = segundo - mi

GRAMO = B + E

X ₃ = A · F((X ₁ + Y ₁ ) · (X ₂ + Y ₂ ) − C − D)

Y ₃ = A · G · (D − aC)

Z ₃ = F·G

Duplicación en curvas torcidas proyectivas

La duplicación de la curva proyectiva torcida viene dada por

(X ₃ :Y ₃ :Z ₃ ) = 2(X ₁ :Y ₁ :Z ₁ ).

Esto cuesta 3 multiplicaciones + 4 cuadraturas + 1 D + 7 sumas , donde 1 D es una multiplicación por a .

Algoritmo

B = (X ₁ + Y ₁ ) ²

C = X ₁ ²

D = Y ₁ ²

mi = aC

F = mi + re

H = Z ₁ ²

J = F - 2H

X ₃ = (B − C − D).J

Y ₃ = F · (E − D)

Z ₃ = F · J ^[1]

Ver también

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

Notas

1. Bernstein, Daniel J.; Birkner, Peter; Joye, Marc; Lange, Tanja; Peters, Christiane (2008). Vaudenay, Serge (ed.). Curvas retorcidas de Edwards. Apuntes de conferencias sobre informática. vol. 5023. Berlín, Heidelberg: Springer. págs. 389–405. doi :10.1007/978-3-540-68164-9_26. ISBN 978-3-540-68164-9. {{cite book}}: |journal=ignorado ( ayuda )
2. Daniel J. Bernstein; Peter Birkner; Marc Joyé; Tanja Lange; Christiane Peters. "Curvas retorcidas de Edwards" (PDF) . Consultado el 28 de enero de 2020 .
3. Daniel J. Bernstein y Tanja Lange, Suma y duplicación más rápidas en curvas elípticas

Referencias

• Daniel J. Bernstein; Marc Joyé; Tanja Lange; Peter Birkner; Christiane Peters, Curvas retorcidas de Edwards (PDF)

• Huseyin Hisil, Kenneth Wong, Gary Carter, Ed Dawson. (2008), "Revisión de las curvas retorcidas de Edwards", Archivo ePrint de criptología{{citation}}: CS1 maint: multiple names: authors list (link)

• Daniel J. Bernstein; Tanja Lange; Peter Birkner; Christiane Peters, ECM usando curvas de Edwards (PDF)

enlaces externos

• http://hyperelliptic.org/EFD/g1p/index.html
• http://hyperelliptic.org/EFD/g1p/auto-twisted.html
• El algoritmo Ed25519: http://ed25519.cr.yp.to/