En matemáticas , la curva de Jacobi es una representación de una curva elíptica diferente a la habitual ( 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 de adición general también para doblar un punto en una curva elíptica de esta forma: de esta manera, las dos operaciones se vuelven indistinguibles de alguna información de 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 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, eso significa encontrar [2] P = P + P (los corchetes se usan para indicar [n] P , el punto P suma n veces), y también se encuentra la negación de P , que se encuentran medios - P . De esta forma, los puntos de una curva elíptica forman un grupo . Tenga en cuenta que el elemento de 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", que es el elemento neutral en la ley de grupo . Las fórmulas de sumar y duplicar 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 mayor parte de la criptografía de curva elíptica .
Una curva elíptica E , sobre un campo K se puede poner en la forma Weierstrass y 2 = x 3 + ax + b , con un , b en K . ¿Qué será de importancia más tarde son cuestión de orden 2 , que es P en E tal que [2] 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 3 + ax + b .
De ahora en adelante, usaremos E a, b para denotar la curva elíptica con la forma de Weierstrass y 2 = x 3 + ax + b .
Si E a, b es tal que el polinomio cúbico x 3 + ax + b tiene tres raíces distintas en K , podemos escribir E a, b en la forma normal de Legendre :
- E a, b : y 2 = 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] . 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 3 ( K ) se puede representar como la intersección de dos superficies cuadráticas :
Es posible definir la forma de Jacobi de una curva elíptica como la intersección de dos cuadrículas. Sea E a, b una curva elíptica en la forma de Weierstrass, le aplicamos el siguiente mapa :
Vemos que se cumple el siguiente sistema de ecuaciones :
La curva E [j] corresponde a la siguiente intersección de superficies en P 3 ( K ):
- .
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
Derecho de grupo
Para S1 , el elemento neutral del grupo es el punto (0, 1, 1, 1), que es la imagen de O = (0: 1: 0) debajo de ψ.
Suma y duplicación
Dado P 1 = ( X 1 , Y 1 , Z 1 , T 1 ) y P 2 = ( X 2 , Y 2 , Z 2 , T 2 ), dos puntos en S1 , las coordenadas del punto P 3 = P 1 + P 2 son:
Estas fórmulas también son válidas para duplicar: basta con tener P 1 = P 2 . 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 usar las siguientes fórmulas para duplicar el punto P 1 y encontrar P 3 = [2] P 1 :
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 1 se puede obtener sumando P 1 con [2] P 1 con un costo de 7 multiplicaciones para [2] P 1 y 16 para P 1 + [2] P 1 [2]
Ejemplo de suma y duplicación
Sea K = R o C y considere el caso:
Considere los puntos y : es fácil verificar que P 1 y P 2 pertenecen a S1 (basta con ver que estos puntos satisfacen ambas ecuaciones del sistema S1 ).
Usando las fórmulas dadas arriba para sumar dos puntos, las coordenadas para P 3 , donde P 3 = P 1 + P 2 son:
El punto resultante es .
Con las fórmulas dadas arriba para duplicar, es posible encontrar el punto P 3 = [2] P 1 :
Entonces, en este caso P 3 = [2] P 1 = (0, 12, –12, 12).
Negación
Dado el punto P 1 = ( X 1 , Y 1 , Z 1 , T 1 ) en S1 , su negación es - P 1 = (- X 1 , Y 1 , Z 1 , T 1 )
Suma y duplicación en coordenadas afines
Dados dos puntos afines P 1 = ( x 1 , y 1 , z 1 ) y P 2 = ( x 2 , y 2 , z 2 ), su suma es un punto P 3 con coordenadas:
Estas fórmulas son válidas también para duplicar con la condición P 1 = P 2 .
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:
las coordenadas extendidas describen un punto P = (x, y, z) con las variables X, Y, Z, T, XY, ZT , donde:
A veces se utilizan estas coordenadas, porque son más convenientes (en términos de tiempo-costo) 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: Jacobi quartic
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/6/62/JacobianQuartic.svg/300px-JacobianQuartic.svg.png)
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 2 Y: sZ) .
- f: E a, b → J
- [3]
Aplicando f a E a, b , se obtiene una curva en J de la siguiente forma:
dónde:
- .
son elementos en K . C representa una curva elíptica en la forma cuártica de Jacobi , en coordenadas de Jacobi.
Cuartico de Jacobi en coordenadas afines
La forma general de una curva cuártica de Jacobi en coordenadas afines es:
- ,
donde a menudo se supone e = 1.
Derecho de grupo
El elemento neutral 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:
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 1 = ( X 1 : Y 1 : Z 1 ) y P 2 = ( X 2 : Y 2 : Z 2 ) en C ′ , las coordenadas para el punto P 3 = ( X 3 : Y 3 : Z 3 ), donde P 3 = P 1 + P 2 , se dan en términos de P 1 y P 2 mediante las fórmulas:
Se puede usar esta fórmula también para duplicar, con la condición de que P 2 = P 1 : de esta manera se obtiene el punto P 3 = P 1 + P 1 = [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 d .
Existen algunas "estrategias" para reducir las operaciones requeridas 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 mediante el trabajo en las constantes e y d : la curva elíptica en forma Jacobi puede ser modificado con el fin de tener un número más pequeño de operaciones para añadir y duplicar. 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 solo se ignoran 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 entonces tenemos e = 1 y d = 1 y la forma cuártica de Jacobi asociada es:
Elegir dos puntos y , es posible encontrar su suma P 3 = P 1 + P 2 usando las fórmulas para sumar dadas anteriormente:
- .
Entonces
- .
Utilizando las mismas fórmulas, se obtiene el punto P 4 = [2] P 1 :
Entonces
- .
Negación
La negación de un punto P 1 = ( X 1 : Y 1 : Z 1 ) es: - P 1 = (- X 1 : Y 1 : Z 1 )
Coordenadas alternativas para el cuártico de Jacobi
Existen otros sistemas de coordenadas que se pueden utilizar para representar un punto en un cuartico de Jacobi: se utilizan para obtener cálculos rápidos en determinados casos. Para más información sobre el tiempo-costo requerido en las operaciones con estas coordenadas ver http://hyperelliptic.org/EFD/g1p/auto-jquartic.html
Dado un afín de Jacobi cuartico
las coordenadas XXYZZ orientadas a la duplicación introducen un parámetro de curva adicional c que satisface a 2 + c 2 = 1 y representan un punto (x, y) como (X, XX, Y, Z, ZZ, R) , tal que:
las coordenadas XYZ orientadas a la duplicación , con el mismo supuesto adicional ( a 2 + c 2 = 1), representan un punto (x, y) con (X, Y, Z) que satisface las siguientes ecuaciones:
Usando las coordenadas XXYZZ no hay suposiciones adicionales, y representan un punto (x, y) como (X, XX, Y, Z, ZZ) tal que:
mientras que las coordenadas XXYZZR representan (x, y) como (X, XX, Y, Z, ZZ, R) tal que:
con las coordenadas XYZ el punto (x, y) viene dado por (X, Y, Z) , con:
- .
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 .
Notas
- ^ Olivier Billet, El modelo de Jacobi de una curva elíptica y análisis de canal lateral
- ^ a b P.Y. Liardet y NPSmart, Prevención de SPA / DPA en sistemas ECC usando el formulario Jacobi , pag 397
- ^ a b Olivier Billet y Marc Joye, El modelo Jacobi de una curva elíptica y análisis de canal lateral , pág. 37-38
- ^ Sylvain Duquesne, Mejora de la aritmética de curvas elípticas en el modelo 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 análisis de canal lateral". El modelo de Jacobi de una curva elíptica y el análisis de canal lateral . Apuntes de conferencias en Ciencias de la Computación. 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 el formulario Jacobi". 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. 391–401. doi : 10.1007 / 3-540-44709-1_32 . ISBN 978-3-540-42521-2.
- http://hyperelliptic.org/EFD/index.html
enlaces externos
- http://hyperelliptic.org/EFD/g1p/index.html