La multiplicación escalar de la curva elíptica es la operación de agregar sucesivamente un punto a lo largo de una curva elíptica a sí misma repetidamente. Se utiliza en criptografía de curva elíptica (ECC) como un medio para producir una función unidireccional . La literatura presenta esta operación como una multiplicación escalar , escrita en forma hessiana de una curva elíptica . Un nombre generalizado para esta operación es también multiplicación de puntos de curva elíptica , pero esto puede dar la impresión errónea de ser una multiplicación entre dos puntos.
Lo esencial
Dada una curva, E , definida a lo largo de alguna ecuación en un campo finito (como E : y 2 = x 3 + ax + b ), la multiplicación de puntos se define como la suma repetida de un punto a lo largo de esa curva. Denotar como nP = P + P + P + ... + P para algunos escalar (número entero) n y un punto P = ( x , y ) que se encuentra en la curva, E . Este tipo de curva se conoce como curva de Weierstrass.
La seguridad de la ECC moderna depende de la intratabilidad de determinar n a partir de Q = nP dados los valores conocidos de Q y P si n es grande (conocido como problema de logaritmo discreto de curva elíptica por analogía con otros sistemas criptográficos ). Esto se debe a que la suma de dos puntos en una curva elíptica (o la adición de un punto a sí misma) produce un tercer punto en la curva elíptica cuya ubicación no tiene una relación inmediatamente obvia con las ubicaciones de los dos primeros, y esto se repite muchas veces. over produce un punto nP que puede estar esencialmente en cualquier lugar. Intuitivamente, esto no es diferente al hecho de que si tuvieras un punto P en un círculo, agregar 42.57 grados a su ángulo puede ser un punto "no muy lejos" de P , pero agregar 1000 o 1001 veces 42.57 grados producirá un punto que puede estar en cualquier parte del círculo. Por lo tanto, revertir este proceso, es decir, dados Q = nP y P y determinar n , solo puede hacerse probando todos los n posibles, un esfuerzo que es computacionalmente intratable si n es grande.
Operaciones puntuales
Hay tres operaciones comúnmente definidas para puntos de curvas elípticas: suma, duplicación y negación.
Apunta al infinito
El punto en el infinito es el elemento de identidad de la aritmética de curvas elípticas. Agregarlo a cualquier punto da como resultado ese otro punto, incluido agregar un punto en el infinito a sí mismo. Es decir:
El punto en el infinito también se escribe como 0 .
Negación puntual
La negación del punto es encontrar un punto tal, que agregarlo a sí mismo dará como resultado un punto en el infinito ().
Para curvas elípticas que es un punto con la misma coordenada x pero negada coordenada y :
Suma de puntos
Con 2 puntos distintos, P y Q , la adición se define como la negación del punto que resulta de la intersección de la curva, E , y la línea recta definida por los puntos P y Q , dando el punto, R .
- .
Suponiendo que la curva elíptica, E , está dada por y 2 = x 3 + ax + b , esto se puede calcular como:
Estas ecuaciones son correctas cuando ningún punto es el punto en el infinito, . Esto es importante para el algoritmo de verificación ECDSA donde el valor hash podría ser cero.
Duplicación de puntos
Donde los puntos P y Q son coincidentes (en las mismas coordenadas), la suma es similar, excepto que no hay una línea recta bien definida que pase por P , por lo que la operación se cierra usando el caso límite, la tangente a la curva, E , en P .
Esto se calcula como se indicó anteriormente, excepto con:
donde a es de la ecuación definitoria de la curva, E , arriba.
Multiplicación de puntos
La forma sencilla de calcular una multiplicación de puntos es mediante la suma repetida. Sin embargo, este es un enfoque completamente exponencial para calcular la multiplicación.
Doble y sume
El método más simple es el método de doble y suma, [1] similar a multiplicar y cuadrado en exponenciación modular. El algoritmo funciona de la siguiente manera:
Para calcular sP , comience con la representación binaria de s :, dónde .
Algoritmo iterativo, índice decreciente:
vamos s; # escalar arbitrario deja res = ; # punto neutro sea i = s. longitud; #No. de bits en s mientras que i> = 0: resultado = res + res; #doble si s [i--]: resultado = res + P; #agregar
Tenga en cuenta que este método es vulnerable al análisis de tiempos. Consulte Montgomery Ladder a continuación para ver un enfoque alternativo.
Una forma alternativa de escribir lo anterior como función recursiva es
f (P, d) es si d = 0 entonces return 0 # cálculo completo de lo contrario, si d = 1 entonces volver P de lo contrario, si d mod 2 = 1 entonces return point_add (P, f (P, d - 1)) # suma cuando d es impar demás return f (point_double (P), d / 2) # doblando cuando d es par
donde f es la función para multiplicar, P es la coordenada para multiplicar, d es el número de veces que se suman las coordenadas. Ejemplo: 100P se puede escribir como 2 (2 [P + 2 (2 [2 (P + 2P)])]) y, por lo tanto, requiere operaciones dobles de seis puntos y operaciones de suma de dos puntos. 100P sería igual af (P, 100) .
Este algoritmo requiere iteraciones log 2 ( d ) de duplicación y suma de puntos para calcular la multiplicación completa de puntos. Hay muchas variaciones de este algoritmo, como el uso de una ventana, una ventana deslizante, NAF, NAF-w, cadenas vectoriales y escalera de Montgomery.
Método de ventana
En la versión de ventana de este algoritmo, [1] uno selecciona un tamaño de ventana wy calcula todos valores de por . El algoritmo ahora usa la representación y se convierte en
Q ← 0 porque yo de ma 0 hago Q ← point_double_repeat (Q, w) si d i > 0 entonces Q ← point_add (Q, d i P) # usando el valor precalculado de d i P volver Q
Este algoritmo tiene la misma complejidad que el enfoque de duplicar y agregar con la ventaja de utilizar menos adiciones de puntos (que en la práctica son más lentas que duplicar). Típicamente, el valor de w se elige a ser bastante pequeño haciendo que el pre-cálculo etapa un componente trivial del algoritmo. Para las curvas recomendadas por NIST,suele ser la mejor selección. Toda la complejidad de un número de n bits se mide como el punto se duplica y adiciones de puntos.
Método de ventana corrediza
En la versión de ventana deslizante, buscamos intercambiar adiciones de puntos por dobles de puntos. Calculamos una tabla similar a la de la versión con ventana, excepto que solo calculamos los puntos por . Efectivamente, solo estamos calculando los valores para los que se establece el bit más significativo de la ventana. El algoritmo luego usa la representación original de doble y suma de.
Q ← 0 Porque yo desde m abajo hasta 0 lo hago si d i = 0 entonces Q ← punto_doble (Q) demás t ← extraer j (hasta w - 1) bits adicionales de d (incluido d i ) i ← i - j si jRealice doble y agregue usando t volver Q demás Q ← point_double_repeat (Q, w) Q ← suma_punto (Q, tP) volver Q
Este algoritmo tiene la ventaja de que la etapa de precálculo es aproximadamente la mitad de compleja que el método de ventana normal, mientras que también intercambia adiciones de puntos más lentas por duplicaciones de puntos. En efecto, hay pocas razones para utilizar el método de ventana sobre este enfoque, excepto que el primero se puede implementar en un tiempo constante. El algoritmo requiere el punto se duplica y como máximo adiciones de puntos.
Método de forma no adyacente w -ary ( w NAF)
En la forma no adyacente, nuestro objetivo es hacer uso del hecho de que la resta de puntos es tan fácil como la suma de puntos para realizar menos (de cualquiera) en comparación con un método de ventana deslizante. El NAF del multiplicando debe calcularse primero con el siguiente algoritmo
yo ← 0 mientras que (d> 0) hacer si (d mod 2) = 1 entonces d i ← d mods 2 w d ← d - d i demás d yo = 0 d ← d / 2 yo ← yo + 1 return (d i − 1 , d i-2 ,…, d 0 )
Donde los mods de la función módulo con signo se definen como
si (d mod 2 w )> = 2 w − 1 return (d mod 2 w ) - 2 w demás volver d mod 2 w
Esto produce el NAF necesario para ahora realizar la multiplicación. Este algoritmo requiere el cálculo previo de los puntos y sus negativos, donde es el punto a multiplicar. En las curvas típicas de Weierstrass, si luego . Entonces, en esencia, los negativos son baratos de calcular. A continuación, el siguiente algoritmo calcula la multiplicación:
Q ← 0 para j ← i - 1 abajo a 0 hacer Q ← punto_doble (Q) si (d j ! = 0) Q ← suma_punto (Q, d j G) volver Q
La wNAF garantiza que en promedio habrá una densidad de adiciones de puntos (ligeramente mejor que la ventana sin firmar). Requiere duplicar 1 punto yadiciones de puntos para el cálculo previo. El algoritmo luego requiere duplicaciones de puntos y Sumas de puntos para el resto de la multiplicación.
Una propiedad de la NAF es que tenemos la garantía de que todos los elementos distintos de cero es seguido por al menos ceros adicionales. Esto se debe a que el algoritmo borra los pedazos de con cada resta de la salida de la función mods . Esta observación se puede utilizar para varios propósitos. Después de cada elemento distinto de cero, los ceros adicionales pueden estar implícitos y no es necesario almacenarlos. En segundo lugar, las divisiones en serie múltiples por 2 pueden reemplazarse por una división por después de cada distinto de cero elemento y dividir por 2 después de cada cero.
Se ha demostrado que mediante la aplicación de un ataque de canal lateral FLUSH + RELOAD en OpenSSL, se puede revelar la clave privada completa después de realizar el tiempo de caché con tan solo 200 firmas realizadas. [2]
Escalera de Montgomery
El método de la escalera de Montgomery [3] calcula la multiplicación de puntos en un período de tiempo fijo . Esto puede ser beneficioso cuando las mediciones de tiempo o consumo de energía se exponen a un atacante que realiza un ataque de canal lateral . El algoritmo utiliza la misma representación que en double-and-add.
R 0 ← 0 R 1 ← P Porque yo desde m abajo hasta 0 lo hago si d i = 0 entonces R 1 ← suma_punto (R 0 , R 1 ) R 0 ← punto_doble (R 0 ) demás R 0 ← suma_punto (R 0 , R 1 ) R 1 ← punto_doble (R 1 ) devuelve R 0
Este algoritmo tiene en efecto la misma velocidad que el método de doble y suma, excepto que calcula el mismo número de sumas y dobles de puntos independientemente del valor del multiplicando d . Esto significa que en este nivel el algoritmo no filtra ninguna información a través del tiempo o la potencia. Sin embargo, se ha demostrado que mediante la aplicación de un ataque de canal lateral FLUSH + RELOAD en OpenSSL, se puede revelar la clave privada completa después de realizar el tiempo de caché contra una sola firma a un costo muy bajo. [4]
Referencias
- ^ a b Hankerson, Darrel; Vanstone, Scott; Menezes, Alfred (2004). Guía de criptografía de curva elíptica . Computación profesional Springer. Nueva York: Springer-Verlag. doi : 10.1007 / b97644 . ISBN 0-387-95273-X. S2CID 720546 .
- ^ Benger, Naomi; van de Pol, Joop; Smart, Nigel P .; Yarom, Yuval (2014). Batina, Lejla; Robshaw, Matthew (eds.). "Ooh Aah ... Solo un poquito": Una pequeña cantidad de canal lateral puede ser de gran ayuda (PDF) . Hardware Criptográfico y Sistemas Embebidos - CHES 2014. Apuntes en Ciencias de la Computación. 8731 . Saltador. págs. 72–95. doi : 10.1007 / 978-3-662-44709-3_5 . ISBN 978-3-662-44708-6.
- ^ Montgomery, Peter L. (1987). "Aceleración de Pollard y métodos de factorización de curva elíptica" . Matemáticas. Comp. 48 (177): 243-264. doi : 10.2307 / 2007888 . JSTOR 2007888 . Señor 0866113 .
- ^ Yarom, Yuval; Benger, Naomi (2014). "Recuperación de OpenSSL ECDSA Nonces usando el ataque de canal lateral FLUSH + RELOAD Cache" . Archivo ePrint de criptología IACR .