cifrado
A finales del 2022, la comunidad TI se vio sacudida por un estudio presentado por un grupo de científicos chinos en el que afirmaban que en un futuro próximo sería posible descifrar el algoritmo de cifrado RSA con una longitud de clave de 2048 bits, lo cual es fundamental para el funcionamiento de los protocolos de internet, al combinar con habilidad la computación clásica y cuántica. Pero ¿es real esta amenaza? Averigüémoslo.
Los fundamentos cuánticos
Hace tiempo que sabemos de la capacidad teórica de un ordenador cuántico para realizar una factorización ultrarrápida de números enteros gigantes y, por lo tanto, hacer coincidir las claves para una serie de algoritmos cifrados asimétricos, incluido el cifrado RSA. En este artículo de nuestro blog ya explicábamos con detalle qué es un ordenador cuántico, cómo funciona y por qué es tan complicado de desarrollar. Hasta ahora, todos los expertos habían coincidido en la idea de que probablemente no se construiría un ordenador cuántico lo suficientemente grande como para descifrar RSA antes de unas cuantas docenas de décadas. De hecho, para factorizar un número entero de 2048 bits, medida que suele usarse en las claves RSA, el algoritmo de Shor necesita ejecutarse en un ordenador cuántico con millones de cúbits (bits cuánticos). Es decir, no podemos hablar de un futuro cercano, ya que los mejores ordenadores cuánticos funcionan a 300-400 cúbits y esto se ha conseguido después de décadas de investigación.
Pero este problema del futuro ya se está teniendo en cuenta y los expertos de seguridad ya está pidiendo la adopción de la criptografía postcuántica; es decir, una serie de algoritmos resistentes al hackeo con un ordenador cuántico. Parecía que tendríamos que esperar una década o más para una transición sin problemas, por lo que la noticia de que el RSA-2048 podría aparecer ya durante el 2023 ha resultado totalmente inesperada.
Noticias desde China
Los investigadores chinos han podido factorizar una clave de 48 bits en un ordenador cuántico de 10 cúbits. También calcularon que era posible escalar su algoritmo para usarlo con claves de 2048 bits con un ordenador cuántico con solo 372 cúbits. Pero ese ordenador ya existe, en IBM por ejemplo, por lo que la necesidad de remplazar los sistemas cifrados mediante internet de repente ha dejado de ser un problema del futuro. Se ha prometido un gran avance al combinar el algoritmo de Schnorr (no confundir con el anteriormente mencionado algoritmo de Shor) con un algoritmo cuántico de optimización aproximada (QAOA por sus siglas en inglés) adicional.
La estrategia propuesta del algoritmo de factorización híbrido.
El algoritmo de Schnorr’s se usa supuestamente para una factorización más eficiente de los números enteros mediante el uso de la computación clásica. El grupo chino propone aplicar optimización cuántica en la etapa más intensa de computación de su trabajo.
Cuestiones pendientes
La comunidad matemática mira con escepticismo el algoritmo de Schnorr. El autor de la afirmación de que “esto destruirá el criptosistema RSA” en la descripción del estudio fue sometido a escrutinio y se sostuvo. Por ejemplo, el famoso criptográfico Bruce Schneier afirmó que “funciona bien con pequeños módulos (aproximadamente del mismo tipo que los que ha probado el grupo chino), pero se desmorona con cifras de mayor tamaño”. Y nadie ha podido demostrar que este algoritmo sea escalable en la práctica.
Aplicar la optimización cuántica en la parte más “pesada” del algoritmo parece una buena idea, pero los expertos en computación cuántica dudan que la optimización QAOA resulte eficiente a la hora de resolver el problema computacional. Se podría usar un ordenador cuántico en esta etapa, pero es poco probable que consiguiera ahorrar tiempo. De hecho, los propios autores del trabajo mencionan estas dudas al final del informe, en las conclusiones:
Cabe destacar que el acelerón cuántico del algoritmo no está claro debido a la ambigua convergencia de QAOA.
…
Además, este acelerón cuántico no se conoce, todavía queda un largo camino para romper el RSA cuánticamente.
Por consiguiente, parece que, aunque implementes este algoritmo híbrido en un sistema cuántico + clásico, tardarás lo mismo en conocer las claves del RSA que con un ordenador corriente.
La guinda del pastel es que, además del número de cúbitos, hay otros parámetros importantes en un ordenador cuántico, como los niveles de interferencia y los errores y el número de puertas. A juzgar por la combinación de los parámetros requeridos, probablemente ni siquiera los ordenadores más prometedores del 2023-2024 sean apropiados para la ejecución del algoritmo chino en la escala deseada.
Conclusiones
Mientras que la revolución cifrada se sigue retrasando, la repercusión sobre este estudio destaca dos desafíos relacionados con la seguridad. En primer lugar, a la hora de elegir un algoritmo resistente cuánticamente entre las numerosas propuestas de “estándar postcuántico”, las estrategias algebraicas (como el ya mencionado algoritmo de Schnorr) deberían estudiarse minuciosamente. Y, en segundo lugar, se debe dar prioridad a los proyectos que fomenten la transición hacia la criptografía postcuántica. A pesar de todo, se seguirá restando importancia a este problema hasta que sea demasiado tarde.
