Continúan los intentos de romper el algoritmo RSA utilizando ordenadores cuánticos. Un grupo chino afirma estar en condiciones de romper el algoritmo RSA-2048.

Los algoritmos criptográficos de clave pública, también conocidos como criptografía asimétrica, se basan en algoritmos matemáticos que actualmente no son fáciles de calcular. En otras palabras, el algoritmo es fácil de manejar en una dirección mientras que es casi imposible en la otra dirección.

El algoritmo RSA se creó en 1977 a partir del trabajo de los inventores Ronald Rivest, Adi Shamir y Leonard Adleman (las iniciales de los apellidos corresponden a la abreviatura RSA).

RSA se usa hoy en día en todos los niveles, y siempre que la clave sea lo suficientemente larga y se genere correctamente, la información protegida por RSA está segura.

Algunos algoritmos de clave pública utilizan la factorización de un número entero, un proceso a que a nivel de cálculo es fácil de hacer pero muy difícil de realizar la operación inversa. El calculo inverso es muy costoso a nivel de computación, es decir, un ordenador normal podría tardar miles de años en realizar el cálculo.

En concreto, RSA basa su funcionamiento precisamente en la factorización: dado un número natural N muy grande, no existe un método rápido para volver a los dos números primos P y Q que, al multiplicarlos, dan como resultado N. Por tanto, si la multiplicación de dos números es una operación muy sencilla de realizar, la factorización no lo es en absoluto e históricamente se ha mantenido como uno de los problemas más complejos de calcular.

Puedes utilizar los métodos de Euler, Fermat, Dixon y Shor o "fuerza bruta" para intentar factorizar un número. Como hemos visto, en el caso de RSA, si se han utilizado claves muy débiles, es posible descifrar un mensaje cifrado: recientemente un grupo de investigadores consiguió incluso utilizar el antiguo algoritmo de Pierre de Fermat para descifrar información protegida con RSA.

Los ordenadores cuánticos están cambiando las reglas en el campo de la supercomputación. Los problemas que se pueden resolver con un ordenador cuántico son, de hecho, gran parte de los que no se pueden gestionar con las tecnologías de la información tradicionales, precisamente por el mencionado coste computacional.

Por lo tanto, factorizar una clave criptográfica se vuelve más que factible con la computación cuántica.

El NIST (Instituto Nacional de Estándares y Tecnología) nos ha recordado repetidamente que es recomendable actuar a tiempo para no encontrarnos en una situación de emergencia con algoritmos criptográficos considerados seguros que de repente se vuelven poco confiables.

Un estudio realizado por Craig Gidney y Martin Ekerå demostró que serían necesarios 20 millones de qubits para factorizar con éxito una clave RSA-2048 en solo 8 horas.

Sobre el papel, se trata de un gran esfuerzo si se tiene en cuenta que el ordenador cuántico IBM Osprey tiene 433 qubits y que la empresa espera alcanzar los 4.000 qubits en 2025.

Aunque la intención de IBM es desarrollar ordenadores cuánticos con más qubits, la meta de 20 millones de qubits parece muy lejana.

El conocido criptógrafo estadounidense Bruce Schneier llama la atención sobre una investigación recientemente publicada por un grupo de investigadores chinos.

Los investigadores chinos afirman poder romper RSA-2048 incluso si en la práctica esto aún no se ha hecho. Según las conclusiones de la investigación, solo un ordenador cuántico de 372 qubits sería suficiente para descifrar los mensajes protegidos con el algoritmo RSA-2048, pero el grupo chino afirma que no tiene un computador cuántico tan poderoso.

Los autores de la investigación han demostrado que pueden factorizar números de 48 bits utilizando un ordenador cuántico de 10 qbit. Disponer de un ordenador cuántico de 372 qubits no es imposible ya que ordenador cuántico de IBM más potente tiene 433 qubits.

Lo que han hecho los investigadores es combinar las técnicas clásicas de factorización destinadas a reducir la red con un algoritmo de optimización de tipo cuántico aproximado: de esta forma se han podido reducir esos 20 millones de qubits a tan solo 372.

Según Schneier, el trabajo del equipo chino se basa en el enfoque del problema de factorización de Peter Schnorr: es un documento controvertido porque describe un algoritmo que funciona bien con módulos más pequeños, aproximadamente del mismo orden que los probados por el grupo chino, pero falla a medida que aumenta el tamaño de la clave. El documento chino afirma que las técnicas cuánticas adoptadas permiten eludir las limitaciones del algoritmo de Schnorr, pero faltan varios elementos por resolver del rompecabezas.

Schneier, escribe que después de un análisis más profundo del trabajo realizado por el equipo chino, no hay motivos para la preocupación.