Secretos en público: Diffie–Hellman y RSA

Todos los cifrados vistos hasta ahora son simétricos: la misma clave cifra y descifra, así que las dos partes deben compartirla antes de poder decirse nada en secreto. Los ejércitos repartían los libros de claves con mensajeros; los bancos tenían responsables de claves que llevaban sobres lacrados. Con $n$ personas que quieren hablar todas en privado hacen falta $n(n-1)/2$ claves. En Internet, donde quieres hablar con una tienda de la que nunca habías oído hablar, es imposible. La salida llegó en tres pasos, entre 1974 y 1977, y cambió lo que es la criptografía.

§Los puzles de Merkle

En 1974 Ralph Merkle, estudiante de grado en Berkeley, propuso un proyecto para acordar una clave en público; su profesor lo rechazó. Su idea: Bob envía a Alicia un millón de puzles, cada uno un mensaje corto cifrado con una clave deliberadamente débil que cuesta un minuto romper. Cada puzle contiene un identificador aleatorio y una clave secreta. Alicia elige un puzle al azar, lo rompe y anuncia su identificador; ahora los dos comparten su clave. Un espía que no sabe qué puzle eligió Alicia tiene que romper, de media, medio millón. La ventaja solo es cuadrática (un minuto para Alicia, un año para el espía), pero fue la primera prueba de que se podía construir un secreto compartido en público. El artículo apareció, tras años de rechazos, en 1978.

§Diffie–Hellman

En noviembre de 1976 Whitfield Diffie y Martin Hellman publicaron New Directions in Cryptography, que empieza así: «Hoy estamos al borde de una revolución en la criptografía». Su acuerdo de claves usa aritmética módulo un primo.

Alicia y Bob acuerdan en público un primo grande $p$ y un generador $g$. Alicia elige un secreto $a$ y envía $A=g^{a}modp$; Bob elige un secreto $b$ y envía $B=g^{b}modp$. Entonces

y los dos tienen $s=g^{ab}modp$. Una espía ve $p$, $g$, $A$ y $B$. Para obtener $s$ parece necesitar $a$ a partir de $A=g^a$: el logaritmo discreto. La exponenciación módulo $p$ es rápida (ver más abajo «elevar al cuadrado y multiplicar»); su inversa, para primos de 2048 bits bien elegidos, está fuera del alcance de todos los algoritmos clásicos conocidos.

Diffie–Hellman protege frente a quien escucha, no frente a un intermediario activo que acuerda una clave con Alicia y otra con Bob. Para derrotarlo hay que autenticar los valores públicos, que es el trabajo de las firmas. Con ese añadido (y con curvas elípticas, capítulo 09), Diffie–Hellman es como empieza cada conexión TLS 1.3. Diffie y Hellman recibieron por él el premio Turing en 2015.

§Descubierto antes, en secreto

En 1997 la agencia británica de inteligencia de señales, el GCHQ, reveló que sus propios matemáticos habían llegado antes. James Ellis había mostrado en 1970 que el «cifrado no secreto» era posible en principio; en 1973 Clifford Cocks, un recluta de 22 años recién llegado, encontró en una tarde un esquema práctico, esencialmente RSA; en 1974 Malcolm Williamson encontró lo que equivale a Diffie–Hellman. Al ser material clasificado, nada de ello se usó ni se publicó, y el mundo aprendió la criptografía de clave pública de los académicos.

§La teoría de números detrás de RSA

Demostración

Los números $a,2a,\dots ,(p-1)a$ son no nulos y distintos dos a dos módulo $p$ (si $ia\equiv ja$ entonces $p\mid (i-j)a$, así que $i=j$), luego son $1,2,\dots ,p-1$ en algún orden. Multiplicándolos todos: $a^{p-1}(p-1)!\equiv (p-1)!(\mathrm{mod}p)$, y $(p-1)!$ es invertible módulo $p$.

La demostración es la misma que la de Fermat, aplicada a los $\phi (n)$ restos invertibles; el teorema de Euler es el teorema de Lagrange para el grupo ${\mathbb{Z}}_n^{\ast }$.

§RSA

En 1977 tres investigadores del MIT, Ron Rivest, Adi Shamir y Leonard Adleman, pasaron un año intentando construir un cifrado de clave pública (Rivest y Shamir proponían, Adleman rompía) hasta que, tras una cena de Pascua judía en abril, Rivest escribió el esquema:

1. Elegir dos primos grandes aleatorios $p$ y $q$, y tomar $n=pq$ y $\phi (n)=(p-1)(q-1)$.
2. Elegir $e$ coprimo con $\phi (n)$ (hoy casi siempre $e=65537$) y calcular $d=e^{-1}mod\phi (n)$ con el algoritmo de Euclides extendido.
3. La clave pública es $(n,e)$; la clave privada es $d$ (y $p$, $q$).
4. Cifrar un número $0\le m<n$ como $c=m^{e}modn$; descifrar como $m=c^{d}modn$.

Demostración

Como $ed\equiv 1(\mathrm{mod}\phi (n))$, escribimos $ed=1+t(p-1)(q-1)$. Módulo $p$: si $p\nmid m$, Fermat da $m^{ed}=m\cdot (m^{p-1}{)}^{t(q-1)}\equiv m$; si $p\mid m$, los dos lados son $0$. Lo mismo ocurre módulo $q$. Así que $p$ y $q$ dividen a $m^{ed}-m$, y como son primos distintos, también lo divide $n=pq$ (es el teorema chino del resto: un resto módulo $pq$ queda determinado por sus restos módulo $p$ y módulo $q$).

Quien sepa factorizar $n$ calcula $\phi (n)$ y después $d$, así que RSA es como mucho tan difícil como factorizar. Aquel agosto, la columna de Martin Gardner en Scientific American describió RSA y publicó un reto: un mensaje cifrado con un módulo de 129 cifras, RSA-129, con un premio de 100 dólares. Los autores calcularon que llevaría 40.000 billones de años. Se factorizó en 1994 gracias a 600 voluntarios coordinados por Internet; el mensaje decía «THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE».

Elevar al cuadrado y multiplicar

Calcular $m^d$ con un $d$ de 3.000 bits multiplicando repetidamente llevaría $2^{3000}$ pasos. En lugar de eso, se lee el exponente en binario y, para cada bit, se eleva al cuadrado el resultado acumulado y se multiplica por $m$ si el bit es 1: unos ${\log }_{2}d$ cuadrados y como mucho otras tantas multiplicaciones, todas módulo $n$. Este algoritmo, que ya se conocía en la India hace más de dos mil años para calcular potencias, es lo que hace práctico RSA (y Diffie–Hellman).

El RSA de libro de texto no es seguro

El esquema anterior, el «RSA de libro de texto», es determinista (el mismo $m$ da siempre el mismo $c$, así que un atacante puede comprobar conjeturas) y maleable ($c\cdot 2^e$ se descifra como $2m$). El RSA real cifra un mensaje con relleno aleatorio. El antiguo relleno de PKCS#1 v1.5 cayó en 1998 ante el ataque de Daniel Bleichenbacher, un oráculo de relleno como el de Vaudenay (capítulo 05), que reaparece una y otra vez en las implementaciones de TLS (ROBOT, 2017). OAEP, de Mihir Bellare y Phillip Rogaway (1994), añade aleatoriedad mediante una mezcla al estilo Feistel con un hash, y es demostrablemente seguro con hipótesis razonables; es lo que usa el RSA-OAEP de la aplicación de escritorio, con SHA-256 y claves de 3.072 bits. RSA cifra como mucho unos cientos de bytes, así que en la práctica cifra una clave simétrica: cifrado híbrido.

§¿Qué tamaño debe tener la clave?

La factorización ha mejorado sin parar: la criba cuadrática (Carl Pomerance, 1981) y la criba general del cuerpo de números (años noventa), cuyo tiempo de ejecución es aproximadamente

subexponencial en el número de cifras. RSA-768 (232 cifras) se factorizó en 2009; RSA-250 (250 cifras, 829 bits), en 2020, con unos 2.700 años-núcleo de cálculo. Un módulo de 2.048 bits da unos 112 bits de seguridad; uno de 3.072 bits, unos 128. Un ordenador cuántico grande con el algoritmo de Shor factorizaría en tiempo polinómico y rompería RSA y Diffie–Hellman de cualquier tamaño; Math of Quantum explica cómo, y el capítulo 10, qué los sustituye.

§Firmas digitales

Si se usa RSA al revés se obtiene una firma: el dueño de $d$ calcula $s=h^{d}modn$ para el hash $h$ de un mensaje, y cualquiera puede comprobar que $s^e\equiv h(\mathrm{mod}n)$ con la clave pública. Solo quien tiene $d$ pudo producir $s$, así que una firma da autenticidad, integridad y no repudio. Como en el cifrado, el hash debe rellenarse: RSA-PSS (Bellare y Rogaway, 1996) lo aleatoriza y tiene una demostración de seguridad ajustada; es uno de los algoritmos de firma de la aplicación de escritorio.

Las firmas hacen utilizable el resto de la criptografía de clave pública. Un certificado es una clave pública firmada por una autoridad de certificación; tu navegador confía en unas decenas de autoridades, y ellas avalan las claves de millones de webs. Cuando empieza TLS, el certificado del servidor autentica su parte del Diffie–Hellman, lo que derrota al intermediario. Las actualizaciones de software, los pasaportes, el correo (S/MIME, PGP), los commits de Git y las criptomonedas se apoyan en firmas. El capítulo siguiente las hace, a ellas y a Diffie–Hellman, mucho más pequeñas.

§Para saber más

1. Whitfield Diffie y Martin Hellman, «New Directions in Cryptography», IEEE Transactions on Information Theory 22(6), 1976.
2. Ron Rivest, Adi Shamir, Leonard Adleman, «A Method for Obtaining Digital Signatures and Public-Key Cryptosystems», Communications of the ACM 21(2), 1978.
3. Ralph Merkle, «Secure Communications over Insecure Channels», Communications of the ACM 21(4), 1978.
4. James Ellis, «The History of Non-Secret Encryption» (escrito en 1987, publicado por el GCHQ en 1997).
5. Dan Boneh, «Twenty Years of Attacks on the RSA Cryptosystem», Notices of the AMS 46(2), 1999.