Curvas elípticas: La aritmética de las curvas: ECDH, ECDSA, Ed25519

Diffie–Hellman y RSA necesitan números de miles de bits, porque hay algoritmos subexponenciales (la criba del cuerpo de números y sus parientes para el logaritmo discreto) que atacan la estructura multiplicativa de los enteros. En 1985 Neal Koblitz y Victor Miller propusieron, por separado, hacer la misma criptografía en otro grupo en el que no se conocía ningún atajo así: los puntos de una curva elíptica sobre un cuerpo finito. Cuarenta años después sigue sin conocerse, y la criptografía de curva elíptica (ECC) ha sustituido a RSA casi en todas partes.

Sumar puntos con una regla

Una curva elíptica, en la forma que usan los criptógrafos, es el conjunto de soluciones de

E : y^{2} = x^{3} + a x + b, 4 a^{3} + 27 b^{2} \neq 0,

junto con un punto extra $𝒪$ , «en el infinito». La condición descarta las cúspides y los autocruces. La curva es simétrica respecto al eje $x$ . Sus puntos se pueden sumar: se traza la recta que pasa por $P$ y $Q$ ; corta a la curva exactamente en un punto más, $R^{'}$ ; su reflejo respecto al eje $x$ es $P + Q$ . Para duplicar un punto se usa la tangente. Una recta vertical corta la curva en el infinito, así que $P + (- P) = 𝒪$ , donde $- P$ es el reflejo de $P$ .

La ley de la cuerda y la tangente sobre los números reales. Cambia la curva con

a

b

y mueve

P

Q

por ella. La recta que los une corta la curva en un tercer punto,

- (P + Q)

; su reflejo es

P + Q

. Cuando

P = Q

, la recta es la tangente. Con

a = - 2

b

pequeño, la curva se parte en dos trozos, y la ley sigue funcionando.

En coordenadas, para $P = (x_{1}, y_{1})$ y $Q = (x_{2}, y_{2})$ con $P \neq - Q$ , sea $λ$ la pendiente de la recta, $λ = (y_{2} - y_{1}) / (x_{2} - x_{1})$ , o $λ = (3 x_{1}^{2} + a) / (2 y_{1})$ para la tangente. Entonces

x_{3} = λ^{2} - x_{1} - x_{2}, y_{3} = λ (x_{1} - x_{3}) - y_{1} .

Teorema (la ley de grupo)

Con esta suma y $𝒪$ como elemento neutro, los puntos de $E$ forman un grupo abeliano. Las mismas fórmulas, calculadas en cualquier cuerpo $K$ , hacen de $E (K)$ , los puntos con coordenadas en $K$ , un grupo.

Sobre la demostración

La conmutatividad es clara (la recta que pasa por $P$ y $Q$ es la que pasa por $Q$ y $P$ ), el neutro y los opuestos vienen de las rectas verticales, y el cierre de que una recta corta a una cúbica en tres puntos contados con multiplicidad. La asociatividad es lo difícil: se puede comprobar por fuerza bruta algebraica con las fórmulas, demostrar con elegancia con el teorema de Cayley–Bacharach sobre cúbicas que pasan por ocho puntos comunes, o mediante el teorema de Riemann–Roch, que identifica $E$ con su propio grupo de Picard.

Curvas sobre un cuerpo finito

La criptografía necesita aritmética exacta y finita, así que las coordenadas viven en $𝔽_{p}$ , los enteros módulo un primo $p$ . La «curva» se convierte en una nube de puntos sin forma visible, pero las fórmulas, y el grupo, son los mismos.

Teorema (Hasse, 1933)

El número de puntos de $E$ sobre $𝔽_{p}$ (contando $𝒪$ ) cumple $| # E (𝔽_{p}) - (p + 1) | \leq 2 \sqrt{p}$ .

Así que una curva sobre un cuerpo primo de 256 bits tiene unos $2^{256}$ puntos; el algoritmo de Schoof (1985) los cuenta exactamente, y se eligen curvas cuyo número de puntos es un primo grande (o un múltiplo pequeño de uno), para que el grupo sea cíclico y no tenga subgrupos pequeños en los que esconderse.

La curva

y^{2} = x^{3} + 2 x + 3

sobre

𝔽_{97}

: todos sus puntos y los múltiplos

G, 2 G, 3 G, \dots

de un generador

G

. Pulsa reproducir: los múltiplos saltan por la cuadrícula sin ningún patrón que se pueda seguir hacia atrás. Conociendo solo el punto final, recuperar

k

es el problema del logaritmo discreto en curvas elípticas. Aquí un ordenador lo encuentra al instante probando todos los

k

; con números de 256 bits, ningún ordenador puede.

El logaritmo discreto en una curva

Multiplicar un punto por un escalar, $k P = P + P + \dots + P$ , es rápido con duplicar y sumar (la versión aditiva de elevar al cuadrado y multiplicar). Deshacerlo es el problema del logaritmo discreto en curvas elípticas (ECDLP): dados $P$ y $Q = k P$ , encontrar $k$ .

Teorema (algoritmos genéricos, Pollard 1978; Shoup 1997)

En un grupo cíclico de orden primo $n$ , el algoritmo rho de Pollard encuentra logaritmos discretos en unas $\sqrt{π n / 2}$ operaciones de grupo y memoria constante. Recíprocamente, cualquier algoritmo que use el grupo solo a través de sus operaciones (un algoritmo genérico) necesita unas $\sqrt{n}$ .

El rho de Pollard es otra vez la paradoja del cumpleaños: un paseo pseudoaleatorio por el grupo acaba repitiendo un punto, y una repetición revela $k$ . Para las buenas curvas elípticas no se conoce nada mejor que estos ataques genéricos. Así que la seguridad crece con la mitad del tamaño en bits del orden del grupo, y las claves son cortas:

Seguridad	Simétrica	RSA / DH en cuerpo finito	Curva elíptica
112 bits	3DES	2.048 bits	224 bits
128 bits	AES-128	3.072 bits	256 bits
192 bits	AES-192	7.680 bits	384 bits
256 bits	AES-256	15.360 bits	512 bits

ECDH y X25519

El Diffie–Hellman de curva elíptica es el protocolo del capítulo 08 con el grupo nuevo: Alicia envía $a G$ , Bob envía $b G$ y los dos calculan $a b G$ . En 2006 Daniel J. Bernstein publicó Curve25519, la curva $y^{2} = x^{3} + 486662 x^{2} + x$ sobre el primo $2^{255} - 19$ , diseñada para que la implementación rápida y sencilla sea también la segura: cualquier cadena de 32 bytes es una clave pública válida, el cálculo (la escalera de Montgomery) es de tiempo constante y no hay casos especiales que olvidar. Su acuerdo de claves, X25519, es hoy el predeterminado de TLS 1.3, SSH, Signal y WireGuard. «X25519 + AES-GCM», en la aplicación de escritorio, genera un par de claves efímero para cada mensaje, acuerda un secreto con la clave pública del destinatario y cifra con AES-GCM: el patrón ECIES.

ECDSA y el nonce

El algoritmo de firma digital de curva elíptica, propuesto por Scott Vanstone en 1992 y estandarizado por ANSI (1999) y el NIST (2000), firma el hash $h$ de un mensaje con la clave privada $d$ (clave pública $Q = d G$ ) en una curva cuyo punto base $G$ tiene orden primo $n$ :

elegir un nonce aleatorio $k \in [1, n - 1]$ y tomar $r = (k G)_{x} mod n$ ;
tomar $s = k^{- 1} (h + r d) mod n$ ; la firma es $(r, s)$ .

El verificador calcula $u_{1} = h s^{- 1}$ , $u_{2} = r s^{- 1}$ y acepta si $(u_{1} G + u_{2} Q)_{x} \equiv r$ . ECDSA sobre la curva P-256 del NIST firma la mayoría de los certificados TLS, las passkeys y las tarjetas bancarias. Su punto débil es el nonce.

Proposición (un nonce repetido filtra la clave)

Si se firman dos mensajes con hashes $h_{1} \neq h_{2}$ con el mismo nonce $k$ (se nota porque $r$ es el mismo), entonces

k = \frac{h_{1} - h_{2}}{s_{1} - s_{2}} mod n, d = \frac{s_{1} k - h_{1}}{r} mod n .

Demostración

$s_{1} k = h_{1} + r d$ y $s_{2} k = h_{2} + r d$ . Restando, $(s_{1} - s_{2}) k = h_{1} - h_{2}$ , que da $k$ ; después la primera ecuación da $d$ . Incluso unos pocos bits sesgados de $k$ en muchas firmas bastan para recuperar $d$ con técnicas de retículos.

En 2010 el grupo fail0verflow mostró que Sony firmaba el software de la PlayStation 3 con el mismo $k$ siempre, recuperó la clave privada de Sony y pudo firmar cualquier cosa. En 2013 un fallo en el generador de números aleatorios de Android hizo que los monederos de Bitcoin repitieran nonces, y les robaron las monedas. La solución es no sacar nunca $k$ al azar: derivarlo de la clave y del mensaje (RFC 6979, 2013).

Ed25519

Bernstein, Niels Duif, Tanja Lange, Peter Schwabe y Bo-Yin Yang diseñaron Ed25519 (2011) sobre una versión en forma de Edwards de Curve25519, con fórmulas de suma completas (sin casos excepcionales) y un nonce derivado de forma determinista de un hash de la clave privada y del mensaje. Es rápido, sus claves ocupan 32 bytes y sus firmas 64, y no hay un nonce aleatorio que pueda salir mal. Lo usan SSH, Signal, Tor, Git y la firma de módulos del núcleo de Linux; lo estandarizan la RFC 8032 (2017) y FIPS 186-5 (2023).

En qué curvas confiar

Las curvas P-256 y P-384 del NIST se generaron en 1999 a partir de semillas que nunca se explicaron. En 2013 los documentos de Snowden confirmaron que la NSA había puesto una puerta trasera en Dual_EC_DRBG, un generador de números aleatorios de curva elíptica estandarizado por el NIST en 2006: quien conociera la relación secreta entre sus dos puntos podía predecir su salida. No se ha encontrado ninguna debilidad en la propia P-256, pero el episodio convirtió los parámetros «rígidos» y explicables, como los de Curve25519, en un requisito de diseño (el proyecto SafeCurves de Bernstein y Lange). La aplicación de escritorio ofrece las dos familias: ECDSA P-256 por compatibilidad, Ed25519 y X25519 como primeras opciones. Todas ellas, igual que RSA, caen ante el algoritmo de Shor.

Para saber más

Neal Koblitz, «Elliptic Curve Cryptosystems», Mathematics of Computation 48, 1987; Victor Miller, «Use of Elliptic Curves in Cryptography», CRYPTO 1985.
Joseph Silverman y John Tate, Rational Points on Elliptic Curves (1992; 2.ª ed. 2015).
Daniel J. Bernstein, «Curve25519: new Diffie-Hellman speed records», PKC 2006; Bernstein et al., «High-speed high-security signatures», CHES 2011.
fail0verflow, «Console Hacking 2010: PS3 Epic Fail», 27.º Chaos Communication Congress.

§Sumar puntos con una regla

§Curvas sobre un cuerpo finito

§El logaritmo discreto en una curva

§ECDH y X25519

§ECDSA y el nonce

§Ed25519

§En qué curvas confiar

§Para saber más