¿Hay criptografía después del gato?

O lo que es lo mismo, ¿qué va a pasar con la criptografía una vez los ordenadores cuánticos se desarrollen? Permítanme explicarme. Actualmente la criptografía está basada en un concepto muy simple: Con la potencia actual de computación es imposible responder al desafío criptográfico en un periodo razonable de tiempo.  Casi toda la criptografía se basa en funciones matemáticas unidireccionales, funciones matemáticas que son sencillas de calcular pero muy difíciles de invertir.

Un ejemplo muy claro de estas funciones es el cálculo del hash. Es sencillo calcular el hash de cualquier entrada, pero imposible calcular la entrada a partir del hash. En teoría. Y con la tecnología actual, claro… Porque si fuera posible calcular la entrada a partir del hash en un plazo razonable de tiempo sería imposible utilizarlo para probar la integridad del mensaje. 

La factorización de números presenta un problema parecido. Muchas funciones criptográficas actuales (RSA por ejemplo) se basan en la dificultad de factorizar un número grande si dicho número es el producto de dos números primos lo suficientemente grandes. Conociendo los dos factores, la multiplicación es una tarea sencilla, pero la dificultad de la operación inversa hace que los algoritmos de clave pública y privada sean seguros.

Esta situación cambia cuando la computación cuántica entra en juego. La computación cuántica difiere de la tradicional en que no se basa en estados discretos de la información (0 o 1) sino en una superposición de estados, por lo que cada bit (en computación cuántica recibe el nombre de qubit) son 0 y 1 a la vez. El fenómeno de superposición cuántica se entiende mejor con la paradoja del gato de Schrödinger. Hasta que no se observa el estado del gato (se abre la caja y se comprueba si el veneno se ha activado o no) el gato está en un estado que podríamos resumir como “estar a la vez vivo y muerto” (50% vivo y 50% muerto). El fenómeno de la superposición permite realizar cálculos suponiendo que el valor del qubit es tanto 0 como 1, lo que se traduce en multiplicar la capacidad de ejecutar operaciones paralelas. Así un ordenador cuántico de sólo 30 qubits equivaldría a uno tradicional de 10 Teraflops (Un procesador Intel core i7 920 @3.4ghz tiene una capacidad de 70 Gigaflops, 142 veces menos)

Peter Shor describió en 1994 un algoritmo cuántico que reduce enormemente el tiempo de computación de la factorización de un número frente a la computación tradicional. Este algoritmo fue implementado en 2001 por el grupo de computación cuántica de IBM y aunque el experimento era sencillo, pues consistió en factorizar el número 15 un 50% de las veces (es un algoritmo probabilístico), permitió demostrar la validez del algoritmo. Desde 2001 se ha ido evolucionando y en 2016, el número más grande factorizado por una computadora cuántica es 200.099, factorizado mediante el algoritmo del temple cuántico. 

La computación cuántica ha llegado para quedarse y tiene una capacidad enorme para cambiar la forma en la que hacemos las cosas actualmente. Es verdad que está lejos de poder factorizar los números que se manejan actualmente en RSA, en el que los primos utilizados actualmente son del orden de 10²⁰⁰ y con tendencia a crecer a medida que aumenta la capacidad de los ordenadores. Sin embargo, también es verdad que es una carrera perdida a la larga. Asumámoslo. Tarde o temprano RSA será inseguro.

Quizá suceda lo mismo que con IPv6 y eso del agotamiento de las direcciones IPv4, que parece que nunca llega, y consigamos mantener viva esta criptografía gracias a incrementar el tamaño de los números primos o las claves, pero debemos empezar a pensar en criptografía que sea resistente a la aparición de la computación cuántica, además de serlo de la computación tradicional.

Esa criptografía es la que recibe el nombre de criptografía postcuántica y, actualmente, se investiga en las siguientes líneas:

• Criptografía basada en retículos: Criptografía de clave asimétrica cuyas primitivas se basan en retículos. Los criptosistemas basados en retículos son bastante eficientes y sencillos de implementar, pero la resolución de las matemáticas subyacentes es complicada y aparentemente resistente a la computación cuántica que no ha logrado todavía encontrar un algoritmo con mayor eficiencia que los que utilizan computación tradicional.
• Criptografía basada en polinomios de múltiples variables: También de clave asimétrica que se basa en polinomios de múltiples variables en un campo finito. Su utilidad se ha demostrado para la realización de firma digital, no habiéndose podido aprovechar para la realización de criptosistemas seguros.
• Criptografía basada en código: Incluye sistemas criptográficos que se basan en códigos de corrección de errores como el McEliece, propuesto en 1978 y que aún no se ha conseguido romper. A pesar de ser bastante rápidos, el tamaño de las claves que se manejan es un problema. En el algoritmo original, la clave tenía un tamaño de 262.000 bits y algunos sistemas que han reducido este tamaño introduciendo más estructura en la clave se han demostrado vulnerables a ataques y por tanto inseguros. Se han propuesto sistemas para la realización de firma digital utilizando este tipo de criptografía, pero se ha demostrado más útil en la creación de esquemas de cifrado. Para resistir la aparición de computadoras cuánticas, el tamaño de claves propuesta ronda los 8.400.000 bits.
• Firmas basadas en hash: que incluye sistemas como la firma de Lamport-Diffie o el sistema de Merkle, que inventó este tipo de criptografía en los 70. Su principal contratiempo es que para cada clave pública basada en hash, hay un límite al número de firmas que se pueden hacer con su correspondiente clave privada. El límite puede ser incrementado, pero eso también incrementa el tamaño de la firma. Además el que firma debe llevar el control del número exacto de mensajes firmados previamente, y cualquier inexactitud en su número hará inseguro el sistema.
• Otros algoritmos, como el intercambio de claves mediante la evaluación de isogenias en curvas elípticas supersingulares, todavía están en desarrollo, pero se consideran buenos candidatos para ser incluidos en el grupo de criptografía postcuántica.

Estos algoritmos postcuánticos actuales no parecen que vayan a poder reemplazar a los tradicionales, ya que presentan como problema que los tamaños de las claves es mucho mayor que el tamaño que utilizan aquellos algoritmos que pretenden reemplazar.

Este aumento del tamaño de las claves afecta de forma notable a muchos protocolos de internet, como a TLS o a IKE, hasta el punto que puede ser necesario modificarlos para poderlos implementar, y esto no se puede hacer a la ligera. Además, ninguno proporciona seguridad total frente a todos los ataques cuánticos, por lo que al evolucionar estos, se podrán descubrir nuevas formas de romper estos sistemas de cifrado.

Esto es algo que pasa en la actualidad donde nuevos avances en la computación dejan inservibles protocolos considerados seguros hasta ahora, como le ha pasado a MD5, SHA-1, DES…