Curva de Edwards torcida

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

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

Definición

Una curva de Edwards torcida sobre un cuerpo con 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 son 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 es que no está torcida , porque la curva se reduce a una curva de Edwards normal . ${\displaystyle a=1}$

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

Derecho de grupo

Como en todas las curvas elípticas, también en la curva de Edwards torcida es posible realizar 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 los apartados siguientes se dan algunas fórmulas para obtener las coordenadas de un punto resultante de una suma entre otros dos puntos (suma), o las coordenadas de un punto resultante de la duplicación de un único punto de una curva.

Adición a las curvas retorcidas de Edwards

Sea un cuerpo con característica distinta de 2. Sean y puntos sobre la curva de Edwards torcida. 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 la duplicación. Si a es un cuadrado en y d es un no cuadrado en , estas fórmulas son completas : esto significa que se pueden usar para todos los pares de puntos sin excepciones; por lo tanto, también funcionan para la duplicación, y se aceptan elementos neutros y negativos como entradas. ^{[3] [ verificación fallida ]} ${\displaystyle \mathbb {K} }$ ${\displaystyle \mathbb {K} }$

Ejemplo de adición

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

Duplicando las curvas retorcidas de Edwards

La duplicación se puede realizar con exactamente 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 en la duplicación se simplifican utilizando la ecuación de 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 satisfaciendo 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 denominan coordenadas de Edwards torcidas extendidas . El elemento identidad se representa por (0:1:1:0). El negativo de un punto es (− X : Y : Z :− T ).

Coordenadas de Edwards torcidas e invertidas

Las coordenadas del punto se denominan coordenadas de Edwards torcidas invertidas en la curva con ; este punto es el afín en . Bernstein y Lange introdujeron estas coordenadas invertidas para el caso a=1 y observaron que las coordenadas ahorran tiempo además. ${\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 torcidas

La ecuación para la curva de Edwards torcida proyectiva 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 , d} . ${\displaystyle (aX^{2}+Y^{2})Z^{2}=Z^{4}+dX^{2}Y^{2}}$

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

Adición en curvas retorcidas proyectivas

La adición en una curva de Edwards torcida proyectiva está dada por

(X3 _: Y3 _: Z3 ₎ = (X1 _: Y1 _: Z1 ₎ + ( _X2 : _Y2 : _Z2 )

y cuesta 10 M ultiplicaciones + 1 elevado al cuadrado + 2 D + 7 adiciones , donde las 2 D son una multiplicación por a y una por d .

Algoritmo

A = _Z1 · _Z2 ,

B = ^A2

C = _X1 · _X2

D = _Y1 · _Y2

E = dC·D

F = B - E

G = B + E

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

Y3 = A · G · (D − aC ₎

Z3 = _F ·G

Duplicación en curvas retorcidas proyectivas

La duplicación de la curva torcida proyectiva se da por

(X3 _: Y3 _: Z3 ₎ = 2(X1 _: Y1 _: Z1 ₎ .

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

Algoritmo

B = ( _X1 + _Y1 ) ²

^C = _X12

D = Y ₁ ²

E = aC

F = E + D

H = ^Z1 ₂

J = F-2H

X3 = (B- _C -D).J

Y3 = F _· (E − D)

Z3 = F·J ^[1 _]

Véase también

• Educación DSA
• 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 J.; Birkner, Peter; Joye, Marc; Lange, Tanja; Peters, Christiane (2008). "Curvas retorcidas de Edwards". En Vaudenay, Serge (ed.). Progresos en criptología - AFRICACRYPT 2008 . 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.
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, Adición 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), "Revisitando las curvas retorcidas de Edwards", Archivo de impresión electrónica 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/