curva jacobiana

En matemáticas , la curva de Jacobi es una representación de una curva elíptica diferente a la habitual definida por la ecuación de Weierstrass . A veces se utiliza en criptografía en lugar de la forma Weierstrass porque puede proporcionar una defensa contra ataques de estilo de análisis de poder (SPA) simples y diferenciales ; De hecho, es posible utilizar la fórmula general de la suma 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 una intersección de dos superficies, y la cuartica 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 forma, los puntos de una curva elíptica forman un grupo . Tenga en cuenta que el elemento identidad de la operación grupal 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 campo K se puede expresar en la forma de Weierstrass y 2 ⁼ x 3 ⁺ ax + b , con a , b en K. Lo que será importante más adelante es el punto 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; de manera más general, los puntos de orden 2 corresponden a las raíces del polinomio f(x) = x ³ + ax + b .

De ahora en adelante, usaremos E _a,b para denotar la curva elíptica con la 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 :

mi _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 utilizamos la notación E[j] . Tenga en cuenta que j se puede expresar 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 cuádricas :

${\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 la forma de Weierstrass, le aplicamos el siguiente mapa :

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

Vemos que se cumple el siguiente sistema de ecuaciones :

${\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 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 tener P ₁ = P ₂ . Entonces, 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}}$

Usando 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 forma 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 considere 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 comprobar que P ₁ y P ₂ pertenecen a S1 (basta con 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}})}$

Usando las fórmulas dadas anteriormente para sumar dos puntos, las coordenadas de 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 ₁ )

Suma 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 la 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}$

A veces se utilizan estas coordenadas porque son más convenientes (en términos de tiempo-coste) 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-jintersect-extended.html

Definición: cuártico de Jacobi

Un cuartico de ecuación de Jacobi ${\displaystyle y^{2}=x^{4}-1.9x^{2}+1}$

Se puede obtener una curva elíptica en forma cuártica de Jacobi a partir de la curva E _a,b en la 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: mi _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 forma cuartica de Jacobi , en coordenadas de Jacobi.

Jacobi cuártico 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 e = 1.

derecho de grupo

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

Suma 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 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 del punto P ₃ = ( X ₃ : Y ₃ : Z ₃ ), donde P ₃ = P ₁ + P ₂ , vienen dados en términos de P ₁ y P ₂ mediante 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}}$

Se puede utilizar esta fórmula también para duplicar, con la condición de que P ₂ = P ₁ : de esta forma 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 (consulte ^[4] sección 3 para obtener más detalles).

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

Ejemplo de suma y duplicación

Considere 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, 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 ₂ usando las fórmulas de suma 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 el cuártico de Jacobi

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

Dado un cuartico 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 satisfacen las siguientes ecuaciones:

${\displaystyle x=X/Z}$

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

Usando las coordenadas XXYZZ no hay suposiciones adicionales, 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}}$.

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 .

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 mediante el formulario Jacobi , página 397
3. Olivier Billet y Marc Joye, El modelo de Jacobi de una curva elíptica y análisis de canal lateral , páginas 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), Universidad Montpellier II

Referencias

• Olivier Billet, Marc Joye (2003). "El modelo de Jacobi de una curva elíptica y análisis de canal lateral". El modelo de Jacobi de una curva elíptica y el análisis de canal lateral . Apuntes de conferencias sobre informática. vol. 2643. Springer-Verlag Berlín Heidelberg 2003. págs. 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 mediante el formulario Jacobi". 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_32. ISBN 978-3-540-42521-2. S2CID  32648481.
• http://hyperelliptic.org/EFD/index.html

enlaces externos

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