La multiplicación escalar en curvas elípticas consiste en sumar sucesivamente un punto a sí mismo en una curva elíptica. Se utiliza en criptografía de curva elíptica (CCE).
En la literatura, esta operación se presenta como multiplicación escalar, tal como se escribe en la forma hessiana de una curva elíptica. También se la conoce comúnmente como multiplicación de puntos en curvas elípticas, pero esto puede dar la impresión errónea de que se trata de una multiplicación entre dos puntos.
Conceptos básicos Dada una curva E definida por una ecuación en un cuerpo finito (como E: ), la multiplicación de puntos se define como la suma repetida de un punto en dicha curva. Denótese como un escalar (entero) n y un punto que se encuentra sobre la curva E. Este tipo de curva se conoce como curva de Weierstrass.
La seguridad de la computación elíptica moderna depende de la dificultad de determinar n a partir de dados valores conocidos de Q y P si n es grande (conocido como el problema curva elíptica logaritmo discreto 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 suma de un punto consigo mismo) 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 al repetir esto muchas veces se obtiene un punto nP que puede estar esencialmente en cualquier lugar. Intuitivamente, esto es similar al hecho de que si se tiene un punto P en un círculo, sumar 42,57 grados a su ángulo puede seguir siendo un punto "no muy lejos" de P, pero sumar 1000 o 1001 veces 42,57 grados producirá un punto que requiere un cálculo un poco más complejo para encontrar el ángulo original. Invertir este proceso, es decir, dados Q=nP y P, y determinar n, solo se puede lograr probando todos los valores posibles de n, un esfuerzo computacionalmente intratable si n es grande.
Operaciones puntuales
Existen tres operaciones comúnmente definidas para los puntos de una curva elíptica: suma, duplicación y negación.
Punto en el infinito El punto en el infinito es el equivalente al elemento neutro en la aritmética de curvas elípticas. Sumarlo a cualquier punto da como resultado ese otro punto, incluyendo la suma del punto en el infinito consigo mismo.
Es decir:
El punto en el infinito también se escribe como .
Negación de punto La negación de punto consiste en encontrar un punto tal que, al sumarlo a sí mismo, dé como resultado el punto en el infinito ().
Para curvas elípticas de la forma E: , la negación es un punto con la misma coordenada x pero con la coordenada y negada:
Suma de puntos Con dos puntos distintos, P y Q, la suma se define como la negación del punto resultante de la intersección de la curva E y la línea recta definida por los puntos P y Q, dando como resultado el punto R.
Suponiendo que la curva elíptica E está dada por , esto se puede calcular como:
Estas ecuaciones son correctas cuando ninguno de los puntos es el punto en el infinito, , y si los puntos tienen coordenadas x diferentes (no son inversos mutuos). Esto es importante para el algoritmo de verificación ECDSA, donde el valor hash podría ser cero.
Duplicación de puntos Cuando los puntos P y Q coinciden (tienen las mismas coordenadas), la suma es similar, excepto en que no existe una línea recta bien definida que pase por P, por lo que la operación se cierra utilizando un caso límite: la tangente a la curva E en P.
Esto se calcula como se indicó anteriormente, tomando derivadas (dE/dx)/(dE/dy):
donde a proviene de la ecuación que define la curva E.
Multiplicación de puntos La forma más directa de calcular la multiplicación de puntos es mediante sumas repetidas. Sin embargo, existen métodos más eficientes para calcular la multiplicación.
Duplicación y suma El método más simple es el de duplicación y suma, similar a cuadrar-y-multiplicar en exponenciación modular. El algoritmo funciona de la siguiente manera:
Para calcular sP, se parte de la representación binaria de s: , donde .
Algoritmo iterativo, índice creciente:
let bits = bit_representation(s) # vector de bits (desde LSB hasta MSB) que representa s let res = # punto del infinito let temp = P # rastrea el valor P duplicado for bit in bits: if bit == 1: res = res + temp # suma de puntos temp = temp + temp # doble return res
Algoritmo iterativo, índice decreciente:
let bits = bit_representation(s) # vector de bits (del LSB al MSB) que representa s let i = length(bits) - 2 let res = P while (i >= 0): # recorrido del segundo MSB al LSB res = res + res # doble if bits[i] == 1: res = res + P # suma i = i - 1 return res
Téngase en cuenta que ambos métodos iterativos anteriores son vulnerables al análisis de tiempos. Consúltese la Escalera de Montgomery a continuación para un enfoque alternativo.
Algoritmo recursivo:
algorithm f(P, d) is if d = 0 then return 0 # cálculo completado else if d = 1 then return P else if d mod 2 = 1 then return point_add(P, f(P, d - 1)) # suma cuando d es impar else return f(point_double(P), d / 2) # duplicación cuando d es par
donde f es la función de multiplicación, P es la coordenada a multiplicar y d es el número de veces que se suma la coordenada a sí misma. Ejemplo: 100P se puede escribir como y, por lo tanto, requiere seis operaciones de punto doble y dos operaciones de suma. 100P sería igual a f(P, 100).
Este algoritmo requiere log2(d) iteraciones de duplicación y suma de puntos para calcular la multiplicación completa de puntos. Existen muchas variaciones de este algoritmo, como el uso de una ventana, una ventana deslizante, NAF, NAF-w, cadenas vectoriales y la escalera de Montgomery.
Método con ventana En la versión con ventana de este algoritmo, se selecciona un tamaño de ventana w y se calculan todos los valores de para . El algoritmo ahora utiliza la representación y se convierte en:
Q ← 0 for i from m to 0 do Q ← point_double_repeat(Q, w) if di > 0 then Q ← point_add(Q, diP) # usando el valor precalculado de diP return Q
Este algoritmo tiene la misma complejidad que el método de duplicar y sumar, con la ventaja de usar menos sumas de puntos (que en la práctica son más lentas que la duplicación). Normalmente, el valor de w se elige bastante pequeño, lo que hace que la etapa de precomputación sea un componente trivial del algoritmo. Para las curvas recomendadas por el NIST, suele ser la mejor opción. La complejidad total para un número de n bits se mide como duplicaciones de puntos y sumas de puntos.
Método de ventana deslizante En la versión de ventana deslizante, buscamos un equilibrio entre sumas de puntos y duplicaciones de puntos. Calculamos una tabla similar a la de la versión con ventana, excepto que solo calculamos los puntos para . En efecto, solo calculamos los valores para los que el bit más significativo de la ventana está activado. El algoritmo utiliza entonces la representación original de doble suma de .
Q ← 0 for i from m downto 0 do if di = 0 then Q ← point_double(Q) else t ← extract j (up to w − 1) additional bits from d (including di) i ← i − j if j < w then Perform double-and-add using t return Q else Q ← point_double_repeat(Q, w) Q ← point_add(Q, tP) return Q
Este algoritmo tiene la ventaja de que la etapa de precomputación es aproximadamente la mitad de compleja que el método de ventana normal, a la vez que intercambia sumas de puntos más lentas por duplicaciones de puntos. En efecto, hay pocas razones para usar el método de ventana en lugar de este enfoque, excepto que el primero se puede implementar en tiempo constante. El algoritmo requiere duplicaciones de puntos y como máximo sumas de puntos.
Método de forma no adyacente -aria (NAF) En el método de forma no adyacente, se busca aprovechar el hecho de que la resta de puntos es tan fácil como la suma de puntos para realizar menos operaciones (de cualquiera de las dos) en comparación con un método de ventana deslizante. La NAF del multiplicando debe calcularse primero con el siguiente algoritmo:
i ← 0 while (d > 0) do if (d mod 2) = 1 then di ← d mods 2w d ← d − di else di = 0 d ← d/2 i ← i + 1 return (di−1, di-2, ..., d0)
donde la función de módulo con signo mods se define como:
if (d mod 2w) >= 2w−1 return (d mod 2w) − 2w else return d mod 2w
Esto genera la función de autocorrelación (NAF) necesaria para realizar la multiplicación. Este algoritmo requiere el cálculo previo de los puntos y sus negativos, donde es el punto a multiplicar. En curvas de Weierstrass típicas, si entonces . Por lo tanto, en esencia, el cálculo de los negativos es sencillo. A continuación, el siguiente algoritmo calcula la multiplicación :
Q ← 0 for j ← i − 1 downto 0 do Q ← point_double(Q) if (dj != 0) Q ← point_add(Q, djP) return Q
La función de autocorrelación (wNAF) garantiza que, en promedio, habrá una densidad de sumas de puntos (ligeramente mejor que la ventana sin signo). Requiere una duplicación de punto y sumas de puntos para el preprocesamiento. El algoritmo requiere luego duplicaciones de puntos y sumas de puntos para el resto de la multiplicación.
Una propiedad del NAF es que se garantiza que cada elemento distinto de cero va seguido de al menos ceros adicionales. Esto se debe a que el algoritmo borra los bits inferiores de con cada resta del resultado de la función módulo. Esta observación puede utilizarse para diversos fines. Tras cada elemento distinto de cero, los ceros adicionales se sobreentienden y no es necesario almacenarlos. En segundo lugar, las múltiples divisiones seriales por 2 pueden sustituirse por una división por después de cada elemento distinto de cero y una división por 2 después de cada cero.
Se ha demostrado que, mediante la aplicación de un ataque de canal lateral FLUSH+RELOAD sobre OpenSSL, se puede revelar la clave privada completa tras realizar mediciones de tiempo de caché con tan solo 200 firmas.
Escalera de Montgomery El método de la escalera de Montgomery calcula la multiplicación de puntos en un número fijo de operaciones. Esto puede ser beneficioso cuando un atacante que realiza un ataque de canal lateral tiene acceso a mediciones de tiempo, consumo de energía o bifurcaciones. El algoritmo utiliza la misma representación que la de la operación de doble suma.
R0 ← 0 R1 ← P for i from m downto 0 do if di = 0 then R1 ← point_add(R0, R1) R0 ← point_double(R0) else R0 ← point_add(R0, R1) R1 ← point_double(R1)
// invariant property to maintain correctness assert R1 == point_add(R0, P) return R0
Este algoritmo tiene, en efecto, la misma velocidad que el método de duplicar y sumar, excepto que calcula el mismo número de sumas y duplicaciones de puntos independientemente del valor del multiplicando d. Esto significa que, a este nivel, el algoritmo no filtra información a través de bifurcaciones ni consume energía.
Sin embargo, se ha demostrado que, mediante un ataque de canal lateral FLUSH+RELOAD contra OpenSSL, se puede revelar la clave privada completa tras realizar una prueba de temporización de caché con una sola firma, a un coste muy bajo.
Cadenas más largas El uso del encadenamiento de Lucas proporciona una secuencia optimizada de duplicación y suma en comparación con la escalera de Montgomery, que es más rápida con múltiplos mayores (cadenas más largas). Este método se denomina "PRAC". PRAC también fue publicado por Montgomery, con la "implementación de referencia" GMP-ECM. HAL DJ Bernstein menciona varios esquemas de este tipo en 2017.
Escalera de Montgomery de tiempo constante