Curva jacobiana

En matemáticas , la curva de Jacobi es una representación de una curva elíptica diferente de la habitual definida por la ecuación de Weierstrass . A veces se utiliza en criptografía en lugar de la forma de Weierstrass porque puede proporcionar una defensa contra ataques de estilo de análisis de potencia simple y diferencial (SPA); es posible, de hecho, utilizar la fórmula de adición general también para duplicar un punto en una curva elíptica de esta forma: de esta manera, las dos operaciones se vuelven indistinguibles de alguna información del canal lateral. ^[1] La curva de Jacobi también ofrece una aritmética más rápida en comparación con la curva de Weierstrass.

La curva de Jacobi puede ser de dos tipos: la intersección de Jacobi , que está dada por la intersección de dos superficies, y la cuártica de Jacobi .

Curvas elípticas: conceptos básicos

Dada una curva elíptica, es posible hacer algunas "operaciones" entre sus puntos: por ejemplo, se pueden sumar dos puntos P y Q obteniendo el punto P + Q que pertenece a la curva; dado un punto P en la curva elíptica, es posible "duplicar" P, es decir, encontrar [2] P = P + P (los corchetes se usan para indicar [n]P , el punto P sumado n veces), y también encontrar la negación de P , es decir, encontrar – P . De esta manera, los puntos de una curva elíptica forman un grupo . Nótese que el elemento identidad de la operación de grupo no es un punto en el plano afín, solo aparece en las coordenadas proyectivas: entonces O = (0: 1: 0) es el "punto en el infinito", es decir, el elemento neutro en la ley de grupo . Las fórmulas de suma y duplicación también son útiles para calcular [n]P , el n -ésimo múltiplo de un punto P en una curva elíptica: esta operación se considera la más importante en criptografía de curva elíptica .

Una curva elíptica E , sobre un cuerpo K se puede poner en la forma de Weierstrass y ² = x ³ + ax + b , con a , b en K . Lo que será de importancia más adelante son los puntos de orden 2 , es decir P en E tal que [2] P = O y P ≠ O . Si P = ( p , 0) es un punto en E , entonces tiene orden 2; más generalmente los puntos de orden 2 corresponden a las raíces del polinomio f(x) = x ³ + ax + b .

A partir de ahora, utilizaremos E _a,b para denotar la curva elíptica con forma de Weierstrass y ² = x ³ + ax + b .

Si E _a,b es tal que el polinomio cúbico x ³ + ax + b tiene tres raíces distintas en K y b = 0 podemos escribir E _a,b en la forma normal de Legendre :

E _a,b : y ² = x(x + 1)(x + j)

En este caso tenemos tres puntos de orden dos: (0, 0), (–1, 0), (– j , 0). En este caso usamos la notación E[j] . Nótese que j puede expresarse en términos de a , b .

Definición: Intersección de Jacobi

Una curva elíptica en P ³ ( K ) se puede representar como la intersección de dos superficies cuadráticas :

${\displaystyle Q:\{Q_{1}(X_{0},X_{1},X_{2},X_{3})=0\}\cap \{Q_{2}(X_{0},X_{1},X_{2},X_{3})=0\}}$

Es posible definir la forma de Jacobi de una curva elíptica como la intersección de dos cuádricas. Sea E _a,b una curva elíptica en forma de Weierstrass, a la que le aplicamos la siguiente función :

${\displaystyle \Phi :(x,y)\mapsto (X,Y,Z,T)=(x,y,1,x^{2})}$

Vemos que el siguiente sistema de ecuaciones se cumple:

${\displaystyle \mathbf {S} :{\begin{cases}X^{2}-TZ=0\\Y^{2}-aXZ-bZ^{2}-TX=0\end{cases}}}$

La curva E[j] corresponde a la siguiente intersección de superficies en P ³ ( K ):

${\displaystyle \mathbf {S} 1:{\begin{cases}X^{2}+Y^{2}-T^{2}=0\\kX^{2}+Z^{2}-T^{2}=0\end{cases}}}$.

El "caso especial", E[0] , la curva elíptica tiene un punto doble y por lo tanto es singular .

S1 se obtiene aplicando a E[j] la transformación :

ψ: E[j] → S1

${\displaystyle (x,y)\mapsto (X,Y,Z,T)=(-2y,x^{2}-j,x^{2}+2jx+j,x^{2}+2x+j)}$

${\displaystyle O=(0:1:0)\mapsto (0,1,1,1)}$

Derecho de grupo

Para S1 , el elemento neutro del grupo es el punto (0, 1, 1, 1), que es la imagen de O = (0:1:0) bajo ψ.

Suma y duplicación

Dados P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) y P ₂ = ( X ₂ , Y ₂ , Z ₂ , T ₂ ), dos puntos en S1 , las coordenadas del punto P ₃ = P ₁ + P ₂ son:

${\displaystyle X_{3}=T_{1}Y_{2}X_{1}Z_{2}+Z_{1}X_{2}Y_{1}T_{2}}$

${\displaystyle Y_{3}=T_{1}Y_{2}Y_{1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}}$

${\displaystyle Z_{3}=T_{1}Z_{1}T_{2}Z_{2}-kX_{1}Y_{1}X_{2}Y_{2}}$

${\displaystyle T_{3}=(T_{1}Y_{2})^{2}+(Z_{1}X_{2})^{2}}$

Estas fórmulas también son válidas para duplicar: basta con que P ₁ = P ₂ . Por lo tanto, sumar o duplicar puntos en S1 son operaciones que requieren 16 multiplicaciones más una multiplicación por una constante ( k ).

También es posible utilizar las siguientes fórmulas para duplicar el punto P ₁ y encontrar P ₃ = [2] P ₁ :

${\displaystyle X_{3}=2Y_{1}T_{1}Z_{1}X_{1}}$

${\displaystyle Y_{3}=(T_{1}Y_{1})^{2}-(T_{1}Z_{1})^{2}+(Z_{1}Y_{1})^{2}}$

${\displaystyle Z_{3}=(T_{1}Z_{1})^{2}-(T_{1}Y_{1})^{2}+(Z_{1}Y_{1})^{2}}$

${\displaystyle T_{3}=(T_{1}Z_{1})^{2}+(T_{1}Y_{1})^{2}-(Z_{1}Y_{1})^{2}}$

Utilizando estas fórmulas se necesitan 8 multiplicaciones para duplicar un punto. Sin embargo, existen “estrategias” aún más eficientes para duplicar que requieren solo 7 multiplicaciones. ^[2] De esta manera es posible triplicar un punto con 23 multiplicaciones; de hecho [3] P ₁ se puede obtener sumando P ₁ con [2] P ₁ con un costo de 7 multiplicaciones para [2] P ₁ y 16 para P ₁ + [2] P ₁ ^[2]

Ejemplo de suma y duplicación

Sea K = R o C y consideremos el caso:

${\displaystyle \mathbf {S} 1:{\begin{cases}X^{2}+Y^{2}-T^{2}=0\\4X^{2}+Z^{2}-T^{2}=0\end{cases}}}$

Consideremos los puntos y : es fácil verificar que P ₁ y P ₂ pertenecen a S1 (basta ver que estos puntos satisfacen ambas ecuaciones del sistema S1 ). ${\displaystyle P_{1}=(1,{\sqrt {3}},0,2)}$ ${\displaystyle P_{2}=(1,2,1,{\sqrt {5}})}$

Utilizando las fórmulas dadas anteriormente para sumar dos puntos, las coordenadas para P ₃ , donde P ₃ = P ₁ + P ₂ son:

${\displaystyle X_{3}=T_{1}Y_{2}X_{1}Z_{2}+Z_{1}X_{2}Y_{1}T_{2}=4}$

${\displaystyle Y_{3}=T_{1}Y_{2}Y_{1}T_{2}-Z_{1}X_{2}X_{1}Z_{2}=4{\sqrt {15}}}$

${\displaystyle Z_{3}=T_{1}Z_{1}T_{2}Z_{2}-kX_{1}Y_{1}X_{2}Y_{2}=-8{\sqrt {3}}}$

${\displaystyle T_{3}=(T_{1}Y_{2})^{2}+(Z_{1}X_{2})^{2}=16}$

El punto resultante es . ${\displaystyle P_{3}=(4,4{\sqrt {15}},-8{\sqrt {3}},16)}$

Con las fórmulas dadas anteriormente para duplicar, es posible encontrar el punto P ₃ = [2] P ₁ :

${\displaystyle X_{3}=2Y_{1}T_{1}Z_{1}X_{1}=0}$

${\displaystyle Y_{3}=(T_{1}Y_{1})^{2}-(T_{1}Z_{1})^{2}+(Z_{1}Y_{1})^{2}=12}$

${\displaystyle Z_{3}=(T_{1}Z_{1})^{2}-(T_{1}Y_{1})^{2}+(Z_{1}Y_{1})^{2}=-12}$

${\displaystyle T_{3}=(T_{1}Z_{1})^{2}+(T_{1}Y_{1})^{2}-(Z_{1}Y_{1})^{2}=12}$

Entonces, en este caso P ₃ = [2] P ₁ = (0, 12, –12, 12).

Negación

Dado el punto P ₁ = ( X ₁ , Y ₁ , Z ₁ , T ₁ ) en S1 , su negación es − P ₁ = (− X ₁ , Y ₁ , Z ₁ , T ₁ )

Adición y duplicación en coordenadas afines

Dados dos puntos afines P ₁ = ( x ₁ , y ₁ , z ₁ ) y P ₂ = ( x ₂ , y ₂ , z ₂ ), su suma es un punto P ₃ con coordenadas:

${\displaystyle x_{3}={\frac {y_{2}x_{1}z_{2}+z_{1}x_{2}y_{1}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}}$

${\displaystyle y_{3}={\frac {y_{2}y_{1}-z_{1}x_{2}x_{1}z_{2}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}}$

${\displaystyle z_{3}={\frac {z_{1}z_{2}-ax_{1}y_{1}x_{2}y_{2}}{(y_{2}^{2}+(z_{1}x_{2})^{2})}}}$

Estas fórmulas son válidas también para duplicar con la condición P ₁ = P ₂ .

Coordenadas extendidas

Existe otro tipo de sistema de coordenadas con el que se puede representar un punto en la intersección de Jacobi. Dada la siguiente curva elíptica en forma de intersección de Jacobi:

${\displaystyle \mathbf {S} 1:{\begin{cases}x^{2}+y^{2}=1\\kx^{2}+z^{2}=1\end{cases}}}$

Las coordenadas extendidas describen un punto P = (x, y, z) con las variables X, Y, Z, T, XY, ZT , donde:

${\displaystyle x=X/T}$

${\displaystyle y=Y/T}$

${\displaystyle z=Z/T}$

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

${\displaystyle ZT=Z\cdot T}$

En ocasiones se utilizan estas coordenadas porque son más convenientes (en términos de costo-tiempo) en algunas situaciones específicas. Para obtener más información sobre las operaciones basadas en el uso de estas coordenadas, consulte http://hyperelliptic.org/EFD/g1p/auto-jintesect-extended.html

Definición: Jacobi cuártico

Una ecuación cuártica de Jacobi ${\displaystyle y^{2}=x^{4}-1.9x^{2}+1}$

Una curva elíptica en forma cuártica de Jacobi se puede obtener a partir de la curva E _a,b en forma de Weierstrass con al menos un punto de orden 2. La siguiente transformación f envía cada punto de E _a,b a un punto en las coordenadas de Jacobi, donde (X: Y: Z) = (sX: s ² Y: sZ) .

f: E _a,b → J

${\displaystyle (p,0)\mapsto (0:-1:1)}$

${\displaystyle (x,y)\neq (p,0)\mapsto (2(x-p):(2x+p)(x-p)^{2}-y^{2}:y)}$

${\displaystyle O\mapsto (0:1:1)}$^[3]

Aplicando f a E _a,b , se obtiene una curva en J de la siguiente forma:

${\displaystyle C:\ Y^{2}=eX^{4}-2dX^{2}Z^{2}+Z^{4}}$^[3]

dónde:

${\displaystyle e={\frac {-(3p^{2}+4a)}{16}},\ \ d={\frac {3p}{4}}}$.

son elementos en K . C representa una curva elíptica en la forma cuártica de Jacobi , en coordenadas de Jacobi.

Cuartica de Jacobi en coordenadas afines

La forma general de una curva cuártica de Jacobi en coordenadas afines es:

${\displaystyle y^{2}=ex^{4}+2ax^{2}+1}$,

donde a menudo se supone que e = 1.

Derecho de grupo

El elemento neutro de la ley de grupo de C es el punto proyectivo (0:1:1).

Adición y duplicación en coordenadas afines

Dados dos puntos afines y , su suma es un punto , tal que: ${\displaystyle P_{1}=(x_{1},y_{1})}$ ${\displaystyle P_{2}=(x_{2},y_{2})}$ ${\displaystyle P_{3}=(x_{3},y_{3})}$

${\displaystyle x_{3}={\frac {x_{1}y_{2}+y_{1}x_{2}}{1-e(x_{1}x_{2})^{2}}}}$

${\displaystyle y_{3}={\frac {((1+e(x_{1}x_{2})^{2})(y_{1}y_{2}+2ax_{1}x_{2})+2ex_{1}x_{2}({x_{1}}^{2}+{x_{2}}^{2}))}{(1-e(x_{1}x_{2})^{2})^{2}}}}$

Al igual que en las intersecciones de Jacobi, también en este caso es posible utilizar esta fórmula también para duplicar.

Suma y duplicación en coordenadas proyectivas

Dados dos puntos P ₁ = ( X ₁ : Y ₁ : Z ₁ ) y P ₂ = ( X ₂ : Y ₂ : Z ₂ ) en C′ , las coordenadas para el punto P ₃ = ( X ₃ : Y ₃ : Z ₃ ), donde P ₃ = P ₁ + P ₂ , se dan en términos de P ₁ y P ₂ por las fórmulas:

${\displaystyle X_{3}=X_{1}Z_{1}Y_{2}+Y_{1}X_{2}Z_{2}}$

${\displaystyle Y_{3}=\left(Z_{1}^{2}Z_{2}^{2}+eX_{1}^{2}X_{2}^{2}\right)\left(Y_{1}Y_{2}-2aX_{1}X_{2}Z_{1}Z_{2}\right)\ +\ 2eX_{1}X_{2}Z_{1}Z_{2}\left(X_{1}^{2}Z_{2}^{2}+Z_{1}^{2}X_{2}^{2}\right)}$

${\displaystyle Z_{3}=Z_{1}^{2}Z_{2}^{2}-eX_{1}^{2}X_{2}^{2}}$

Esta fórmula también se puede utilizar para duplicar, con la condición de que P ₂ = P ₁ : de esta manera se obtiene el punto P ₃ = P ₁ + P ₁ = [2] P _{1 .}

El número de multiplicaciones necesarias para sumar dos puntos es 13 más 3 multiplicaciones por constantes: en particular hay dos multiplicaciones por la constante e y una por la constante a .

Existen algunas "estrategias" para reducir las operaciones necesarias para sumar y duplicar puntos: el número de multiplicaciones se puede reducir a 11 más 3 multiplicaciones por constantes (ver ^[4] sección 3 para más detalles).

El número de multiplicaciones se puede reducir trabajando sobre las constantes e y d : la curva elíptica en la forma de Jacobi se puede modificar para tener un número menor de operaciones de suma y duplicación. Así, por ejemplo, si la constante d en C es significativamente pequeña, la multiplicación por d se puede cancelar; sin embargo, la mejor opción es reducir e : si es pequeña, no solo se descuidan una, sino dos multiplicaciones.

Ejemplo de suma y duplicación

Consideremos la curva elíptica E _4,0 , tiene un punto P de orden 2: P = ( p , 0) = (0, 0). Por lo tanto, a = 4, b = p = 0, por lo que tenemos e = 1 y d = 1 y la forma cuártica de Jacobi asociada es:

${\displaystyle C:\ Y^{2}=X^{4}+Z^{4}}$

Eligiendo dos puntos y , es posible encontrar su suma P ₃ = P ₁ + P ₂ utilizando las fórmulas para sumar dadas anteriormente: ${\displaystyle P_{1}=(1:{\sqrt {2}}:1)}$ ${\displaystyle P_{2}=(2:{\sqrt {17}}:1)}$

${\displaystyle X_{3}=1\cdot 1\cdot {\sqrt {17}}+{\sqrt {2}}\cdot 2\cdot 1={\sqrt {17}}+2{\sqrt {2}}}$

${\displaystyle Y_{3}=\left(1^{2}\cdot 1^{2}+1\cdot 1^{2}\cdot 2^{2}\right)\left({\sqrt {2}}\cdot {\sqrt {17}}-2\cdot 0\cdot 1\cdot 2\cdot 1\cdot 1\right)+2\cdot 1\cdot 1\cdot 2\cdot 1\cdot 1\left(1^{2}\cdot 1^{2}+1^{2}\cdot 2^{2}\right)=5{\sqrt {34}}+20}$

${\displaystyle Z_{3}=1^{2}\cdot 1^{2}-1\cdot 1^{2}\cdot 2^{2}=-3}$.

Entonces

${\displaystyle P_{3}=({\sqrt {17}}+2{\sqrt {2}}:5{\sqrt {34}}+20:-3)}$.

Utilizando las mismas fórmulas se obtiene el punto P ₄ = [2] P _{1 :}

${\displaystyle X_{3}=1\cdot 1\cdot {\sqrt {2}}+{\sqrt {2}}\cdot 1\cdot 1=2{\sqrt {2}}}$

${\displaystyle Y_{3}=\left(1+1\cdot 1\right)\left({\sqrt {2}}\cdot {\sqrt {2}}-2\cdot 0\cdot 1\cdot 1\cdot 1\cdot 1\right)+2\cdot 1\left(1^{2}\cdot 1^{2}+1^{2}\cdot 1^{2}\right)=8}$

${\displaystyle Z_{3}=1^{2}\cdot 1^{2}-1\cdot 1^{2}\cdot 1^{2}=0}$

Entonces

${\displaystyle P_{4}=(2{\sqrt {2}}:8:0)}$.

Negación

La negación de un punto P ₁ = ( X ₁ : Y ₁ : Z ₁ ) es: − P ₁ = (− X ₁ : Y ₁ : Z ₁ )

Coordenadas alternativas para la cuártica de Jacobi

Existen otros sistemas de coordenadas que pueden utilizarse para representar un punto en una cuártica de Jacobi: se utilizan para obtener cálculos rápidos en ciertos casos. Para más información sobre el coste de tiempo requerido en las operaciones con estas coordenadas, consulte http://hyperelliptic.org/EFD/g1p/auto-jquartic.html

Dado un cuártico de Jacobi afín

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

Las coordenadas XXYZZ orientadas a la duplicación introducen un parámetro de curva adicional c que satisface a ² + c ² = 1 y representan un punto (x, y) como (X, XX, Y, Z, ZZ, R) , tal que:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^{2}}$

${\displaystyle ZZ=Z^{2}}$

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

Las coordenadas XYZ orientadas a la duplicación , con el mismo supuesto adicional ( a ² + c ² = 1), representan un punto (x, y) con (X, Y, Z) que satisface las siguientes ecuaciones:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/Z^{2}}$

Utilizando las coordenadas XXYZZ no hay ninguna suposición adicional, y representan un punto (x, y) como (X, XX, Y, Z, ZZ) tal que:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^{2}}$

${\displaystyle ZZ=Z^{2}}$

mientras que las coordenadas XXYZZR representan (x, y) como (X, XX, Y, Z, ZZ, R) tal que:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/ZZ}$

${\displaystyle XX=X^{2}}$

${\displaystyle ZZ=Z^{2}}$

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

con las coordenadas XYZ el punto (x, y) viene dado por (X, Y, Z) , con:

${\displaystyle x=X/Z}$

${\displaystyle y=Y/Z^{2}}$.

Véase también

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. Olivier Billet, El modelo de Jacobi de una curva elíptica y análisis de canal lateral
2. PYLiardet y NPSmart, Prevención de SPA/DPA en sistemas ECC utilizando el formulario Jacobi , pág. 397
3. Olivier Billet y Marc Joye, El modelo de Jacobi de una curva elíptica y análisis de canal lateral , pág. 37-38
4. Sylvain Duquesne, Mejora de la aritmética de curvas elípticas en el modelo de Jacobi -I3M, (UMR CNRS 5149) y Lirmm, (UMR CNRS 5506), Universite Montpellier II

Referencias

• Olivier Billet, Marc Joye (2003). "El modelo de Jacobi de una curva elíptica y el análisis de canal lateral". El modelo de Jacobi de una curva elíptica y el análisis de canal lateral . Apuntes de clase en informática. Vol. 2643. Springer-Verlag Berlin Heidelberg 2003. págs. 34–42. doi :10.1007/3-540-44828-4_5. ISBN 978-3-540-40111-7.
• PY Liardet, NP Smart (2001). "Prevención de SPA/DPA en sistemas ECC utilizando la forma de Jacobi". Hardware criptográfico y sistemas integrados — CHES 2001. Apuntes de clase en informática. Vol. 2162. Springer-Verlag Berlin Heidelberg 2001. págs. 391–401. doi :10.1007/3-540-44709-1_32. ISBN 978-3-540-42521-2. Número de identificación del sujeto  32648481.
• http://hyperelliptic.org/EFD/index.html

Enlaces externos

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