La clave pública

La criptografía de clave pública resuelve el problema que ningún cifrado anterior había podido resolver: cómo dos personas que nunca se han visto y que solo pueden hablar por un canal que todo el mundo escucha acuerdan un secreto. Durante dos mil años, desde el cifrado de César hasta la libreta de un solo uso, cifrar exigía compartir antes una clave, y compartir la clave exigía un mensajero, una valija, un encuentro. En 1976 Whitfield Diffie y Martin Hellman mostraron que no hacía falta: dos personas podían intercambiar números a la vista de todos y acabar con un secreto común que ningún oyente puede calcular. Sin ese hallazgo no existiría el comercio electrónico, ni la banca en línea, ni la mensajería cifrada, ni el candado que aparece en el navegador.

El problema se entiende con el caso más famoso de la Primera Guerra Mundial. En enero de 1917 el ministro alemán Arthur Zimmermann envió un telegrama a México proponiendo una alianza contra Estados Unidos, cifrado con un código de libro: cada palabra o sílaba era un grupo de cifras que había que buscar en un volumen que solo tenían las embajadas. Los británicos lo descifraron porque tenían copias parciales del libro, obtenidas de un barco hundido y de un agente en Persia. El código era bueno; lo que falló fue la distribución de la clave. Y esa es la debilidad estructural de toda la criptografía clásica: cuanto más gente necesita comunicarse en secreto, más claves hay que repartir por adelantado y más ocasiones de que una caiga en manos ajenas. Un ejército puede permitirse mensajeros; una red de millones de personas que compran, cobran y hablan entre sí, no.

La solución de Diffie y Hellman se apoya en una operación fácil de hacer y difícil de deshacer. Se elige un número primo p y un número g menor que él, los dos públicos. Alicia elige en secreto un número a y envía a Benito g elevado a a módulo p, es decir, el resto de dividir esa potencia entre p. Benito hace lo mismo con su secreto b. Cada uno eleva lo que ha recibido a su propio secreto, y los dos obtienen el mismo número, g elevado a a por b módulo p, porque el orden en que se elevan las potencias no importa. Eva, que ha oído p, g y las dos potencias, tendría que recuperar a a partir de g elevado a a: el logaritmo discreto. Con los números de dos cifras de la figura se hace probando, y el contador de Eva dice cuántas multiplicaciones necesita. Con el primo de siete cifras sigue siendo poco. Con los primos de seiscientas cifras que se usan hoy, no se conoce ningún método que termine en un tiempo comparable a la edad del universo, mientras que las potencias que calculan Alicia y Benito se hacen en milisegundos. La seguridad no está en que Eva no sepa cómo funciona el sistema —el sistema es público— sino en una asimetría de esfuerzo: multiplicar es barato y deshacer la multiplicación es caro.

Diffie y Hellman propusieron también, sin conseguir construirlo, algo más ambicioso: un cifrado en el que la clave para cerrar y la clave para abrir fueran distintas, de modo que una pudiera publicarse. Ron Rivest, Adi Shamir y Leonard Adleman lo construyeron en 1977, en el MIT, después de un año de intentos —Rivest cuenta que la idea le llegó una noche tras una cena de Pésaj— y se llama RSA por sus iniciales. Se toman dos primos grandes, p y q, y se publica su producto n junto con un exponente e. Cualquiera puede cifrar un mensaje m calculando m elevado a e módulo n. Para descifrar hace falta un exponente d que solo se puede calcular conociendo p y q por separado, y obtenerlos a partir de n es factorizar, el otro problema fácil de plantear y difícil de resolver de la aritmética. La tabla de la figura hace RSA con primos de dos cifras y muestra cada número: el cifrado, el descifrado que devuelve exactamente el mensaje, y las divisiones que necesita Eva para romperlo. Con un n de 617 cifras, el estándar actual, la mayor factorización conseguida hasta hoy se queda muy lejos.

La clave pública trajo algo que la criptografía clásica no tenía: la firma. Si Alicia cifra un mensaje con su clave privada, cualquiera puede descifrarlo con su clave pública, y el hecho de que salga algo con sentido demuestra que lo cifró ella y nadie más. Eso es una firma digital, y con ella se resuelve el problema que ni Diffie-Hellman resuelve por sí solo: saber que el g elevado a b que llega viene de Benito y no de Eva haciéndose pasar por él. Los certificados que hay detrás del candado del navegador son firmas encadenadas: una autoridad firma la clave pública de un sitio web, y el navegador trae de fábrica las claves de las autoridades. En la práctica, los sistemas actuales usan la clave pública solo para acordar un secreto y firmar, y cifran el grueso del tráfico con un cifrado simétrico rápido con la clave acordada, porque las potencias de seiscientas cifras son lentas.

Dos notas para terminar. La primera es que el descubrimiento se hizo dos veces. James Ellis, Clifford Cocks y Malcolm Williamson, del servicio de cifrado británico GCHQ, habían encontrado entre 1970 y 1974 tanto la idea general como el equivalente de RSA y el de Diffie-Hellman, y no pudieron publicarlo; se supo en 1997, cuando el GCHQ desclasificó los informes. Ralph Merkle, estudiante en Berkeley, había propuesto en 1974 una manera distinta de acordar una clave en público, que su profesor rechazó como trabajo de curso, y que se publicó en 1978. La segunda es que la asimetría de esfuerzo es un hecho empírico, no un teorema: nadie ha demostrado que factorizar o calcular logaritmos discretos sea difícil, solo que nadie sabe hacerlo deprisa con los ordenadores que existen. Peter Shor demostró en 1994 que un ordenador cuántico suficientemente grande haría las dos cosas en un tiempo razonable, y por eso desde 2016 se estandarizan cifrados «poscuánticos» basados en otros problemas. La figura sirve también para eso: recorrer los primos de la lista hacia arriba y ver cómo crece el trabajo de Eva es ver, en pequeño, la apuesta sobre la que descansa toda la seguridad de internet.