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.

Figura 1: Factorización de RSA con un Optimizador

de Quantum Computing (y Classic Computing)

Imagen: Dall-e 2 (happy hacker in futurist art style)

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.

Figura 3: RSA Factoring Challenge (RSA100 a RSA220)

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.

Figura 4: RSA Factoring Challenge RSA2048

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.

Figura 5: Algoritmo de Shor en Wikipedia en Español

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. 

Figura 6: Artículo de Fast Factoring Integers by SVN Algorithms

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. 

Figura 7: Quantum Computing Cybersecurity Preparedness Act

Y es que, cada día vemos equipos cuánticos de más potencia y calidad. A finales del año 2022, la empresa IBM anunció que su ordenador cuántico OSPrey de 433 Qbits, pero sobre todo que planea tener en el año 2025 a Kookaburra, con un objetivo de más de 4158 Qbits, lo que cambiará, seguro, las reglas del juego con los algoritmos que se van a poder ejecutar.

Figura 8: IBM lanza OSPrey con 433 Qbits y planea tener

Kookaburra con más de 4158 Qbits en 2025

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.

Factorización de RSA con Quantum Computing y Classic Computing

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. 

Figura 9: Optimizaciones de Shor basadas en optimizador cuántico

Para su prueba de concepto, utilizaron la factorización de enteros en RSA48 utilizando un ordenador de 10 Qbits. En este caso utilizan, computación clásica para la mayor parte del algoritmo, pero añade un optimizador cuántico "QAOA" que sirve para resolver las partes no escalables del algoritmo de Schnorr  para optimizar el algoritmo de Shor, que no garantizaban un rendimiento asintótico sublinear, y elevaba la complejidad al tiempo que reducía la potencia de la solución.

Figura 10: Se utiliza computación clásica para implementar Shor y se optimiza con un optimizador cuántico. Esta aproximación aumenta la eficacia de Shor con los equipos cuánticos actuales reduciendo el número de Qbits necesarios.

Con esta aproximación, el equipo de investigación ha hecho también un estudio de cuál sería el tamaño del equipo cuántico que se necesitaría para llegar a romper RSA2048 con esta aproximación mixta, lo que ha generado mucha controversia en la comunidad investigadora, a la par que mucho miedo geopolítico entre los encargados de los sistemas de cifrado de las grandes empresas y estados.

Figura 11: IBM ya podría romper RSA-2048 con su OSPrey

Claro, si sumas las últimas noticias, pues parece que IBM ya podría romper RSA-2048 con su equipo OSPrey, y parece que los equipos de más de 372 Qbits, están más cerca de lo que parece. Pero aún hay que ver cómo evoluciona esto. Lo cierto es que, viendo la velocidad a la que van las noticias, hay que ir pensando en poner estrategias de Post-Quantum Encryption en los estados y gobiernos cuanto antes, porque puede ser que no en mucho tiempo, esto ya sea posible de una manera más o menos común.

¡Saludos Malignos!

Autor: Chema Alonso (Contactar con Chema Alonso)