Cómo una computadora cuántica podría romper el cifrado RSA de 2048 bits en 8 horas

Un primer plano del chip D-Wave Vesuvius Steve Jurvetson | Flickr

A muchas personas les preocupa que las computadoras cuánticas puedan descifrar ciertos códigos utilizados para enviar mensajes seguros. Los códigos en cuestión cifran los datos mediante funciones matemáticas trampilla que funcionan fácilmente en una dirección pero no en la otra. Eso hace que cifrar datos sea fácil, pero decodificarlos es enormemente difícil sin la ayuda de una clave especial.

Estos sistemas de encriptación nunca han sido irrompibles. En cambio, su seguridad se basa en la gran cantidad de tiempo que le tomaría a una computadora clásica hacer el trabajo. Los métodos de encriptación modernos están diseñados específicamente para que su decodificación lleve tanto tiempo que sean prácticamente irrompibles.

Pero las computadoras cuánticas cambian este pensamiento. Estas máquinas son mucho más poderosas que las computadoras clásicas y deberían poder descifrar estos códigos con facilidad.

Eso plantea una pregunta importante: ¿cuándo serán las computadoras cuánticas lo suficientemente poderosas para hacer esto? Después de esa fecha, cualquier información protegida por esta forma de encriptación se vuelve insegura.

Por lo tanto, los científicos informáticos han intentado calcular los recursos que podría necesitar una computadora cuántica de este tipo y luego determinar cuánto tiempo pasará hasta que se pueda construir una máquina de este tipo. Y la respuesta siempre ha sido décadas.

Hoy, ese pensamiento debe revisarse gracias al trabajo de Craig Gidney en Google en Santa Bárbara y Martin Ekerå en el KTH Royal Institute of Technology en Estocolmo, Suecia. Estos muchachos han encontrado una forma más eficiente para que las computadoras cuánticas realicen los cálculos de descifrado de códigos, reduciendo los recursos que requieren en órdenes de magnitud.

En consecuencia, estas máquinas están significativamente más cerca de la realidad de lo que nadie sospechaba. El resultado será una lectura incómoda para los gobiernos, las organizaciones militares y de seguridad, los bancos y cualquier otra persona que necesite proteger los datos durante 25 años o más.

Primero algunos antecedentes. En 1994, el matemático estadounidense Peter Shor descubrió un algoritmo cuántico que superó a su equivalente clásico. El algoritmo de Shor factoriza grandes números y es el elemento crucial en el proceso para descifrar códigos basados ​​en trampillas.

Las funciones de trampilla se basan en el proceso de multiplicación, que es fácil de realizar en una dirección pero mucho más difícil de realizar en sentido inverso. Por ejemplo, es trivial multiplicar dos números: 593 por 829 es 491,597. Pero es difícil comenzar con el número 491,597 y determinar qué dos números primos se deben multiplicar para producirlo.

Y se vuelve cada vez más difícil a medida que los números aumentan. De hecho, los científicos informáticos consideran que es prácticamente imposible que una computadora clásica factorice números que superen los 2048 bits, que es la base de la forma de cifrado RSA más utilizada.

Shor demostró que una computadora cuántica lo suficientemente poderosa podría hacer esto con facilidad, un resultado que conmocionó a la industria de la seguridad.

Y desde entonces, las computadoras cuánticas han ido aumentando su poder. En 2012, los físicos usaron una computadora cuántica de cuatro qubits para factorizar 143. Luego, en 2014, usaron un dispositivo similar para factorizar 56 153.

Es fácil imaginar que a este ritmo de progreso, las computadoras cuánticas pronto deberían poder superar a las mejores clásicas.

No tan. Resulta que la factorización cuántica es mucho más difícil en la práctica de lo que cabría esperar. La razón es que el ruido se convierte en un problema importante para las grandes computadoras cuánticas. Y, actualmente, la mejor manera de abordar el ruido es usar códigos de corrección de errores que requieren una cantidad considerable de qubits adicionales.

Tener esto en cuenta aumenta drásticamente los recursos necesarios para factorizar números de 2048 bits. En 2015, los investigadores estimaron que una computadora cuántica necesitaría mil millones de qubits para hacer el trabajo de manera confiable. Eso es significativamente más que los 70 qubits en las computadoras cuánticas de última generación de hoy.

Sobre esa base, los expertos en seguridad bien podrían haber justificado la idea de que pasarían décadas antes de que una computadora cuántica pudiera descifrar los mensajes con encriptación RSA de 2048 bits.

Ahora, Gidney y Ekerå han demostrado cómo una computadora cuántica podría hacer el cálculo con solo 20 millones de qubits. De hecho, muestran que un dispositivo de este tipo tardaría solo ocho horas en completar el cálculo. [Como resultado], la estimación del peor de los casos de cuántos qubits se necesitarán para factorizar enteros RSA de 2048 bits ha caído casi dos órdenes de magnitud, dicen.

Su método se enfoca en una forma más eficiente de realizar un proceso matemático llamado exponenciación modular. Este es el proceso de encontrar el resto cuando un número se eleva a cierta potencia y luego se divide por otro número.

Este proceso es la operación más costosa computacionalmente en el algoritmo de Shor. Pero Gidney y Ekerå han encontrado varias formas de optimizarlo, reduciendo significativamente los recursos necesarios para ejecutar el algoritmo.

Es un trabajo interesante que debería tener implicaciones importantes para cualquiera que almacene información para el futuro. Una computadora cuántica de 20 millones de qubits ciertamente parece un sueño lejano hoy. Pero la pregunta que estos expertos deberían hacerse es si tal dispositivo podría ser posible dentro de los 25 años que quieren asegurar la información. Si creen que lo es, entonces necesitan una nueva forma de encriptación.

De hecho, los expertos en seguridad han desarrollado códigos poscuánticos que ni siquiera una computadora cuántica podrá descifrar. Por lo tanto, ya es posible salvaguardar los datos hoy contra futuros ataques de computadoras cuánticas. Pero estos códigos aún no se utilizan como estándar.

Para la gente común, hay poco riesgo. La mayoría de la gente usa el cifrado de 2048 bits, o algo similar, para tareas como enviar datos de tarjetas de crédito por Internet. Si estas transacciones se registran hoy y se rompen en 25 años, se perderá poco.

Pero para los gobiernos, hay más en juego. Los mensajes que envían hoy, entre embajadas o el ejército, por ejemplo, pueden ser significativos dentro de 20 años y, por lo tanto, vale la pena mantenerlos en secreto. Si dichos mensajes aún se envían a través del cifrado RSA de 2048 bits, o algo similar, entonces estas organizaciones deberían comenzar a preocuparse, rápidamente.

Ref: arxiv.org/abs/1905.09749 : Cómo factorizar enteros RSA de 2048 bits en 8 horas usando 20 millones de Qubits ruidosos

esconder