Proponen método para descifrar claves RSA-2048

Un grupo de investigadores de varios centros científicos y universidades chinos propusieron una nueva forma de optimizar el proceso de factorización de parámetros clave RSA en computadoras cuánticas.

Según los investigadores, el método que desarrollaron permite utilizar una computadora cuántica con 372 qubits para descifrar las claves RSA-2048. En comparación, IBM Osprey, el procesador cuántico más potente construido actualmente, contiene 433 qubits y para 2026 IBM planea construir un sistema Kookaburra con 4000 qubits.

Cabe mencionar que el método todavía es solo teórico, no se ha probado en la práctica y genera escepticismo entre algunos criptógrafos.

El cifrado RSA se basa en la operación de exponenciación módulo un gran número. La clave pública contiene el módulo y el grado. El módulo se forma en base a dos números primos aleatorios que solo conoce el propietario de la clave privada. Los ordenadores cuánticos permiten resolver eficazmente el problema de descomponer un número en factores primos, que pueden utilizarse para sintetizar una clave privada a partir de una pública.

Hasta ahora se creía que, dado el desarrollo actual de las computadoras cuánticas, las claves RSA con un tamaño de 2048 bits no podrán ser crackeadas por mucho tiempo, ya que al utilizar el clásico algoritmo de Shor, una computadora cuántica con millones de qubits, requiere mucho tiempo para factorizar una clave RSA de 2048 bits.

El método propuesto por investigadores chinos arroja dudas sobre esta suposición y, si se confirma, permite descifrar claves RSA-2048 no en sistemas de un futuro lejano, sino en computadoras cuánticas ya existentes.

El método se basa en el algoritmo de factorización rápida de Schnorr propuesto en 2021, que permite lograr una reducción drástica del número de operaciones al seleccionar en ordenadores convencionales. Sin embargo, en la práctica, el algoritmo resultó ser de poca utilidad para descifrar claves reales, ya que solo funcionó para claves RSA con valores de módulo pequeños (un número entero que debe descomponerse en números primos). El algoritmo resultó inadecuado para la factorización de números grandes. Investigadores chinos afirman que con la ayuda de métodos cuánticos pudieron eludir la limitación del algoritmo de Schnorr.

El escepticismo de algunos criptógrafos se debe al hecho de que el artículo de los investigadores chinos demuestra la aplicación de su método solo con números pequeños, aproximadamente el mismo orden para el que funciona el algoritmo de Schnorr. A pesar de las afirmaciones de que se ha superado el límite de tamaño, aún no se han proporcionado pruebas ni detalles. En la práctica, se muestra que el método factoriza números enteros de 48 bits usando una computadora cuántica de 10 qubits.

El algoritmo de Shor ha desafiado seriamente la seguridad de la información basada en criptosistemas de clave pública. Sin embargo, para romper el esquema RSA-2048 ampliamente utilizado, se necesitan millones de qubits físicos, lo cual va mucho más allá de las capacidades técnicas actuales. Aquí, reportamos un algoritmo cuántico universal para números enteros factorización combinando la reducción de red clásica con un algoritmo de optimización cuántica aproximada (QAOA).

El número de qubits necesarios es O(logN/loglogN), que es sublineal en la longitud de bits del entero N, lo que lo convierte en el algoritmo de factorización que ahorra más qubits hasta la fecha. Demostramos el algoritmo experimentalmente al factorizar números enteros de hasta 48 bits con 10 qubits superconductores, el más grande entero factorizado en un dispositivo cuántico. Estimamos que un circuito cuántico con 372 qubits físicos y se necesita una profundidad de miles para desafiar a RSA-2048 usando nuestro algoritmo. Nuestro estudio muestra una gran promete acelerar la aplicación de las ruidosas computadoras cuánticas actuales y allana el camino para factorizar enteros grandes de significado criptográfico realista.

Se menciona que la suposición de que 372 qubits físicos serán suficientes para factorizar una clave RSA-2048 es teórica, por lo que es muy probable que el método cuántico basado en el algoritmo de Schnorr tenga los mismos problemas de escala y no funcione al factorizar números grandes.

Si el problema con el escalamiento se resuelve realmente, entonces la seguridad de los criptoalgoritmos basados ​​en la complejidad de factorizar números primos grandes se verá socavada no a largo plazo, como se esperaba, sino ya en la actualidad.

Finalmente si estás interesado en poder conocer más al respecto, puedes consultar los detalles en el siguiente enlace.