Que se pueda cifrar información con números primos es en sí llamativo, pero el concepto subyacente roza lo asombroso. Durante siglos, los sistemas de cifrado han tenido un grave talón de Aquiles: utilizamos la misma clave para cifrar y para descifrar. Si le damos a una persona una clave para que pueda enviarnos un mensaje cifrado, le estamos dando también la posibilidad de descifrar todos los mensajes cifrados con esa clave.
La situación mejoraría si las claves de cifrado y de descifrado fuesen distintas. Sería algo así como un buzón de correos: cualquiera puede introducir una carta, pero solamente el poseedor de la llave puede abrir el buzón para leer las cartas. La clave para cifrar sería accesible para cualquiera que desease cifrar un mensaje, en tanto que la clave de descifrado solamente estaría accesible al destinatario.
Usar claves distintas para cifrar y para descifrar se consideró algo imposible durante muchos años, una especie de santo grial de la criptografía. Pero en los años setenta, lo imposible se hizo realidad. Investigadores de Estados Unidos y el Reino Unido descubrieron los principios de lo que hoy conocemos con el nombre de criptografía de clave pública, a veces llamada también criptografía asimétrica. En lo que sigue, me referiré a ella mediante las siglas en inglés PKC (Public Key Criptography).
La PKC se basa en la existencia de dos claves. Una de ellas (la clave pública) puede diseminarse a los cuatro vientos para que cualquiera pueda usarla; la otra (la clave privada) permanece firmemente bajo el control del dueño. Cualquiera puede cifrar mensajes con la clave pública, pero solamente el poseedor de la clave privada asociada podrá descifrarlos. La PKC permite resolver otros problemas como el intercambio de claves o la firma digital.
La PKC fue desarrollada por los investigadores norteamericanos Whitfield Diffie, Martin Hellman y Ralph Merkle a finales de los años 70. No fueron los primeros, ya que pocos años antes sus homólogos británicos James Ellis, Clifford Cocks y Malcolm Williamson habían descubierto los principios de la PKC. Por desgracia para ellos, trabajaban para la agencia criptoanalítica británica GCHQ, y su trabajo se mantuvo en secreto durante muchos años (solamente a finales de los años 90 se les permitió hablar de su papel en la PKC). Fueron los norteamericanos quienes revolucionaron el campo de la criptografía civil y se llevaron todos los honores.
La PKC basa su fortaleza en problemas matemáticos difíciles. Las claves pública y privada no son independientes, y en teoría podría obtenerse una de ellas conociendo la otra; la seguridad del sistema se basa en escoger un problema tan difícil que la posibilidad teórica de resolverlo derive en una imposibilidad práctica. No es fácil encontrar un problema matemático adecuado. Algunos no son lo bastante difíciles, otros lo son demasiado, o bien las claves de cifrado son demasiado largas.
Uno de los primeros ejemplos de PKC se basó en lo que se conoce como “problema de la mochila” (knapsack problem). Podemos enunciarlo de la siguiente manera: dado un conjunto de elementos, cada uno de ellos de un peso determinado, ¿es posible llenar una mochila con algunos de ellos, de forma que la mochila pese una determinada cantidad? O dicho matemáticamente: dados un conjunto de valores V1, V2… Vn y una suma S, determínense los valores Ai (cero o uno) que cumplan la condición:
S=A1*V1 +A2*V2… + An*Vn
En la película Jungla de Cristal 3: la venganza, el detective McClane y su compañero deben resolver una variante del problema de la mochila. En una fuente pública hay una bomba con una báscula incorporada. Las instrucciones del malo para desactivarla son sencillas:
“Debería haber dos garrafas en la fuente, una de cinco y otra de tres galones. Llene una de ellas con cuatro galones justos de agua y póngala sobre la báscula; el contador se parará… si siguen vivo dentro de cinco minutos volveremos a hablar”.
Si quiere usted probar suerte, adelante, es fácil. Cuando tenemos pocos elementos, el problema es fácilmente tratable; pero conforme el número de elementos n aumenta, el problemas se hace cada vez más difícil. Eso forma la base de un sistema de cifrado asimétrico diseñado por Ralph Merkle y Martin Hellman en 1978[1].
Puesto que los valores Ai son ceros o unos, la secuencia (A1, A2, A3… An) se escoge de forma que sean una representación binaria del mensaje. Los procesos de cifrado y descifrado están basados en dos series distintas de valores (V1, V2, V3… Vn). La diferencia entre ambas estriba en que la clave privada está formada por lo que se llama una secuencia supercreciente, en la que un valor es mayor que la suma de los valores anteriores, o sea: Vk > V1+V2+V3… +V(k-1).
El lector tiene en sus bolsillos un ejemplo de secuencia supercreciente. Fíjese y verá cómo cualquier billete o moneda tiene más valor que todas las de menor cuantía juntas. Tener monedas en sucesión supercreciente facilita las transacciones. Si tiene usted que pagar 62 céntimos, no tiene más que tomar una moneda de 50, una de 10 y una de 2. Por supuesto, existen otras posibilidades (50+5+5+1+1 céntimos), pero no son muchas. Con un sistema de monedas no supercreciente, habría muchas más posibilidades, y tendríamos que llevar muchas más monedas en el bolsillo.
El hecho de que la clave privada esté formada por una sucesión supercreciente, y la clave pública no, garantiza que el proceso de descifrado será sencillo si se conoce la clave (espero que me crea en esto, porque no quiero aburrirle con detalles matemáticos); en caso contrario, es lo que los matemáticos llaman un problema NP-completo. Para entendernos, es el tipo de problemas que no puede resolverse con un algoritmo matemático que, al final de un cierto conjunto finito de pasos binarios, diga “sí, hay solución” o “no, no hay solución”.
Al principio se creyó que el problema de la mochila podría ser usado como “problema duro” para basar en él un sistema de cifrado. Sin embargo, Adi Shamir demostró en 1984 que el problema de la mochila puede “casi resolverse” en un tiempo relativamente corto. Ese “casi resolverse” significa que no hay seguridad de resolverlo, pero se puede considerar resuelto con una probabilidad muy alta de éxito[2].
Durante los años setenta y ochenta se pusieron a prueba muchos problemas matemáticos difíciles. Uno de ellos finalmente dio origen a un sistema de clave pública conocido con el nombre de RSA, por las iniciales de sus creadores: Rivest, Shamir, Adleman. Fue uno de los más importantes hitos que permitieron crear una Internet segura, con páginas web protegidas mediante criptografía. Su éxito fue tal que la empresa que comercializa RSA es en la actualidad una de las más importantes en el campo de la seguridad en Internet[3].
A partir de aquí, nuestro camino se llena de matemáticas. El siguiente apartado será tan sencillo como puedo explicarlo, pero aun así puede que usted no quiera volver a clase de matemáticas. Llega, por tanto, el momento en el que usted escoge. Bienvenidos a las matemáticas interactivas. Por favor, escoja una de las dos opciones:
—Continuar adelante (Apartado 2)
—Saltar la explicación matemática (Apartado 3)