Nuevo algoritmo cuántico permite a computadora de 20 millones de qubits descifrar RSA de 2048 bits en 8 horas

Investigadores desarrollan un nuevo algoritmo cuántico que usa menos recursos para realizar cálculos de descifrado.

Una computadora cuántica de 20 millones de qubits ejecutando este algoritmo tardaría solo 8 horas en descifrar cifrado RSA de 2.048 bits.

Las computadoras cuánticas se vuelven más potentes

En 1994, el matemático estadounidense Peter Shor desarrolló un algoritmo cuántico para factorizar números grandes exponencialmente más rápido que los mejores algoritmos existentes en computadoras clásicas. Sugirió que una máquina cuántica lo suficientemente potente podría romper técnicas de cifrado modernas con facilidad.

En la última década, se han hecho muchos avances en computación cuántica. En 2012, científicos lograron usar una computadora cuántica de 4 qubits para factorizar «143». Dos años después, usaron una máquina similar para factorizar «56153».

Considerando la tasa de progreso, las computadoras cuánticas pronto podrán superar a las computadoras actuales. Al menos esto es lo que los científicos esperaban hace unos años.

Resulta que factorizar números grandes en máquinas cuánticas es mucho más difícil de lo previsto. Esto se debe al ruido significativo en computadoras cuánticas grandes. El problema podría abordarse usando códigos de corrección de errores, que a su vez requieren qubits adicionales.

Referencia: arXiv:1905.09749 | MIT Technology Review

Teniendo en cuenta este factor de ruido, una computadora cuántica necesitaría mil millones de qubits para factorizar números de 2048 bits (o descifrar cifrado RSA de 2048 bits). Sin embargo, las computadoras cuánticas universales actuales solo tienen 70 qubits.

Exponentiación modular

El nuevo algoritmo permite a las computadoras cuánticas realizar estos cálculos con solo 20 millones de qubits. De hecho, los investigadores han demostrado que un dispositivo cuántico ejecutando este nuevo algoritmo tardaría solo 8 horas en descifrar cifrado RSA de 2.048 bits.

Su método realiza exponentiación modular —un tipo de exponentiación realizada sobre un módulo— de manera eficiente. Esta operación matemática es computacionalmente costosa en el algoritmo de Shor.

Los investigadores han encontrado diferentes formas de optimizar esta operación, reduciendo drásticamente los recursos necesarios para ejecutar el algoritmo.

Aunque una computadora cuántica de 20 millones de qubits no es factible en el futuro próximo, los expertos en seguridad deben pensar en una nueva forma de cifrado que ni una potente computadora cuántica pueda descifrar.