RSA se mantiene intacto frente al algoritmo de Shor y otros ataques cuánticos

Durante la Conferencia Enigma 2023 celebrada en Santa Clara (California) el pasado 24 de enero, el científico informático y experto en seguridad y privacidad, Simson Garfinkel, aseguró públicamente que la computación cuántica tenía pocas aplicaciones y recursos para acabar con el cifrado RSA. Además, añadía que si nos centramos en este asunto dejaremos la puerta abierta a otras amenazas inminentes.

Las computadoras cuánticas, en palabras de Garfinkel, pueden valerse de aplicaciones para realizar operaciones de física y química y optimizaciones informáticas, pero no es compatible con la computación clásica. A pesar de su éxito para publicar artículos o para obtener financiación, aún les queda mucho camino por recorrer en este sentido.

El origen del problema

El tema fue abordado en esta convención como consecuencia de que hace tres semanas se descubriese un avance que alteró el descifrado del esquema RSA a partir de la computación cuántica. Todo ello es debido al conocido como algoritmo de Shor, que es capaz de calcular los números primos secretos que componen una clave RSA.

No obstante, para que Shor pueda ejercer dicho descifrado precisaría de infinidad de recursos informáticos. Sin ir más lejos, para acabar con una clave RSA de 1024 bits o 2048 bits es necesaria una computadora cuántica equipada con 20 millones de qubits y ocho horas de funcionamiento en superposición.

Quien introdujo el poder de Shor frente al cifrado RSA de 2048 bits fue un  equipo de investigadores de China, los cuales aseguraban que utilizando un sistema cuántico dotado de 372 qubits. Pero para que esta estrategia funcionase se precisaría a su vez del algoritmo de Schnorr, que es otro diferente y desarrollado en 1994. Se trata de estructuras matemáticas que tienen muchas aplicaciones en criptografía constructiva y criptoanálisis, pero que podría mejorar el uso del método inventado de optimización cuántica QAOA. Su gran problema era que trabajaba en un tiempo polinomial, y no exponencial como los algoritmos clásicos.

El científico informático de la Universidad de Texas, Scott Aaronson, asegura que es imposible que Shor, sin la ayuda de los nuevos sistemas de optimización cuántica pudiese trabajar en el descifrado de RSA sin tardar miles de millones de años.

El estudio de Fujitsu

La tecnológica japonesa se sumó a la opinión de los investigadores y aseguró públicamente que para descifrar una clave RSA se precisaba de una computadora cuántica tolerante a una escala de 10.000 qubits y 2,23 billones de puertas cuánticas, y aún así el cálculo podría tardar unos 104 días.

A raíz de estas afirmaciones, el estudiante de doctorado en la Universidad de Cambridge, Samuel Jaques, no tardó en escribir un correo electrónico a la compañía tecnológica asegurando que la mejor estimación para la factorización cuántica sigue siendo que para RSA-2048 se precisan 20 millones de qubits físicos y 8 horas, apoyándose en un estudio científico de Gidney y Ekera. Esto se contradice con los datos de Fujitsu, que baja de 20 millones a 10.000.

Y es que un sistema cuántico de 20 millones de qubits tardaría ocho horas en superposición constante para descifrar una única clave de cifrado, algo inútil debido a que cualquier persona podría emplear la capacidad de firma criptográfica de actualizaciones maliciosas con una clave de Microsoft o Apple y distribuirlas a millones de usuarios.

A lo largo de los últimos cinco años, el Instituto Nacional de Estándares y Tecnología ha buscado nuevos algoritmos criptográficos que no sean vulnerables a Shor, aunque ninguno ha alcanzado el éxito. Todo ello hace indicar que, según afirma Garfinkel, una vez que se nombre un reemplazo poscuántico habrá una carrera sin precedentes por vender nuevos productos a los gobiernos para que se adapten a la lucha contra los innovadores algoritmos.

Para Garfinkel se debería destinar el mismo tiempo en analizar el peligro que supone el algoritmo de Shor en estudiar la posibilidad de que RSA pueda caer ante otro ataque de computadora clásica. Además, concluyó afirmando: “Tal vez deberíamos usar algoritmos poscuánticos y RSA en paralelo porque podría haber un problema con los algoritmos poscuánticos”.