Multiplicación de puntos de curva elíptica

Apuntar al infinito${\displaystyle {\mathcal {O}}}$es el elemento neutro de la aritmética de curvas elípticas. Sumarlo a cualquier punto da como resultado ese otro punto, incluyendo sumar el punto en el infinito a sí mismo. Es decir:

${\displaystyle {\begin{aligned}{\mathcal {O}}+{\mathcal {O}}={\mathcal {O}}\\{\mathcal {O}}+P=P\end{aligned}}}$

El punto en el infinito también se escribe como 0 .

La negación de un punto consiste en encontrar un punto tal que, al sumarlo a sí mismo, dé como resultado un punto en el infinito ( ⁠${\displaystyle {\mathcal {O}}}$⁠ ).

${\displaystyle {\begin{aligned}P+(-P)={\mathcal {O}}\end{aligned}}}$

Para curvas elípticas de la forma E : y ² = x ³ + ax + b , la negación es un punto con la misma coordenada x pero con la coordenada y negada :

${\displaystyle {\begin{aligned}(x,y)+(-(x,y))&={\mathcal {O}}\\(x,y)+(x,-y)&={\mathcal {O}}\\(x,-y)&=-(x,y)\end{aligned}}}$

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. ^{[ 1} ]

${\displaystyle {\begin{aligned}P+Q&=R\\(x_{p},y_{p})+(x_{q},y_{q})&=(x_{r},y_{r})\end{aligned}}}$

Suponiendo que ^la curva elíptica, E , está dada por y² = ^x³ + ax + b , esto se puede calcular como:

${\displaystyle {\begin{aligned}\lambda &={\frac {y_{q}-y_{p}}{x_{q}-x_{p}}}\\x_{r}&=\lambda ^{2}-x_{p}-x_{q}\\y_{r}&=\lambda (x_{p}-x_{r})-y_{p}\\\end{aligned}}}$

Estas ecuaciones son correctas cuando ninguno de los puntos es el punto en el infinito ,${\displaystyle {\mathcal {O}}}$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.

Cuando los puntos P y Q coinciden (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 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): ^{[ 1 ]}

${\displaystyle \lambda ={\frac {3x_{p}^{2}+a}{2y_{p}}}}$

donde a proviene de la ecuación definitoria de la curva, E , arriba.

El método más sencillo es el método de duplicar y sumar, ^{[ 2 ]} similar al de elevar al cuadrado y multiplicar en la exponenciación modular . El algoritmo funciona de la siguiente manera:

Para calcular sP , comenzamos con la representación binaria de s :${\displaystyle s=s_{0}+2s_{1}+2^{2}s_{2}+\cdots +2^{n-1}s_{n-1}}$, donde​${\displaystyle s_{0}~..~s_{n-1}\in \{0,1\},n=\lceil \log _{2}{s}\rceil }$.​

• Algoritmo iterativo, índice creciente:

let bits = bit_representation(s) # el vector de bits (desde LSB hasta MSB) que representa s let res =${\displaystyle {\begin{aligned}{\mathcal {O}}\end{aligned}}}$# apunta al infinito sea temp = P # rastrea el valor P duplicado para bit en bits: si bit == 1: res = res + temp # suma de puntos temp = temp + temp # doble retorno res

• Algoritmo iterativo, índice decreciente:

let bits = bit_representation(s) # el vector de bits (desde LSB hasta MSB) que representa s let i = length(bits) - 2 let res = P while (i >= 0): # recorriendo desde el segundo MSB hasta LSB res = res + res # doble si bits[i] == 1: res = res + P # sumar i = i - 1 retorno res

Tenga en cuenta que ambos métodos iterativos mencionados anteriormente son vulnerables al análisis de tiempos. Consulte el método de Montgomery Ladder a continuación para ver un enfoque alternativo.

• Algoritmo recursivo:

El algoritmo f(P, d) es: si d = 0, entonces devuelve 0 (cálculo completado) ; si no, si d = 1 , entonces devuelve P; si no, si d mod 2 = 1 , entonces devuelve point_add(P, f(P, d - 1)) (suma cuando d es impar); si no , devuelve 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 2(2[P + 2(2[2(P + 2P)])]) y, por lo tanto, requiere seis operaciones de doble precisión y dos operaciones de suma. 100P sería igual a f(P, 100) .

Este algoritmo requiere log ₂ ( 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.

En la versión con ventana de este algoritmo, ^{[ 2 ]} se selecciona un tamaño de ventana w y se calcula todo${\displaystyle 2^{w}}$valores de${\displaystyle dP}$para${\displaystyle d=0,1,2,\dots ,2^{w}-1}$El algoritmo ahora utiliza la representación${\displaystyle d=d_{0}+2^{w}d_{1}+2^{2w}d_{2}+\cdots +2^{mw}d_{m}}$y se convierte

Q ← 0 para i desde m hasta 0 hacer Q ← punto_doble_repetición(Q, w) Si d i > 0 , entonces Q ← point_add(Q, d i P) # utilizando el valor precalculado de d i P, devolver Q

Este algoritmo tiene la misma complejidad que el método de duplicar y sumar, con la ventaja de utilizar 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,${\displaystyle w=4}$suele ser la mejor opción. La complejidad total para un número de n bits se mide como${\displaystyle n+1}$dobles de punto y${\displaystyle 2^{w}-2+{\tfrac {n}{w}}}$sumas de puntos.

En la versión de ventana deslizante, buscamos intercambiar adiciones de puntos por duplicaciones de puntos. Calculamos una tabla similar a la de la versión de ventana, excepto que solo calculamos los puntos.${\displaystyle dP}$para${\displaystyle d=2^{w-1},2^{w-1}+1,\dots ,2^{w}-1}$En efecto, solo estamos calculando los valores para los que está activado el bit más significativo de la ventana. El algoritmo luego utiliza la representación original de doble suma de${\displaystyle d=d_{0}+2d_{1}+2^{2}d_{2}+\cdots +2^{m}d_{m}}$.

Q ← 0 para i desde m hasta 0 hacer si d i = 0 entonces Q ← punto_doble(Q) de lo contrario t ← extrae j (hasta w − 1) bits adicionales de d (incluido d i ) i ← i − j si j < w entonces Realizar doble suma usando t Devuelve Q de lo contrario Q ← punto_doble_repetición(Q, w) Q ← punto_añadir(Q, tP) devolver 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 adiciones 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${\displaystyle w-1+n}$dobles de puntos y como máximo${\displaystyle 2^{w-1}-1+{\tfrac {n}{w}}}$sumas de puntos.

En la forma no adyacente, nuestro objetivo es 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. El NAF del multiplicando${\displaystyle d}$debe calcularse primero con el siguiente algoritmo

i ← 0 mientras (d > 0) hacer si (d mod 2) = 1 entonces d i ← d mod 2 w d ← d − d i sino d i = 0 d ← d/2 i ← i + 1 devolver (d i−1 , d i-2 , ..., d 0 )

Donde la función módulo con signo mods se define como

Si (d mod 2 w ) > = 2 w−1 , devolver (d mod 2 w ) − 2 w; de lo contrario, devolver d mod 2 w.

Esto produce el NAF necesario para realizar ahora la multiplicación. Este algoritmo requiere el cálculo previo de los puntos.${\displaystyle \lbrace 1,3,5,\dots ,2^{w-1}-1\rbrace P}$y sus aspectos negativos, donde${\displaystyle P}$es el punto que se va a multiplicar. En las curvas típicas de Weierstrass, si${\displaystyle P=\lbrace x,y\rbrace }$entonces${\displaystyle -P=\lbrace x,-y\rbrace }$. Por lo tanto, en esencia, los negativos son baratos de calcular. A continuación, el siguiente algoritmo calcula la multiplicación${\displaystyle dP}$:

Q ← 0 para j ← i − 1 hasta 0 hacer Q ← punto_doble(Q) si (d j != 0) Q ← point_add(Q, d j P) devuelve Q

El wNAF garantiza que en promedio habrá una densidad de${\displaystyle {\tfrac {1}{w+1}}}$sumas de puntos (ligeramente mejor que la ventana sin signo). Requiere 1 duplicación de punto y${\displaystyle 2^{w-2}-1}$sumas de puntos para el preprocesamiento. El algoritmo luego requiere${\displaystyle n}$duplicaciones de puntos y${\displaystyle {\tfrac {n}{w+1}}}$suma de puntos para el resto de la multiplicación.

Una propiedad del NAF es que tenemos la garantía de que cada elemento distinto de cero${\displaystyle d_{i}}$va seguido de al menos${\displaystyle w-1}$ceros adicionales. Esto se debe a que el algoritmo borra los valores inferiores.${\displaystyle w}$trozos de${\displaystyle d}$con cada resta de la salida de la función mods . Esta observación puede utilizarse 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 múltiples divisiones seriales por 2 pueden reemplazarse por una división por${\displaystyle 2^{w}}$después de cada valor distinto de cero${\displaystyle d_{i}}$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 un análisis de temporización de caché contra tan solo 200 firmas realizadas. ^{[ 3 ]}

El método de la escalera de Montgomery ^{[ 4 ]} calcula la multiplicación de puntos en un número fijo de operaciones. Esto puede ser beneficioso cuando la temporización, el consumo de energía o las mediciones de bifurcación están expuestas a un atacante que realiza un ataque de canal lateral . El algoritmo utiliza la misma representación que la de la operación de doble suma.

R 0 ← 0 R 1 ← P para i desde m hasta 0 hacer si d i = 0 entonces R 1 ← point_add(R 0 , R 1 ) R 0 ← punto_doble(R 0 ) de lo contrario R 0 ← punto_añadido(R 0 , R 1 ) R 1 ← punto_doble(R 1 ) // propiedad invariante para mantener la corrección assert R 1 == point_add(R 0 , P) return R 0

Este algoritmo tiene, en efecto, la misma velocidad que el método de duplicar y sumar, con la diferencia de 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 pierde información a través de bifurcaciones ni consume energía.

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 una comprobación de temporización de caché contra una sola firma a un costo muy bajo. ^{[ 5 ]}

El uso de cadenas 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 en múltiplos mayores (cadenas más largas). Este método se denomina "PRAC". Montgomery también publica PRAC, siendo GMP-ECM la " implementación de referencia ". ^{[ 6 ]} DJ Bernstein menciona varios esquemas de este tipo en 2017. ^{[ 7 ] : § 4.8.2}

La seguridad de una implementación criptográfica puede verse amenazada por los llamados ataques de temporización , que explotan las características de temporización dependientes de los datos de la implementación. Las máquinas que ejecutan implementaciones criptográficas consumen cantidades variables de tiempo para procesar diferentes entradas, por lo que los tiempos varían según la clave de cifrado. Para resolver este problema, los algoritmos criptográficos se implementan de forma que se elimina la característica de temporización variable dependiente de los datos de la implementación, lo que da lugar a las llamadas implementaciones de tiempo constante. Las implementaciones de software se consideran de tiempo constante en el siguiente sentido, como se indica en: ^{[ 8 ]} “ evita todas las bifurcaciones dependientes de la entrada, todos los índices de matriz dependientes de la entrada y otras instrucciones con tiempos dependientes de la entrada ”. La página de GitHub ^{[ 9 ]} enumera las reglas de codificación para las implementaciones de operaciones criptográficas y, más generalmente, para las operaciones que involucran valores secretos o sensibles.

La escalera de Montgomery es una${\displaystyle x}$-algoritmo de coordenadas solamente para la multiplicación de puntos de curvas elípticas y se basa en las reglas de doble y suma sobre un conjunto específico de curvas conocido como curva de Montgomery . El algoritmo tiene una ramificación condicional tal que la condición depende de un bit secreto. Por lo tanto, una implementación directa de la escalera no será de tiempo constante y tiene el potencial de filtrar el bit secreto. Este problema se ha abordado en la literatura ^{[ 10 ] [ 11 ]} y se conocen varias implementaciones de tiempo constante. El algoritmo de escalera de Montgomery de tiempo constante es el que se da a continuación que utiliza dos funciones CSwap y Ladder-Step. En el valor de retorno del algoritmo Z ₂ ^p-2 es el valor de Z ₂ ⁻¹ calculado usando el pequeño teorema de Fermat .

El algoritmo Montgomery-Ladder(x P , n) tiene como entrada : Un${\displaystyle l}$escalar de bits${\displaystyle n}$y el${\displaystyle x}$-coordinar${\displaystyle x_{P}}$de un punto${\displaystyle P}$. producción :${\displaystyle x}$-coordenada de${\displaystyle nP}$, el${\displaystyle n}$-veces múltiplo escalar de${\displaystyle P}$. X 1 ← x P ; X 2 ← 1; Z 2 ← 0; X 3 ← x P ; Z 3 ← 1 prevbit ← 0 para${\displaystyle i}$de${\displaystyle l-1}$downto 0 hacer bit ← valor de bit en el índice${\displaystyle i}$de${\displaystyle n}$ b ← bit${\displaystyle \oplus }$prefijo bit anterior ← bit (${\displaystyle \langle }$X 2 ,Z 2${\displaystyle \rangle }$,${\displaystyle \langle }$X 3 ,Z 3${\displaystyle \rangle }$) ← CSwap(${\displaystyle \langle }$X 2 ,Z 2${\displaystyle \rangle }$,${\displaystyle \langle }$X 3 ,Z 3${\displaystyle \rangle }$,b) (${\displaystyle \langle }$X 2 ,Z 2${\displaystyle \rangle }$,${\displaystyle \langle }$X 3 ,Z 3${\displaystyle \rangle }$) ← Escalera-escalón(${\displaystyle \langle }$X 2 ,Z 2${\displaystyle \rangle }$,${\displaystyle \langle }$X 3 ,Z 3${\displaystyle \rangle }$,X 1 ) devolver X 2 Z 2 p-2

La función Ladder-Step (que se muestra a continuación) utilizada dentro de la escalera es el núcleo del algoritmo y es una forma combinada de las operaciones de suma diferencial y duplicación. La constante de campo a ₂₄ se define como a ₂₄ =${\displaystyle (A+2)/4}$, dónde${\displaystyle A}$es un parámetro de la curva de Montgomery subyacente .

Función Escalera-Paso(${\displaystyle \langle }$X 2 ,Z 2${\displaystyle \rangle }$,${\displaystyle \langle }$X 3 ,Z 3${\displaystyle \rangle }$,X 1 ) T 1 ← X 2 + Z 2 T 2 ← X 2 - Z 2 T 3 ← X 3 + Z 3 T 4 ← X 3 - Z 3 T 5 ← T 1 2 T 6 ← T 2 2 T 2 ← T 2 · T 3 T 1 ← T 1 · T 4 T 1 ← T 1 + T 2 T 2 ← T 1 - T 2 X 3 ← T 1 2 T 2 ← T 2 2 Z 3 ← T 2 · X 1 X 2 ← T 5 · T 6 T 5 ← T 5 - T 6 T 1 ← a 24 · T 5 T 6 ← T 6 + T 1 Z 2 ← T 5 · T 6 regreso (${\displaystyle \langle }$X 2 ,Z 2${\displaystyle \rangle }$,${\displaystyle \langle }$X 3 ,Z 3${\displaystyle \rangle }$)

La función CSwap gestiona la ramificación condicional y ayuda a que la escalera se ejecute siguiendo los requisitos de una implementación de tiempo constante. La función intercambia el par de elementos del campo.${\displaystyle \langle }$X ₂ ,Z ₂${\displaystyle \rangle }$y${\displaystyle \langle }$X ₃ ,Z ₃${\displaystyle \rangle }$solo si${\displaystyle b}$= 1 y esto se hace sin filtrar ninguna información sobre el bit secreto. Se han propuesto varios métodos de implementación de CSwap en la literatura. ^{[ 10 ] [ 11 ]} Una opción menos costosa para gestionar el requisito de tiempo constante de la escalera de Montgomery es la selección condicional que se formaliza a través de una función CSelect. Esta función se ha utilizado en varias optimizaciones y se ha discutido formalmente en ^{[ 12 ]}

Desde la creación de la curva Montgomery estándar Curve25519 con un nivel de seguridad de 128 bits, se han desarrollado diversas implementaciones de software para calcular el ECDH en diferentes arquitecturas. Para lograr el mejor rendimiento posible, los desarrolladores criptográficos han recurrido a escribir las implementaciones utilizando el lenguaje ensamblador de la arquitectura subyacente. El trabajo ^{[ 13 ]} proporcionó un par de implementaciones en ensamblador de 64 bits dirigidas a la arquitectura AMD64. Estas implementaciones se desarrollaron utilizando una herramienta conocida como qhasm ^{[ 14 ]} , que puede generar programas criptográficos en lenguaje ensamblador de alta velocidad. La función CSwap se utilizó en las implementaciones de estas escaleras. Posteriormente, se realizaron varios intentos para optimizar la implementación de la escalera mediante programas en ensamblador escritos a mano, entre los cuales la noción de CSelect se utilizó por primera vez en ^{[ 15 ]} y luego en ^{[ 16 ]} . Además de utilizar instrucciones secuenciales, también se han utilizado instrucciones vectoriales para optimizar el cálculo de la escalera en diversos trabajos. ^{[ 17 ] [ 18 ] [ 19 ] [ 20 ]} Junto con AMD64, también se han realizado intentos para lograr implementaciones eficientes en otras arquitecturas como ARM. Los trabajos ^{[ 21 ]} y ^{[ 22 ]} proporcionan implementaciones eficientes dirigidas a la arquitectura ARM. Las bibliotecas lib25519 ^{[ 23 ]} y ^{[ 24 ]} son ​​dos bibliotecas de vanguardia que contienen implementaciones eficientes de la escalera de Montgomery para Curve25519 . No obstante, las bibliotecas también tienen implementaciones de otras primitivas criptográficas.

Aparte de Curve25519 , se han realizado varios intentos de calcular la escalera sobre otras curvas en diversos niveles de seguridad. También se han estudiado en la literatura implementaciones eficientes de la escalera sobre la curva estándar Curve448 en un nivel de seguridad de 224 bits. ^{[ 15 ] [ 18 ] [ 20 ]} Se propuso una curva llamada Curve41417 que proporciona una seguridad de poco más de 200 bits ^{[ 25 ]} en la que se utilizó una variante de la estrategia Karatsuba para implementar la multiplicación de campo necesaria para el software ECC relacionado. En la búsqueda de curvas de Montgomery que sean competitivas con Curve25519 y Curve448, se ha llevado a cabo una investigación y se propusieron un par de curvas junto con implementaciones secuenciales eficientes ^{[ 16 ]} y vectorizadas ^{[ 20 ]} de las escaleras correspondientes. En un nivel de seguridad de 256 bits, también se han abordado implementaciones eficientes de la escalera a través de tres curvas de Montgomery diferentes. ^{[ 26 ]}