En matemáticas , las curvas de Edwards son una familia de curvas elípticas estudiadas por Harold Edwards en 2007. El concepto de curvas elípticas sobre campos finitos se utiliza ampliamente en la criptografía de curvas elípticas . Las aplicaciones de las curvas de Edwards a la criptografía fueron desarrolladas por Daniel J. Bernstein y Tanja Lange : señalaron varias ventajas de la forma de Edwards en comparación con la forma más conocida de Weierstrass .
Definición
La ecuación de una curva de Edwards sobre un campo K que no tiene la característica 2 es:
para algunos escalares . También el siguiente formulario con los parámetros c y d se denomina una curva de Edwards:
donde c , d ∈ K con cd (1 - c 4 · d ) ≠ 0.
Cada curva de Edwards es biracionalmente equivalente a una curva elíptica en forma de Weierstrass y, por lo tanto, admite una ley de grupo algebraica una vez que se elige un punto para que sirva como elemento neutral. Si K es finito, entonces una fracción considerable de todas las curvas elípticas sobre K se puede escribir como curvas de Edwards. A menudo, las curvas elípticas en forma de Edwards se definen con c = 1, sin pérdida de generalidad. En las siguientes secciones, se supone que c = 1.
La ley de grupo
(Ver también ley de grupo de curvas de Weierstrass )
Cada curva de Edwards sobre el campo K con característica no igual a 2 con es biracionalmente equivalente a una curva elíptica sobre el mismo campo: , dónde y el punto se asigna a la infinidad O . Este mapeo biracional induce un grupo en cualquier curva de Edwards.
Ley de adición de Edwards
En cualquier curva elíptica, la suma de dos puntos viene dada por una expresión racional de las coordenadas de los puntos, aunque en general se pueden necesitar varias fórmulas para cubrir todos los pares posibles. Para la curva de Edwards, tomando el elemento neutro como el punto (0, 1), la suma de los puntos y está dado por la fórmula
La inversa de cualquier punto es . El punto tiene orden 2, y los puntos tiene orden 4. En particular, una curva de Edwards siempre tiene un punto de orden 4 con coordenadas en K .
Si d no es un cuadrado en K y, entonces no hay puntos excepcionales: los denominadores y son siempre distintos de cero. Por lo tanto, la ley de adición Edwards se completa cuando D no es un cuadrado en K . Esto significa que las fórmulas funcionan para todos los pares de puntos de entrada en la curva de Edwards sin excepciones para duplicar, sin excepción para el elemento neutral, sin excepción para negativos, etc. [1] En otras palabras, se define para todos los pares de puntos de entrada en la curva de Edwards sobre K y el resultado da la suma de los puntos de entrada.
Si d es un cuadrado en K , entonces la misma operación puede tener puntos excepcionales, es decir, puede haber pares de puntos tal que uno de los denominadores se convierta en cero: o .
Una de las características atractivas de la ley de Adición de Edwards es que está fuertemente unificada, es decir, también se puede usar para duplicar un punto, simplificando la protección contra ataques de canal lateral . La fórmula de adición anterior es más rápida que otras fórmulas unificadas y tiene la fuerte propiedad de estar completa [1]
Ejemplo de ley de la adición :
Considere la curva elíptica en la forma de Edwards con d = 2
y el punto en eso. Es posible probar que la suma de P 1 con el elemento neutro (0,1) da nuevamente P 1 . De hecho, usando la fórmula dada arriba, las coordenadas del punto dadas por esta suma son:
Un análogo en el círculo.
Para comprender mejor el concepto de "suma" de puntos en una curva, el grupo circular clásico ofrece un buen ejemplo:
toma el círculo de radio 1
y considere dos puntos P 1 = (x 1 , y 1 ), P 2 = (x 2 , y 2 ) en él. Sean α 1 y α 2 los ángulos tales que:
La suma de P 1 y P 2 está, pues, dada por la suma de "sus ángulos". Es decir, el punto P 3 = P 1 + P 2 es un punto en el círculo con coordenadas (x 3 , y 3 ), donde:
De esta manera, la fórmula de suma para puntos en el círculo de radio 1 es:
- .
Significado de la geometría de la suma de puntos en las curvas de Edwards
Los puntos de una curva elíptica forman un grupo abeliano: se pueden sumar puntos y tomar múltiplos enteros de un solo punto. Cuando una curva elíptica se describe mediante una ecuación cúbica no singular, entonces la suma de dos puntos P y Q , denotado P + Q , está directamente relacionada con tercer punto de intersección entre la curva y la línea que pasa a través de P y Q .
El mapeo biracional entre una curva de Edward y la curva elíptica correspondiente mapea las líneas rectas en secciones cónicas [2]. En otras palabras, para las curvas de Edwards, los tres puntos, y yacía sobre una hipérbola .
Dados dos puntos distintos de no identidad , los coeficientes de la forma cuadrática son (hasta escalares):
,
,
En el caso de doblar un punto el punto inverso descansa sobre la cónica que toca la curva en el punto . Los coeficientes de la forma cuadrática, que define la cónica, son (hasta escalares):
,
,
Coordenadas proyectivas homogéneas
En el contexto de la criptografía, se utilizan coordenadas homogéneas para evitar inversiones de campo que aparecen en la fórmula afín. Para evitar inversiones en las fórmulas de adición originales de Edwards, la ecuación de la curva se puede escribir en coordenadas proyectivas como:
.
Un punto proyectivo corresponde al punto afín en la curva de Edwards.
El elemento de identidad está representado por . El inverso de es .
La fórmula de suma en coordenadas homogéneas viene dada por:
dónde
Algoritmo
La suma de dos puntos en la curva de Edwards podría calcularse de manera más eficiente [3] en el formulario Edwards extendido , dónde :
Duplicación
La duplicación se puede realizar con exactamente la misma fórmula que la suma. La duplicación se refiere al caso en el que las entradas ( x 1 , y 1 ) y ( x 2 , y 2 ) son iguales.
Doblar un punto :
Los denominadores se simplificaron con base en la ecuación de la curva . Se logra una mayor aceleración mediante la como . Esto reduce el costo de duplicar en coordenadas homomórficas a 3 M + 4 S + 3 C + 6 a , mientras que la suma general cuesta 10 M + 1 S + 1 C + 1 D + 7 a . Aquí M son multiplicaciones de campo, S es cuadratura de campo, D es el costo de multiplicar por el parámetro de curva d , y a es la suma de campo.
- Ejemplo de duplicación
Como en el ejemplo anterior para la ley de la adición, considere la curva de Edwards con d = 2:
y el punto . Las coordenadas del punto están:
El punto obtenido al doblar P es entonces.
Adición mixta
La suma mixta es el caso cuando se sabe que Z 2 es 1. En tal caso, A = Z 1 . Z 2 se puede eliminar y el costo total se reduce a 9 M +1 S +1 C +1 D +7 a
Algoritmo
A = Z 1 . Z 2 // en otras palabras, A = Z 1
B = Z 1 2
C = X 1 .X 2
D = Y 1 . Y 2
E = d . C . D
F = BE
G = B + E
X 3 = A . F ((X I + Y 1 ) . (X 2 + Y 2 ) -CD)
Y 3 = A . G . (CORRIENTE CONTINUA)
Z 3 = C . F . GRAMO
Triplicando
Se puede triplicar primero doblando el punto y luego agregando el resultado a sí mismo. Aplicando la ecuación de la curva como al duplicar, obtenemos
Hay dos conjuntos de fórmulas para esta operación en coordenadas estándar de Edwards. El primero cuesta 9 M + 4 S mientras que el segundo necesidades 7 M + 7 S . Si la relación S / M es muy pequeña, específicamente por debajo de 2/3, entonces el segundo conjunto es mejor, mientras que para relaciones más grandes se prefiere el primero. [4] Usando las fórmulas de suma y duplicación (como se mencionó anteriormente), el punto ( X 1 : Y 1 : Z 1 ) se calcula simbólicamente como 3 ( X 1 : Y 1 : Z 1 ) y se compara con ( X 3 : Y 3 : Z 3 )
- Ejemplo de triplicar
Dando la curva de Edwards con d = 2, y el punto P 1 = (1,0), el punto 3P 1 tiene coordenadas:
Entonces, 3P 1 = (- 1,0) = P- 1 . Este resultado también se puede encontrar considerando el ejemplo de duplicación: 2P 1 = (0,1), entonces 3P 1 = 2P 1 + P 1 = (0, -1) + P 1 = -P 1 .
- Algoritmo
A = X 1 2
B = Y 1 2
C = (2Z 1 ) 2
D = A + B
E = D 2
F = 2D. (AB)
G = EB.C
H = EA.C
Yo = F + H
J = FG
X 3 = GJX1
Y 3 = HIY1
Z 3 = IJZ1
Esta fórmula cuesta 9 M + 4 S
Coordenadas de Edwards invertidas
Bernstein y Lange introdujeron un sistema de coordenadas aún más rápido para curvas elípticas llamado coordenadas de Edward invertidas [5] en las que las coordenadas ( X : Y : Z ) satisfacen la curva ( X 2 + Y 2 ) Z 2 = ( dZ 4 + X 2 Y 2 ) y corresponde al punto afín ( Z / X , Z / Y ) en la curva de Edwards x 2 + y 2 = 1 + dx 2 y 2 con XYZ ≠ 0.
Las coordenadas de Edwards invertidas , a diferencia de las coordenadas de Edwards estándar, no tienen fórmulas de suma completas: algunos puntos, como el elemento neutro, deben manejarse por separado. Pero las fórmulas de adición todavía tienen la ventaja de una fuerte unificación: se pueden usar sin cambios para duplicar un punto.
Para obtener más información sobre las operaciones con estas coordenadas, consulte http://hyperelliptic.org/EFD/g1p/auto-edwards-inverted.html
Coordenadas extendidas para las curvas de Edward
Existe otro sistema de coordenadas con el que se puede representar una curva de Edwards; estas nuevas coordenadas se denominan coordenadas extendidas [6] y son incluso más rápidas que las coordenadas invertidas. Para más información sobre el tiempo-costo requerido en las operaciones con estas coordenadas ver: http://hyperelliptic.org/EFD/g1p/auto-edwards.html
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
- ^ a b Daniel. J. Bernstein, Tanja Lange, pág. 3, adición y duplicación más rápida en curvas elípticas
- ^ Christophe Arene; Tanja Lange; Michael Naehrig; Christophe Ritzenthaler (2009). "Cálculo más rápido del emparejamiento Tate" . arXiv : 0904.0854 . Código bibliográfico : 2009arXiv0904.0854A . Consultado el 28 de febrero de 2010 .
- ^ Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter y Ed Dawson. Las curvas retorcidas de Edwards revisadas . En ASIACRYPT 2008, páginas 326–343, 2008
- ^ Bernstein et al., Optimización de la multiplicación escalar simple de curva elíptica de base doble
- ^ Daniel J. Bernstein. Tanja Lange, pág.2, coordenadas de Edward invertidas
- ^ H. Hisil, KK Wong, G. Carter, E. Dawson Operaciones de grupo más rápidas en curvas elípticas
Referencias
- Bernstein, Daniel ; Lange, Tanja (2007),Suma y duplicación más rápidas en curvas elípticas (PDF)
- Edwards, Harold M. (9 de abril de 2007), "una forma normal para curvas elípticas", Boletín de la American Mathematical Society , 44 (3): 393-422, doi : 10.1090 / s0273-0979-07-01153-6 , ISSN 0002-9904
- Operaciones grupales más rápidas en curvas elípticas , H. Hisil, KK Wong, G. Carter, E. Dawson
- DJBernstein, P. Birkner. T. Lange, C. Peter,Optimización de la multiplicación escalar simple de curva elíptica de base doble (PDF)CS1 maint: varios nombres: lista de autores ( enlace )
- Washington, Lawrence C. (2008), Curvas elípticas: Teoría de números y criptografía , Matemáticas discretas y sus aplicaciones (2a ed.), Chapman & Hall / CRC, ISBN 978-1-4200-7146-7
- Bernstein, Daniel ; Coordenadas de Lange, Tanja, Edwards invertido (PDF)
enlaces externos
- http://hyperelliptic.org/EFD/g1p/index.html
- http://hyperelliptic.org/EFD/g1p/auto-edwards.html