Factorización de RSA con un Optimizador de Quantum Computing (y Classic Computing)

Desde hace años llevamos hablando del riesgo para los algoritmos de cifrado de la aparición de los ordenadores cuánticos. Sabemos que cuando lleguen los ordenadores cuánticos profesionales, la factorización de números enteros que es soporte fundamental de RSA, será trivial. Y esto nos dejará sin uno de los soportes fundamentales de la criptografía moderna, ya que en él se sustenta el cifrado de las comunicaciones modernas.

Pero hace años que se está estudiando e investigando cómo sería posible romper RSA, por supuesto. Es uno de los grandes objetivos de los investigadores en criptografía, y cualquier avance que abra nuevas puertas, nuevos caminos, nuevas formas de atacar la robustez de RSA, son siempre exploradas y analizadas en detalle. Si no estás familiarizado con RSA, te recomiendo que te compres, leas y subrayes este libro.

Figura 2: Libro de Cifrado de las comunicaciones digitales: de la cifra clásica a RSA 2ª Edición de 0xWord

Desde el año 2001 existe el RSA Factoring Challenge, donde se premia a los que consiguen hitos relevantes en su ruptura, pero al mismo tiempo, donde los investigadores buscan dejar su nombre escrito, pues es un reconocimiento mundial. Si vemos la tabla en Wikipedia, podemos ver que el reto comienza en RSA100, que ya fue roto en el año 1991.

Si vamos a la segunda parte de la tabla, ya vemos que el último hito lo tenemos en romper RSA250, conseguido en el año 2020. Algo que, a pesar de ser un avance en la investigación y en la técnica, deja todavía muy lejos a RSA2048 que es el más utilizado hoy en día.

Lo que sí es cierto es que ya se conocen algoritmos para romper RSA cuando existan los equipos cuánticos del tamaño necesario para ejecutarlos, como es el caso del propuesto por Peter Shor, que permite factorizar los números enteros en tiempo asintótico de O((logN)^3) y espacial de O(logN). Este algoritmo no es nuevo y, como explica la Wikipedia, en el año 2001 se puedo aplicar en un ordenador cuántico de 7 Qbits para descomponer 15 en 3 y 5.

Hoy en día, los investigadores están buscando encontrar nuevas formas de atacar el problema de romper RSA desde varios puntos diferentes, que ayuden a reducir la complejidad desde diferentes puntos de vista.  El primero de ellos, intentando encontrar algoritmos que factoricen números enteros grandes de forma más eficiente. Exprimiendo para ello la matemática. Como explican en Segu-Info, en el año 2021, el matemático alemán Claus-Peter Schnorr publicó el artículo académico de «Fast Factoring Integers by SVN Algorithms«, que propone un método más eficiente para intentar que las computadoras clásicas pudieran romper RSA, pero no escala tanto como para ser una amenaza real para RSA2048. 

Por otro lado, es cierto que las Computadoras Cuánticas – no orientadas a este problema, sino generalistas – avanzan cada vez más deprisa y, en cuanto estas lleguen, podrán implementar el algoritmo de citado anteriormente de Peter Shor, lo que obliga a trabajar y pensar en los algoritmos de Post-Quantum Encryption y a tener una estrategia de reemplazo en todos los rincones. Como ya vimos, el gobierno de Estados Unidos ya ha comenzado con su camino en esta dirección, bajo la publicación de la Quantum Computing Cybersecurity Preparedness Act. 

Por supuesto, habrá que ver en lo que están trabajando Google y Microsoft en estas áreas de investigación, donde también tienen puestos muchos recursos en la competición cuántica que estamos viendo desde hace unos años.

A todos estos avances, el pasado 23 de Diciembre de 2022 se presentó un artículo académico en China, titulado «Factoring integers with sublinear resources on a superconducting quantum processor«, donde un equipo de investigación amplio explicaba cómo habían utilizado una aproximación mixta para resolver el problema de escala que tenía el algoritmo de «Fast Factoring Integers by SVN Algorithms«, utilizando para las partes que no escalaban un ordenador cuántico. 

¡Saludos Malignos!