Hace tres semanas, el pánico se extendió por algunos rincones del mundo de la seguridad después de que los investigadores descubrieran un avance que, por fin, puso fin al descifrado de los ampliamente utilizados Cifrado RSA esquema al alcance mediante el uso de la computación cuántica.
Los científicos y criptógrafos saben desde hace dos décadas que un método de factorización conocido como algoritmo de Shor hace teóricamente posible que una computadora cuántica con recursos suficientes rompa RSA. Esto se debe a que los números primos secretos que sustentan la seguridad de una clave RSA son fáciles de calcular utilizando el algoritmo de Shor. Calcular los mismos números primos utilizando la computación clásica lleva miles de millones de años.
Lo único que frena este escenario apocalíptico es la enorme cantidad de recursos informáticos necesarios para que el algoritmo de Shor descifre claves RSA de tamaño suficiente. La estimación actual es que romper una clave RSA de 1024 bits o 2048 bits requiere una computadora cuántica con vastos recursos. En concreto, esos recursos son unos 20 millones de qubits y unas ocho horas de ellos funcionando en superposición. (Un qubit es una unidad básica de computación cuántica, análoga al bit binario en la computación clásica. Pero mientras que un bit binario clásico puede representar solo un único valor binario como 0 o 1, un qubit se representa mediante una superposición de múltiples posibles estados.)
Él papel, publicado hace tres semanas por un equipo de investigadores en China, informó haber encontrado un método de factorización que podría descifrar una clave RSA de 2048 bits utilizando un sistema cuántico con solo 372 qubits cuando operaba con miles de pasos de operación. El hallazgo, de ser cierto, habría significado que la caída del cifrado RSA en la computación cuántica podría llegar mucho antes de lo que la mayoría de la gente creía.
La desaparición de RSA es muy exagerada
En la Conferencia Enigma 2023 en Santa Clara, California, el martes, el científico informático y experto en seguridad y privacidad Simson Garfinkel aseguró a los investigadores que la desaparición de RSA fue muy exagerada. Por el momento, dijo, la computación cuántica tiene pocas aplicaciones prácticas, si es que tiene alguna.
“A corto plazo, las computadoras cuánticas son buenas para una cosa, y eso es publicar artículos en revistas prestigiosas”, Garfinkel, coautor con Chris Hoofnagle del libro de 2021 Ley y política para la era cuántica, dijo a la audiencia. “La segunda cosa en la que son razonablemente buenos, pero no sabemos por cuánto tiempo más, es que son razonablemente buenos para obtener financiamiento”.
Incluso cuando la computación cuántica se vuelve lo suficientemente avanzada como para proporcionar aplicaciones útiles, es probable que las aplicaciones simulen física y química y realicen optimizaciones informáticas que no funcionan bien con la computación clásica. Garfinkel dijo que la escasez de aplicaciones útiles en el futuro previsible podría provocar un “invierno cuántico”, similar a las múltiples rondas de inviernos de inteligencia artificial antes de que la IA finalmente despegara.
El problema con el artículo publicado a principios de este mes era su dependencia del algoritmo de Shnorr (que no debe confundirse con el algoritmo de Shor), que se desarrolló en 1994. El algoritmo de Schnorr es un cálculo clásico basado en redes, que son estructuras matemáticas que tienen muchas aplicaciones en criptografía constructiva y criptoanálisis. Los autores que idearon el algoritmo de Schnorr dijeron que podría mejorar el uso del método heurístico de optimización cuántica llamado QAOA.
En poco tiempo, una gran cantidad de investigadores señalaron imperfecciones fatales en el algoritmo de Shnorr que casi lo han desacreditado. Específicamente, los críticos dijeron que no había evidencia que respaldara las afirmaciones de los autores de que el algoritmo de Schnorr logró un tiempo polinomial, a diferencia del tiempo exponencial logrado con los algoritmos clásicos.
El trabajo de investigación de hace tres semanas parecía tomar el algoritmo de Shor al pie de la letra. Incluso cuando supuestamente se mejora con QAOA, algo para lo que actualmente no hay soporte, es cuestionable si proporciona algún aumento de rendimiento.
“En total, este es uno de los artículos de computación cuántica más engañosos que he visto en 25 años, y he visto… muchos”, Scott Aaronson, científico informático de la Universidad de Texas en Austin y director de Quantum Centro de Información, escribió. “Habiendo dicho eso, esta no es la primera vez que me encuentro con la extraña idea de que la aceleración cuántica exponencial para la factorización de números enteros, que conocemos por el algoritmo de Shor, debería de alguna manera ‘pegarse’ a las heurísticas de optimización cuántica que no incorporan ninguna. de las percepciones reales del algoritmo de Shor, como por arte de magia simpática.