La idea que cambió la criptografía.

Durante casi toda su historia, la criptografía tuvo una regla que parecía una ley de la naturaleza: para comunicarse en secreto, las dos partes tenían que compartir antes una clave. El general y su lugarteniente, el banco y su sucursal, el embajador y su cancillería. Quien quisiera hablar en secreto con mil personas necesitaba mil claves y mil mensajeros confiables para repartirlas. Y la firma, entendida como prueba de autoría ante un tercero, ni siquiera estaba en discusión: si las dos partes conocen la misma clave, cualquiera de ellas pudo haber producido el mensaje.

En noviembre de 1976, Whitfield Diffie y Martin Hellman publicaron en la revista IEEE Transactions on Information Theory un artículo que empezaba con una frase deliberadamente provocadora: «Estamos hoy al borde de una revolución en criptografía». No exageraban. «New Directions in Cryptography» proponía dos ideas que hasta entonces nadie había formulado en público: acordar una clave secreta a través de un canal completamente expuesto, y firmar digitalmente con algo que sólo una persona posee pero que cualquiera puede verificar.

Funciones de una vía

Todo lo que sigue descansa en una noción simple de enunciar y difícil de demostrar: una función de una vía es una función f que se calcula con facilidad, pero tal que, dado y = f(x), encontrar algún x que la produzca es inviable en la práctica.

«Inviable» tiene aquí un sentido preciso. No significa imposible, porque siempre se puede probar todas las entradas. Significa que el mejor método conocido requiere una cantidad de operaciones que crece de manera exponencial (o casi) con el tamaño de la entrada, de modo que con parámetros razonables supera cualquier capacidad de cómputo imaginable. Calcular f cuesta un tiempo polinomial en la longitud de x; invertirla, un tiempo que no lo es.

Una función de una vía sirve para guardar contraseñas, pero no alcanza para cifrar ni para firmar: si nadie puede invertirla, tampoco puede hacerlo el destinatario legítimo. Diffie y Hellman propusieron un objeto más sutil, la función de una vía con trampa: imposible de invertir en general, pero fácil de invertir para quien conoce un dato adicional, la trampa. Ese dato es la clave privada. La función, con todo lo necesario para calcularla, es la clave pública.

Aritmética de reloj

El candidato que eligieron Diffie y Hellman viene de la aritmética modular, la de los relojes. Trabajar «módulo p» significa quedarse sólo con el resto de dividir por p: en un reloj de 12 horas, 9 + 5 = 2. Con un primo p, los números del 1 al p 1 forman un grupo bajo la multiplicación: todo número tiene inverso, y existen elementos llamados generadores cuyas potencias recorren el grupo entero.

Para números reales, el logaritmo es una función suave y fácil de aproximar: si 2^x = 1000, x anda cerca de 10. En aritmética modular esa intuición desaparece. Las potencias saltan de un lugar a otro del reloj sin orden visible, y saber dónde cayó una no dice casi nada sobre el exponente. El laboratorio siguiente lo muestra con un reloj de 23 posiciones.

Con 23 posiciones, encontrar el exponente probando es trivial. Con un primo de 3072 bits, el mejor algoritmo conocido, la criba del cuerpo de números, necesita del orden de 2¹²⁸ operaciones. Es el mismo nivel de seguridad que ofrece una clave simétrica de 128 bits, y por eso NIST asocia ambos tamaños en su recomendación de gestión de claves.

El intercambio de Diffie y Hellman

La primera aplicación del artículo de 1976 no fue la firma sino algo que parecía todavía más imposible: que dos personas que nunca se vieron acuerden un secreto hablando en voz alta delante de todos.

1. Parámetros públicos. Ana y Bruno acuerdan, a la vista de todos, un primo p y un generador g. En el ejemplo, p = 23 y g = 5.
2. Secretos propios. Ana elige en privado a = 6; Bruno elige b = 15. Nunca los revelan.
3. Valores públicos. Ana envía A = 5⁶ mod 23 = 8. Bruno envía B = 5¹⁵ mod 23 = 19.
4. Secreto compartido. Ana calcula B^a = 19⁶ mod 23 = 2. Bruno calcula A^b = 8¹⁵ mod 23 = 2. Ambos llegan a g^ab sin haberlo transmitido nunca.

Quien escuchó toda la conversación conoce 23, 5, 8 y 19. Para obtener el 2 necesitaría a o b, es decir, resolver un logaritmo discreto. (En rigor necesita resolver el llamado problema de Diffie y Hellman, que no se sabe si es equivalente al logaritmo discreto pero tampoco se sabe resolver más rápido.) El protocolo tiene una debilidad que el artículo ya intuía: no dice con quién se está hablando. Un intermediario puede hacer un intercambio con cada parte y leerlo todo. La solución a ese problema es, precisamente, la firma digital.

La firma, tal como la imaginaron

La sección del artículo dedicada a la autenticación define con precisión lo que se busca: un mensaje firmado que el receptor pueda verificar, pero que no pueda haber producido él mismo, y que por lo tanto sirva para convencer a un tercero, un juez por ejemplo. Es la propiedad que hoy llamamos no repudio, y es lo que distingue una firma de un simple código de autenticación de mensajes, donde ambas partes comparten la clave y cualquiera pudo generarlo.

El esquema abstracto que proponen sigue siendo el de hoy:

Lo que Diffie y Hellman no tenían era una función con trampa concreta para implementarlo. La encontraron pocos meses después, en el MIT, Ron Rivest, Adi Shamir y Leonard Adleman: la factorización de enteros. Su artículo de 1978 llevaba en el título las palabras «firmas digitales» antes que «criptosistemas de clave pública». RSA es el tema del próximo artículo de esta serie.

Los que llegaron antes, en silencio

La historia tiene un capítulo que sólo se conoció en 1997. En el GCHQ, la agencia británica de inteligencia de señales, James Ellis había formulado en 1970 la idea de un «cifrado no secreto». En 1973 Clifford Cocks, recién incorporado, encontró en una tarde un esquema esencialmente igual a RSA, y en 1974 Malcolm Williamson llegó a un intercambio equivalente al de Diffie y Hellman. Todo quedó clasificado. Por su parte, Ralph Merkle, entonces estudiante en Berkeley, había propuesto en 1974 un protocolo de acuerdo de claves basado en «rompecabezas», que se publicó recién en 1978 y que hoy se reconoce como el primer esquema público de su tipo.

Tres familias de problemas

Medio siglo después, la criptografía de clave pública en uso se apoya en muy pocos problemas matemáticos. Conviene tenerlos presentes, porque determinan qué la amenaza y cómo se mide su fortaleza.

Los tres primeros caen ante un mismo enemigo, el algoritmo de Shor en una computadora cuántica suficientemente grande. Los últimos fueron elegidos justamente porque no se conoce un ataque cuántico eficiente contra ellos. Toda la serie vuelve, de una u otra forma, a esta tabla.

← Todas las notas