Forma hessiana 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 fue sugerida para su aplicación en criptografía de curva elíptica , porque la aritmética en esta representación de 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}$

Sea un campo y considere una curva elíptica en el siguiente caso especial de la forma de Weierstrass : donde la curva tiene discriminante Entonces el punto tiene orden 3. ${\displaystyle K}$ ${\displaystyle E}$ ${\displaystyle K}$ $${\displaystyle Y^{2}+a_{1}XY+a_{3}Y=X^{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 at es la recta que corta a 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}$

Para obtener la curva de Hesse es necesario realizar 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.}$$

Entonces $${\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 {(\mu -\delta )}{\mu }}}$

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

que se llama forma cúbica de Hesse (en coordenadas proyectivas ) $${\displaystyle C:x^{3}+y^{3}+1=3Dxy}$$

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 está dada por las transformaciones: y donde: y $${\displaystyle v^{2}=u^{3}-27D\left(D^{3}+8\right)u+54\left(D^{6}-20D^{3}-8\right),}$$ $${\displaystyle (x,y)=\left(\eta \left(u+9D^{2}\right),-1+\eta \left(3D^{3}-Dx-12\right)\right)}$$ $${\displaystyle (u,v)=\left(-9D^{2}+\varepsilon x,3\varepsilon \left(y-1\right)\right)}$$ $${\displaystyle \eta ={\frac {6\left(D^{3}-1\right)\left(v+9D^{3}-3Du-36\right)}{\left(u+9D^{2}\right)^{3}+\left(3D^{3}-Du-12\right)^{3}}}}$$ $${\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 grupos se define de la siguiente manera: si tres puntos se encuentran en la misma línea, su suma es cero . Entonces, según esta propiedad, las leyes del 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 de la curva. La recta contiene el punto P y el punto en el infinito θ . Por tanto, − P es el tercer punto de intersección de esta recta con la curva. Intersectando la curva elíptica con la recta, 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 }$

Como 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 alguna aplicación 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 duplicar y sumar. ; estas operaciones necesitan las fórmulas de suma y duplicación.

Duplicación

Ahora bien, si es un punto de la curva elíptica, es posible definir una operación de "duplicación" utilizando 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)}$$

Suma

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 vienen 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 utilizar para sumar dos puntos diferentes o duplicarlo; está dado por Joye y Quisquater . Entonces, el siguiente resultado da la posibilidad de obtener la operación de duplicación por suma:

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

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

Finalmente, a diferencia de otras parametrizaciones , no existe ninguna 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:

En resumen, adaptando el orden de las entradas según la ecuación (2) o (3), el algoritmo de suma presentado anteriormente se puede utilizar indiferentemente para: Sumar 2 puntos (diferenciales), Duplicar 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 canales laterales .

Para algunos algoritmos no es necesaria la protección contra ataques de canal lateral. Entonces, estas duplicaciones pueden ser más rápidas. 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:

Suma

Sean 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 ₃ = POR Y ₁ - Y ₂ A

Y ₃ = X ₁ A - B X ₂

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

El costo necesario es de 8 multiplicaciones y 3 sumas costo de readdición de 7 multiplicaciones y 3 sumas, 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

Y3 ₌ −1−0 = −1

Z3 ₌ 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
• GRAMO = ( X ₁ + Y ₁ ) ² - D
• X ₃ = (2 Y ₁ − GRAMO ) × ( X ₁ + A + 1)
• Y ₃ = ( GRAMO - 2 X ₁ ) × ( Y ₁ + B + 1)
• Z ₃ = ( X ₁ - Y ₁ ) × ( GRAMO + 2 D )

El coste de este algoritmo es tres multiplicaciones + tres elevaciones al cuadrado + 11 sumas + 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

Eso es, ${\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 llaman coordenadas extendidas . Pueden acelerar la suma y la duplicación. Para tener más información sobre operaciones con las coordenadas extendidas ver:

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 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.
• Curvas retorcidas de arpillera

enlaces externos

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

Notas

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

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 sobre informática. vol. 2162. Springer-Verlag Berlín Heidelberg 2001. págs. 402–410. doi :10.1007/3-540-44709-1_33. ISBN 978-3-540-42521-2.
• NP inteligente (2001). "La forma de Hesse de una curva elíptica". Hardware criptográfico y sistemas integrados: CHES 2001 . Apuntes de conferencias sobre informática. vol. 2162. Springer-Verlag Berlín Heidelberg 2001. págs. doi :10.1007/3-540-44709-1_11. ISBN 978-3-540-42521-2. S2CID  30487134.