Una curva de Montgomery sobre un campo K se define mediante la ecuación
para cierto A , B ∈ K y con B ( A 2 - 4) ≠ 0 .
Generalmente esta curva se considera sobre un campo finito K (por ejemplo, sobre un campo finito de q elementos , K = F q ) con característica diferente de 2 y con A ≠ ± 2 y B ≠ 0 , pero también se consideran sobre el racionales con las mismas restricciones para A y B .
Aritmética de Montgomery
Es posible hacer algunas "operaciones" entre los puntos de una curva elíptica: "sumando" dos puntos consiste en encontrar un tercero tal que ; "duplicar" un punto consiste en calcular(Para obtener más información sobre las operaciones, consulte La ley de grupos ) y más abajo.
Un punto en la curva elíptica en la forma de Montgomery se puede representar en las coordenadas de Montgomery , dónde son coordenadas proyectivas y por .
Observe que este tipo de representación para un punto pierde información: de hecho, en este caso, no hay distinción entre los puntos afines y porque ambos están dados por el punto . Sin embargo, con esta representación es posible obtener múltiplos de puntos, es decir, dado, computar .
Ahora, considerando los dos puntos y : su suma viene dada por el puntocuyas coordenadas son:
Si , entonces la operación se convierte en una "duplicación"; las coordenadas de vienen dadas por las siguientes ecuaciones:
La primera operación considerada arriba ( suma ) tiene un costo de tiempo de 3 M +2 S , donde M denota la multiplicación entre dos elementos generales del campo en el que se define la curva elíptica, mientras que S denota el cuadrado de un elemento general de la campo.
La segunda operación (duplicación) tiene un costo de tiempo de 2 M + 2 S + 1 D , donde D denota la multiplicación de un elemento general por una constante ; observe que la constante es, entonces se puede elegir para tener una D pequeña .
Algoritmo y ejemplo
El siguiente algoritmo representa la duplicación de un punto en una curva elíptica en la forma de Montgomery.
Se asume que . El costo de esta implementación es 1M + 2S + 1 * A + 3add + 1 * 4. Aquí M denota las multiplicaciones requeridas, S indica los cuadrados y a se refiere a la multiplicación por A.
Ejemplo
Dejar ser un punto en la curva . En coordenadas, con , .
Luego:
El resultado es el punto tal que .
Adición
Dados dos puntos , en la curva de Montgomery en coordenadas afines, el punto representa, geométricamente el tercer punto de intersección entre y la linea que pasa por y . Es posible encontrar las coordenadas de , de la siguiente manera:
1) considere una línea genérica en el plano afín y dejarlo pasar y (imponer la condición), de esta manera, se obtiene y ;
2) interseca la línea con la curva , sustituyendo el variable en la ecuación de la curva con ; Se obtiene la siguiente ecuación de tercer grado :
Como se ha observado anteriormente, esta ecuación tiene tres soluciones que corresponden a la coordenadas de , y . En particular, esta ecuación se puede reescribir como:
3) Comparando los coeficientes de las dos ecuaciones idénticas dadas anteriormente, en particular los coeficientes de los términos de segundo grado, se obtiene:
.
Entonces, se puede escribir en términos de , , , , como:
4) Para encontrar el coordenada del punto basta con sustituir el valor En la linea . Tenga en cuenta que esto no le dará el puntodirectamente. De hecho, con este método se encuentran las coordenadas del punto tal que , pero si se necesita el punto resultante de la suma entre y , entonces es necesario observar que: si y solo si . Entonces, dado el punto, es necesario encontrar , pero esto se puede hacer fácilmente cambiando el signo a la coordenada de . En otras palabras, será necesario cambiar el signo del coordenada obtenida sustituyendo el valor en la ecuación de la recta.
Reanudando, las coordenadas del punto , están:
Duplicación
Dado un punto en la curva de Montgomery , el punto Representa geométricamente el tercer punto de intersección entre la curva y la recta tangente a ; entonces, para encontrar las coordenadas del puntoes suficiente seguir el mismo método dado en la fórmula de adición; sin embargo, en este caso, la recta y = lx + m tiene que ser tangente a la curva en, Así que si con
entonces el valor de l , que representa la pendiente de la recta, viene dado por:
Teorema (i) Cada curva de Edwards torcida es biracionalmente equivalente a una curva de Montgomery sobre. En particular, la retorcida curva de Edwards es biracionalmente equivalente a la curva de Montgomery dónde , y .
Tenga en cuenta que esta equivalencia entre las dos curvas no es válida en todas partes: de hecho, el mapa no está definido en los puntos o de El .
Equivalencia con curvas de Weierstrass
Cualquier curva elíptica se puede escribir en forma de Weierstrass. En particular, la curva elíptica en la forma de Montgomery
:
se puede transformar de la siguiente manera: dividir cada término de la ecuación por por Y sustituir las variables x e y , con y respectivamente, para obtener la ecuación
Para obtener una forma corta de Weierstrass a partir de aquí, es suficiente reemplazar u con la variable:
finalmente, esto da la ecuación:
Por lo tanto, el mapeo se da como
:
Por el contrario, una curva elíptica sobre el campo base en forma de Weierstrass
:
se puede convertir a la forma de Montgomery si y solo si tiene un orden divisible por cuatro y cumple las siguientes condiciones: [3]
tiene al menos una raíz ; y
es un residuo cuadrático en .
Cuando se cumplen estas condiciones, entonces por tenemos el mapeo
^Daniel J. Bernstein , Peter Birkner, Marc Joye, Tanja Lange y Christiane Peters (2008). "Curvas torcidas de Edwards". Progreso en Criptología - AFRICACRYPT 2008 . Apuntes de conferencias en Ciencias de la Computación. 5023 . Springer-Verlag Berlín Heidelberg. págs. 389–405. doi : 10.1007 / 978-3-540-68164-9_26 . ISBN 978-3-540-68159-5.CS1 maint: varios nombres: lista de autores ( enlace )
^Katsuyuki Okeya, Hiroyuki Kurumatani y Kouichi Sakurai (2000). Curvas elípticas con la forma de Montgomery y sus aplicaciones criptográficas . Criptografía de clave pública (PKC2000). doi : 10.1007 / 978-3-540-46588-1_17 .CS1 maint: varios nombres: lista de autores ( enlace )
Referencias
Peter L. Montgomery (1987). "Aceleración de los métodos de factorización Pollard y la curva elíptica" . Matemáticas de la Computación . 48 (177): 243-264. doi : 10.2307 / 2007888 . JSTOR 2007888 .
Daniel J. Bernstein , Peter Birkner, Marc Joye, Tanja Lange y Christiane Peters (2008). "Curvas torcidas de Edwards". Progreso en Criptología - AFRICACRYPT 2008 . Apuntes de conferencias en Ciencias de la Computación. 5023 . Springer-Verlag Berlín Heidelberg. págs. 389–405. doi : 10.1007 / 978-3-540-68164-9_26 . ISBN 978-3-540-68159-5.CS1 maint: varios nombres: lista de autores ( enlace )
Wouter Castryck; Steven Galbraith; Reza Rezaeian Farashahi (2008). "Aritmética eficiente en curvas elípticas utilizando una representación mixta de Edwards-Montgomery" (PDF) . Cite journal requiere |journal=( ayuda )
enlaces externos
Curvas de género 1 sobre campos de características grandes