Forma arpillera de una curva elíptica

En geometría , la curva de Hesse es una curva plana similar al folio de Descartes . Lleva el nombre del matemático alemán Otto Hesse . Esta curva se sugirió para su aplicación en criptografía de curva elíptica , porque la aritmética en esta representación de la curva es más rápida y necesita menos memoria que la aritmética en la forma estándar de Weierstrass . ^[1]

Definición

Una curva de ecuación de Hesse ${\displaystyle x^{3}+y^{3}+1=0.3xy}$

Vamos a ser un campo y considerar una curva elíptica en el siguiente caso especial de forma Weierstrass sobre :${\displaystyle K}$ ${\displaystyle E}$${\displaystyle K}$

${\displaystyle Y^{2}+a_{1}XY+a_{3}Y=X^{3}}$

donde la curva tiene discriminante Entonces el punto tiene orden 3.${\displaystyle \Delta =\left(a_{3}^{3}\left(a_{1}^{3}-27a_{3}\right)\right)=a_{3}^{3}\delta .}$${\displaystyle P=(0,0)}$

Para demostrar que tiene orden 3, observe que la tangente a en es la recta que se cruza con la multiplicidad 3 en .${\displaystyle P=(0,0)}$${\displaystyle E}$${\displaystyle P}$${\displaystyle Y=0}$${\displaystyle E}$${\displaystyle P}$

Por el contrario, dado un punto de orden 3 en una curva elíptica, ambos definidos sobre un campo, se puede poner la curva en forma de Weierstrass de modo que la tangente en sea ​​la línea . Entonces la ecuación de la curva es con .${\displaystyle P}$${\displaystyle E}$${\displaystyle K}$${\displaystyle P=(0,0)}$${\displaystyle P}$${\displaystyle Y=0}$${\displaystyle Y^{2}+a_{1}XY+a_{3}Y=X^{3}}$${\displaystyle a_{1},a_{3}\in K}$

Ahora, para obtener la curva de Hesse, es necesario hacer la siguiente transformación :

Primero denotemos una raíz del polinomio${\displaystyle \mu }$

${\displaystyle T^{3}-\delta T^{2}+{\delta ^{2} \over 3}T+a_{3}\delta ^{2}=0.}$

Luego

${\displaystyle \mu ={\delta -a_{1}\delta ^{2/3} \over 3}.}$

Tenga en cuenta que si tiene un campo de orden finito , entonces cada elemento de tiene una raíz cúbica única ; en general, se encuentra en un campo de extensión de K . ${\displaystyle K}$${\displaystyle q\equiv 2{\pmod {3}}}$${\displaystyle K}$${\displaystyle \mu }$

Ahora, definiendo el siguiente valor , se obtiene otra curva, C, que es biracionalmente equivalente a E:${\textstyle D={\frac {3(\mu -\delta )}{\mu }}}$

${\displaystyle C}$ : ${\displaystyle x^{3}+y^{3}+z^{3}=Dxyz}$

que se llama forma hessiana cúbica (en coordenadas proyectivas )

${\displaystyle C}$ : ${\displaystyle x^{3}+y^{3}+1=Dxy}$

en el plano afín (satisfactorio y ).${\textstyle x={\frac {X}{Z}}}$${\textstyle y={\frac {Y}{Z}}}$

Además, (de lo contrario, la curva sería singular ).${\displaystyle D^{3}\neq 1}$

A partir de la curva de Hesse, una ecuación de Weierstrass biracionalmente equivalente viene dada por

${\displaystyle v^{2}=u^{3}-27D\left(D^{3}+8\right)u+54\left(D^{6}-20D^{3}-8\right),}$

bajo las transformaciones:

${\displaystyle (x,y)=\left(\eta \left(u+9D^{2}\right),-1+\eta \left(3D^{3}-Dx-12\right)\right)}$

y

${\displaystyle (u,v)=\left(-9D^{2}+\varepsilon x,3\varepsilon \left(y-1\right)\right)}$

dónde:

${\displaystyle \eta ={\frac {6\left(D^{3}-1\right)\left(v+9D^{3}-3Du-36\right)}{\left(u+9D^{2}\right)^{3}+\left(3Dd-Du-12\right)^{3}}}}$

y

${\displaystyle \varepsilon ={\frac {12\left(D^{3}-1\right)}{Dx+y+1}}}$

Derecho de grupo

Es interesante analizar la ley de grupo de la curva elíptica, definiendo las fórmulas de suma y duplicación (porque los ataques SPA y DPA se basan en el tiempo de ejecución de estas operaciones). Además, en este caso, solo necesitamos usar el mismo procedimiento para calcular la suma, duplicación o resta de puntos para obtener resultados eficientes, como se dijo anteriormente. En general, la ley de grupo se define de la siguiente manera: si tres puntos se encuentran en la misma línea, entonces suman cero . Entonces, según esta propiedad, las leyes de grupo son diferentes para cada curva.

En este caso, la forma correcta es utilizar las fórmulas de Cauchy-Desboves, obteniendo el punto en el infinito θ = (1: −1: 0) , es decir, el elemento neutro (la inversa de θ es nuevamente θ ). Sea P = ( x ₁ , y ₁ ) un punto en la curva. La línea contiene el punto P y el punto en el infinito θ . Por lo tanto, - P es el tercer punto de la intersección de esta línea con la curva. Al intersectar la curva elíptica con la línea, se obtiene la siguiente condición ${\displaystyle y=-x+(x_{1}+y_{1})}$${\displaystyle x_{2}-(x_{1}+y_{1})\cdot x+x_{1}\cdot y_{1}=\theta }$

Dado que no es cero (porque D ³ es distinto de 1), la coordenada x de - P es y ₁ y la coordenada y de - P es x ₁ , es decir, o en coordenadas proyectivas .${\displaystyle x_{1}+y_{1}+D}$${\displaystyle -P=(y_{1},x_{1})}$${\displaystyle -P=(Y_{1}:X_{1}:Z_{1})}$

En algunas aplicaciones de criptografía de curva elíptica y el método de factorización de curva elíptica ( ECM ) es necesario calcular las multiplicaciones escalares de P , digamos [ n ] P para algún número entero n , y se basan en el método de doble y suma ; estas operaciones necesitan las fórmulas de suma y duplicación.

Duplicación

Ahora, si es un punto en la curva elíptica, es posible definir una operación de "duplicación" usando las fórmulas de Cauchy-Desboves:${\displaystyle P=(X_{1}:Y_{1}:Z_{1})}$

${\displaystyle [2]P=\left(Y_{1}\cdot \left(X_{1}^{3}-Z_{1}^{3}\right):X_{1}\cdot \left(Z_{1}^{3}-Y_{1}^{3}\right):Z_{1}\cdot \left(Y_{1}^{3}-X_{1}^{3}\right)\right)}$

Adición

De la misma manera, para dos puntos diferentes, digamos y , es posible definir la fórmula de la suma. Sea R la suma de estos puntos, R = P + Q , entonces sus coordenadas están dadas por:${\displaystyle P=(X_{1}:Y_{1}:Z_{1})}$${\displaystyle Q=(X_{2}:Y_{2}:Z_{2})}$

${\displaystyle R=\left(Y_{1}^{2}\cdot X_{2}\cdot Z_{2}-Y_{2}^{2}\cdot X_{1}\cdot Z_{1}:X_{1}^{2}\cdot Y_{2}\cdot Z_{2}-X_{2}^{2}\cdot Y_{1}\cdot Z_{1}:Z_{1}^{2}\cdot X_{2}\cdot Y_{2}-Z_{2}^{2}\cdot X_{1}\cdot Y_{1}\right)}$

Algoritmos y ejemplos

Hay un algoritmo que se puede usar para agregar dos puntos diferentes o para duplicar; lo dan Joye y Quisquater . Entonces, el siguiente resultado da la posibilidad de obtener la operación de duplicación por la suma:

Proposición . Sea P = ( X, Y, Z ) un punto en una curva elíptica de Hesse E ( K ) . Luego:

${\displaystyle 2(X:Y:Z)=(Z:X:Y)+(Y:Z:X)}$ (2).

Además, tenemos ( Z : X : Y ) ≠ ( Y : Z : X ) .

Finalmente, contrariamente a otras parametrizaciones , no hay resta para calcular la negación de un punto. Por lo tanto, este algoritmo de suma también se puede utilizar para restar dos puntos P = ( X ₁ : Y ₁ : Z ₁ ) y Q = ( X ₂ : Y ₂ : Z ₂ ) en una curva elíptica de Hesse:

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

En resumen, adaptando el orden de las entradas de acuerdo con la ecuación (2) o (3), el algoritmo de suma presentado anteriormente se puede usar indistintamente para: Sumar 2 (diferencia) puntos, Doblar un punto y Restar 2 puntos con solo 12 multiplicaciones y 7 variables auxiliares, incluidas las 3 variables de resultado. Antes de la invención de las curvas de Edwards , estos resultados representan el método más rápido conocido para implementar la multiplicación escalar de la curva elíptica hacia la resistencia contra ataques de canal lateral .

Para algunos algoritmos, la protección contra ataques de canal lateral no es necesaria. Entonces, para estas duplicaciones puede ser más rápido. Dado que hay muchos algoritmos, aquí solo se proporciona el mejor para las fórmulas de suma y duplicación, con un ejemplo para cada uno:

Adición

Sea P ₁ = ( X ₁ : Y ₁ : Z ₁ ) y P ₂ = ( X ₂ : Y ₂ : Z ₂ ) dos puntos distintos de θ . Suponiendo que Z ₁ = Z ₂ = 1, entonces el algoritmo viene dado por:

A = X ₁ Y ₂

B = Y ₁ X ₂

X ₃ = B Y ₁ - Y ₂ A

Y ₃ = X ₁ A - B X ₂

Z ₃ = Y ₂ X ₂ - X ₁ Y ₁

El costo necesario es 8 multiplicaciones y 3 adiciones costo de readición de 7 multiplicaciones y 3 adiciones, dependiendo del primer punto.

Ejemplo

Dados los siguientes puntos en la curva para d = −1 P ₁ = (1: 0: −1) y P ₂ = (0: −1: 1) , entonces si P ₃ = P ₁ + P ₂ tenemos:

X ₃ = 0-1 = −1

Y ₃ = −1−0 = −1

Z ₃ = 0 - 0 = 0

Entonces: P ₃ = (−1: −1: 0)

Duplicación

Sea P  = ( X ₁  :  Y ₁  :  Z ₁ ) un punto, entonces la fórmula de duplicación viene dada por:

• A = X ₁ ²
• B = Y ₁ ²
• D = A  +  B
• G = ( X ₁  +  Y ₁ ) ²  -  D
• X ₃ = (2 Y ₁  -  G ) × ( X ₁  +  A  + 1)
• Y ₃ = ( G  - 2 X ₁ ) × ( Y ₁  +  B  + 1)
• Z ₃ = ( X ₁  -  Y ₁ ) × ( G  + 2 D )

El costo de este algoritmo es tres multiplicaciones + tres cuadraturas + 11 adiciones + 3 × 2.

Ejemplo

Si es un punto sobre la curva de Hesse con parámetro d = −1 , entonces las coordenadas de están dadas por:${\displaystyle P=(-1:-1:1)}$${\displaystyle 2P=(X:Y:Z)}$

X = (2. (−1) - 2) (−1 + 1 + 1) = −4

Y = (−4-2. (−1)) ((−1) + 1 + 1) = −2

Z = (−1 - (−1)) ((−4) + 2. 2) = 0

Es decir, ${\displaystyle 2P=(-4:-2:0)}$

Coordenadas extendidas

Existe otro sistema de coordenadas con el que se puede representar una curva de Hesse; estas nuevas coordenadas se denominan coordenadas extendidas . Pueden acelerar la adición y la duplicación. Para obtener más información sobre las operaciones con las coordenadas extendidas, consulte:

http://hyperelliptic.org/EFD/g1p/auto-hessian-extended.html#addition-add-20080225-hwcd

${\displaystyle x}$y se representan satisfaciendo las siguientes ecuaciones:${\displaystyle y}$${\displaystyle X,Y,Z,XX,YY,ZZ,XY,YZ,XZ}$

${\displaystyle x=X/Z}$

${\displaystyle y=Y/Z}$

${\displaystyle XX=X\cdot X}$

${\displaystyle YY=Y\cdot Y}$

${\displaystyle ZZ=Z\cdot Z}$

${\displaystyle XY=2\cdot X\cdot Y}$

${\displaystyle YZ=2\cdot Y\cdot Z}$

${\displaystyle XZ=2\cdot X\cdot Z}$

Ver también

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

Curvas retorcidas de Hesse

enlaces externos

• http://hyperelliptic.org/EFD/g1p/index.html

Notas

1. Fórmulas de Cauchy-Desbove: curvas elípticas hessianas y ataques de canal lateral , Marc Joye y Jean-Jacques Quisquarter

Referencias

• Otto Hesse (1844), "Über die Elimination der Variabeln aus drei algebraischen Gleichungen vom zweiten Grade mit zwei Variabeln", Journal für die reine und angewandte Mathematik , 10, págs. 68–96
• Marc Joye, Jean-Jacques Quisquater (2001). "Curvas elípticas de Hesse y ataques de canal lateral". Hardware criptográfico y sistemas integrados - CHES 2001 . Apuntes de conferencias en Ciencias de la Computación. 2162 . Springer-Verlag Berlin Heidelberg 2001. págs. 402–410. doi : 10.1007 / 3-540-44709-1_33 . ISBN 978-3-540-42521-2.
• NP Smart (2001). "La forma de Hesse de una curva elíptica". Hardware criptográfico y sistemas integrados - CHES 2001 . Apuntes de conferencias en Ciencias de la Computación. 2162 . Springer-Verlag Berlin Heidelberg 2001. págs. 118-125. doi : 10.1007 / 3-540-44709-1_11 . ISBN 978-3-540-42521-2.