Curvas elípticas sin miedo.

En 1985, Victor Miller, en IBM, y Neal Koblitz, en la Universidad de Washington, propusieron por separado la misma idea: usar como base de la criptografía de clave pública no los números módulo un primo, sino los puntos de una curva elíptica. La propuesta tardó casi veinte años en imponerse, entre patentes, desconfianza hacia una matemática poco familiar y la comodidad de RSA. Hoy las curvas elípticas protegen la mayor parte de las conexiones seguras de internet, firman en los documentos de identidad electrónicos de muchos países y autorizan cada transacción de las principales cadenas de bloques.

La razón es un número. Para igual seguridad, una clave de curva elíptica de 256 bits reemplaza a una clave RSA de 3072. Este artículo explica de dónde sale esa diferencia, empezando por algo tan concreto como sumar dos puntos con una regla.

Qué es una curva elíptica

Pese al nombre, no tiene nada que ver con una elipse; el nombre viene de las integrales elípticas, que en el siglo XIX llevaron a estudiarlas. Para la criptografía, una curva elíptica es el conjunto de puntos (x, y) que cumplen una ecuación de Weierstrass, más un punto adicional llamado punto en el infinito, O:

Lo extraordinario es que esos puntos se pueden sumar, y la suma tiene todas las propiedades que uno espera: es asociativa, conmutativa, tiene elemento neutro y cada punto tiene opuesto. En otras palabras, forman un grupo, la misma estructura algebraica que los números módulo p del artículo sobre los fundamentos, con otra geometría.

La regla de la cuerda y la tangente

Para sumar dos puntos P y Q se traza la recta que pasa por ambos. Una cúbica cortada por una recta tiene, contando multiplicidades, tres intersecciones, así que la recta toca la curva en un tercer punto R. El resultado se define como el reflejo de R respecto del eje horizontal. Si P = Q, se usa la tangente. Si la recta es vertical, el tercer punto es O, y por eso el opuesto de (x, y) es (x, y).

Que esta operación sea asociativa no es evidente en absoluto; la demostración usa geometría algebraica de cierto nivel. Pero se puede comprobar en el dibujo. El laboratorio permite mover los dos puntos y ver la construcción completa.

De la geometría al cuerpo finito

La criptografía no usa números reales, que tienen precisión infinita y propiedades continuas aprovechables. Usa las mismas fórmulas con aritmética módulo un primo p. La división se reemplaza por la multiplicación por el inverso modular. La curva deja de ser una línea y se convierte en una nube de puntos con coordenadas enteras, aparentemente desordenada, pero que conserva intacta la estructura de grupo.

¿Cuántos puntos tiene? El teorema de Hasse, de 1933, responde con precisión notable: el número de puntos de la curva sobre el cuerpo de p elementos difiere de p + 1 en a lo sumo 2√p. Para la criptografía se eligen curvas cuyo número de puntos sea primo, o un primo grande multiplicado por un factor pequeño llamado cofactor.

Multiplicar por un número, y el problema inverso

Sumar un punto consigo mismo k veces se escribe k · G y se llama multiplicación escalar. Hacerlo sumando de a uno sería impracticable para un k de 256 bits, pero el método de duplicar y sumar lo resuelve con unas 256 duplicaciones y, en promedio, 128 sumas, igual que la exponenciación rápida en aritmética modular.

Aquí aparece la diferencia decisiva con RSA. Para factorizar enteros o calcular logaritmos discretos módulo un primo existen algoritmos subexponenciales, de la familia del cálculo de índices, que aprovechan que los números enteros se descomponen en factores pequeños. Los puntos de una curva elíptica no tienen una noción útil de «factores pequeños». Para curvas bien elegidas, el mejor ataque conocido sigue siendo genérico: el método rho de Pollard, que necesita alrededor de √n operaciones. Con n de 256 bits, eso es 2¹²⁸.

La brecha crece con el nivel de seguridad porque los ataques contra RSA son subexponenciales y los ataques contra curvas son exponenciales. En la práctica, eso significa claves y firmas más chicas, operaciones con la clave privada más rápidas y menos consumo, algo decisivo en tarjetas inteligentes y dispositivos móviles. Una firma ECDSA sobre P 256 ocupa 64 bytes; una RSA de nivel comparable, 384.

No toda curva sirve

La seguridad depende de elegir bien la curva, y la historia registra varias trampas.

• Curvas anómalas. Si el número de puntos es exactamente p, el logaritmo discreto se resuelve en tiempo polinomial.
• Grado de inmersión bajo. En ciertas curvas, entre ellas las supersingulares, el ataque de Menezes, Okamoto y Vanstone de 1993 traslada el problema a un cuerpo finito donde sí hay algoritmos subexponenciales.
• Orden con factores pequeños. Si el grupo no tiene un subgrupo primo grande, el método de Pohlig y Hellman divide el problema en partes fáciles.
• Puntos inválidos. Un verificador que no comprueba que el punto recibido está en la curva puede terminar calculando sobre otra curva, débil, elegida por el atacante. Validar los puntos de entrada no es opcional.

Las curvas con nombre propio

Por todo esto, nadie genera su propia curva: se usan curvas estandarizadas, con parámetros públicos y estudiados.

Curve25519 merece una nota aparte, porque cambió la forma de pensar el diseño. Bernstein no buscó sólo una curva sin debilidades conocidas, sino una en la que cada decisión tuviera una justificación pública, y en la que la implementación más simple fuera también la segura. Su variante para firmas, en forma de Edwards, tiene una ley de suma «completa»: la misma fórmula sirve para sumar, duplicar y operar con el neutro, sin ramas que filtren información por el tiempo de cálculo. El próximo artículo de la serie muestra cómo esa curva se usa en EdDSA y por qué su firma es determinista.

← Todas las notas