elikaski/ecc_attacksAtaques conocidos contra la criptografía de curva elíptica
En los últimos años, el enfoque de la criptografía de curvas elípticas se ha vuelto popular debido a su alta eficiencia y fuerte seguridad. El propósito de este artículo es presentar este tema de una manera relativamente más clara de lo que existe hoy en internet.
En este artículo presentaré qué son las curvas elípticas, las operaciones básicas que se pueden realizar sobre ellas y cómo se pueden utilizar en el contexto criptográfico. La mayor parte de este artículo consiste en ejemplos de ataques conocidos a implementaciones incorrectas o usos indebidos de las mismas. A lo largo del artículo intento separar la explicación en una parte intuitiva y de alto nivel, y una parte matemática que entra en más detalle. Se invita al lector a centrarse en la parte que le interese en cada lugar y a omitir las partes que le interesen menos.
¡Feliz lectura!
En general, una curva elíptica es un tipo de línea curva. Un ejemplo de ello es la parábola, cuya ecuación es de la forma $𝑦 = 𝑎𝑥^2 + 𝑏𝑥 + 𝑐$ y se ve así:
En el contexto de la criptografía, es habitual usar curvas elípticas cuya ecuación es de la forma
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏$
Por ejemplo, una curva elíptica correspondiente a la ecuación $𝑦^2 = 𝑥^3 − 3𝑥 + 3$ se ve así:
La ecuación de la curva define la relación entre la coordenada 𝑥 de un punto de la curva y su coordenada 𝑦. En un contexto criptográfico, restringimos 𝑥, 𝑦, 𝑎, 𝑏 a números enteros y restringimos los cálculos al módulo de algún número primo grande. Así, la ecuación de la curva elíptica es:
$𝑦^2 = 𝑥^3 + 𝑎𝑥 + 𝑏\ \ \ \ (mod\ 𝑝)$.
Esto significa que tenemos un número finito de puntos en la curva. En lenguaje matemático, se dice que la curva está definida sobre un cuerpo finito de orden 𝑝. Como resultado, ahora no necesariamente toda coordenada 𝑥 tendrá un punto correspondiente en la curva, porque puede que la coordenada 𝑦 correspondiente no sea un número entero.
El conjunto de puntos de la curva consiste en pares de enteros (𝑥, 𝑦) que satisfacen la ecuación de la curva. Además de estos puntos, se define otro punto especial llamado "Infinito", denotado por 𝒪. En lenguaje matemático, este punto es el elemento neutro del conjunto de puntos de la curva respecto a la operación de suma, que definiremos en la siguiente sección. El número de puntos de la curva (incluido el punto 𝒪) se denomina "orden de la curva".
Otra observación es que las curvas elípticas son simétricas respecto al eje X. Esto significa que si el punto 𝑃 = (𝑥, 𝑦) está en la curva, entonces el punto −𝑃 = (𝑥, −𝑦) también está en la curva. De hecho, se considera que estos puntos son "inversos" entre sí (de ahí la notación −𝑃 para el segundo punto), y el resultado de la operación de suma entre ellos se define como el elemento neutro 𝒪.
Un teorema llamado teorema de Hasse proporciona una estimación de #𝐸, el orden de la curva, y es del orden de magnitud de Θ(𝑝). Más precisamente:
$𝑝 + 1 − 2\sqrt𝑝 ≤ 𝐸 ≤ 𝑝 + 1 + 2\sqrt𝑝$
Dados dos puntos de la curva, es posible definir una operación de suma entre ellos, cuyo resultado es un tercer punto que también está en la curva. Para encontrar este punto geométricamente, trazamos una línea entre los dos puntos dados y la continuamos hasta que interseque la curva en un tercer punto. Este punto se refleja con respecto al eje 𝑋, y el punto resultante se define como el resultado de la suma.
Aquí hay un diagrama que muestra cómo, dados los puntos 𝑃 y 𝑄, se puede encontrar el punto 𝑃 + 𝑄:
Una pregunta que puede surgir de esta descripción es: ¿qué ocurre si la línea trazada entre los dos puntos no vuelve a intersecar la curva? En este caso se dice que la línea interseca la curva en el "infinito", y el resultado de la suma es el punto 𝒪. Nótese que este caso ocurre si la línea trazada es vertical, es decir, estamos intentando sumar un punto 𝑃 con su punto inverso, −𝑃:
De esto se derivan dos identidades básicas. Para todo punto 𝑃 se cumple que:
𝑃 + 𝒪 = 𝑃
𝑃 + (−𝑃) = 𝒪
Otra pregunta que surge de la descripción geométrica es: ¿cómo sumamos un punto consigo mismo? Vimos que para sumar dos puntos distintos 𝑃 y 𝑄, trazamos una línea entre ellos y observamos el punto de intersección de su prolongación con la curva. Intuitivamente, dejaremos 𝑃 constante y observaremos la línea que se crea a medida que movemos 𝑄 "cada vez más cerca" de 𝑃, hasta que 𝑄 se fusione con 𝑃. Lo que obtendremos es una línea cada vez más "tangente" a la curva en el punto 𝑃, y esa es exactamente la línea que consideraremos cuando queramos sumar 𝑃 consigo mismo:
Para sumar un punto 𝑃 consigo mismo, trazamos una tangente a la curva en el punto 𝑃 y la continuamos hasta que interseque la curva en un segundo punto. Este punto se refleja con respecto al eje 𝑋, y el punto resultante se define como el resultado de la suma. Es habitual denotar el resultado de la suma como 𝑃 + 𝑃 = 2𝑃. Nuevamente, si la tangente no interseca la curva en un segundo punto, se dice que interseca la curva en el "infinito", y el resultado de la suma en este caso es el punto 𝒪.
Estas descripciones geométricas visuales ilustran muy bien y nos ayudan a entender cómo funciona la suma de puntos. Pero, ¿cómo la calculamos realmente? ¡Ecuaciones matemáticas, por supuesto!
