¿Las computadoras cuánticas podrán descifrar en 2023 el cifrado RSA?

A finales del 2022, la comunidad TI se sacudió tras un estudio presentado por un grupo de científicos chinos donde afirmaban que sería posible descifrar el algoritmo de cifrado RSA con una longitud de clave de 2048 bits en un futuro cercano, 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 ¿esta amenaza es real? Averigüémoslo.

Los fundamentos cuánticos

Hace tiempo que conocemos de la capacidad teórica de una computadora cuántica para realizar una factorización ultrarrápida de números enteros gigantes y, por ende, hacer coincidir las claves para una serie de algoritmos cifrados asimétricos, incluido el cifrado RSA. En este artículo de nuestro blog ya habíamos explicado con detalle lo que es una computadora cuántica, cómo funciona y por qué es tan difícil de desarrollar. Hasta ahora, todos los expertos coincidían en la idea de que quizá una computadora cuántica no podría hacerse 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 una computadora cuántica con millones de cúbits (bits cuánticos). O sea, no hablamos de un futuro cercano, ya que las mejores computadoras cuánticas funcionan a 300-400 cúbits y esto se consiguió tras décadas de investigación.

Pero ya se está tomando en cuenta este problema y los expertos de seguridad ya está pidiendo la adopción de la criptografía postcuántica; o sea, una serie de algoritmos resistentes al hackeo con una computadora cuántica. Al parecer 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 darse durante el 2023 ha sido completamente inesperada.

Noticias desde China

Los investigadores chinos han podido factorizar una clave de 48 bits en una computadora cuántica de 10 cúbits. Calcularon también que era posible escalar su algoritmo para usarlo con claves de 2048 bits con una computadora cuántica con solo 372 cúbits. Pero esa computadora ya existe, en IBM por ejemplo, por lo que la necesidad de remplazar los sistemas cifrados mediante internet ya dejó 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 supuestamente se utiliza 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.

Puntos pendientes

La comunidad matemática ve escéptica 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 en la práctica este algoritmo sea escalable.

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. En esta etapa podría usarse una computadora cuántica, pero es poco probable que ahorre tiempo. De hecho, los propios autores del trabajo mencionan estas dudas en las conclusiones al final del informe:

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 ende, 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 una computadora común.

La cereza del pastel es que, además del número de cúbitos, existen otros parámetros importantes en una computadora cuántica, 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 las computadoras más prometedoras del 2023-2024 sean apropiadas 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. Primero, 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 de forma minuciosa. Y segundo, 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.