.

Steve Jurvetson | Flickr

Computación

Un ordenador cuántico romperá el cifrado RSA de 2048 bits en ocho horas

1

Un nuevo enfoque matemático revela que una máquina cuántica de 20 millones de cúbits podría hacerlo en un tiempo récord. Aunque este tipo de computadoras aún no existen, puede que estén disponibles en 25 años, lo que debería preocupar a gobiernos y agencias de ciberseguridad

  • por Emerging Technology From The Arxiv | traducido por Ana Milutinovic
  • 10 Junio, 2019

A muchas personas les preocupa que los ordenadores cuánticos logren descifrar ciertos tipos de encriptación que actualmente se usan para enviar mensajes de forma segura. Dichos códigos cifran los datos mediante funciones matemáticas de "trampilla" que funcionan fácilmente en una dirección pero no en la otra. Eso hace que la encriptación de datos resulte fácil mientras que su descodificación es casi sin una clave especial.

Pero estos sistemas de encriptación nunca han sido infalibles. En realidad, su seguridad se basa en la enorme cantidad de tiempo que necesitaría un ordenador convencional para hacerlo. Los métodos modernos de encriptación están diseñados específicamente para que el proceso de decodificación sea tan lento que parezcan prácticamente irrompibles.

Pero los ordenadores cuánticos no se adaptan a este enfoque. Estas máquinas son mucho más potentes que los ordenadores convencionales y podrían romper estos códigos con mucha facilidad. Esto plantea una pregunta importante: ¿cuándo serán los ordenadores cuánticos lo suficientemente poderosos para lograrlo? Cuando llegue ese momento, cualquier información protegida mediante las técnicas actuales de encriptación se volverá insegura.

Así que varios informáticos han intentado calcular los recursos que un ordenador cuántico podría necesitar para descubrir cuánto tiempo pasaría hasta que se pueda construir una máquina de este tipo. Y, hasta ahora, la respuesta siempre se había medido en décadas.

Pero ese cálculo se debe revisar debido al trabajo del investigador de Google en Santa Barbara (EE. UU.) Craig Gidney y del investigador del Real Instituto de Tecnología KTH en Estocolmo (Suecia) Martin Ekerå. Ambos han encontrado una manera más eficiente para que los ordenadores cuánticos realicen los cálculos de descifrado de códigos, lo que reduce los recursos que necesitan por varias órdenes de magnitud.

Su hallazgo implica que estas máquinas están mucho más cerca de hacerse realidad de lo que se sospechaba. El resultado resultará incómodo para gobiernos, organizaciones militares y de seguridad, bancos y cualquier otra persona que necesite almacenar sus datos por periodos superiores a 25 años a partir de ahora.

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

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 en sentido inverso. Por ejemplo, multiplicar dos números resulta muy sencillo: 593 x 829 = 491.597. Lo difícil es comenzar con el número 491.597 y calcular cuáles son los dos números que se han multiplicado para producirlo

A medida que los números aumentan, la cosa se complica aún más. De hecho, los informáticos consideran prácticamente imposible que un ordenador convencional calcule los números que tienen más de 2048 bits, que es la base de la forma más utilizada del cifrado RSA, un sistema criptográfico de clave pública desarrollado en 1979.

Shor demostró que un ordenador cuántico suficientemente potente podría hacerlo con facilidad, algo que sorprendió y mucho a la industria de la ciberseguridad. Y desde entonces, la potencia de las máquinas cuánticas no ha hecho más que aumentar. En 2012, unos físicos utilizaron un ordenador cuántico de cuatro cúbits para calcular el factor 143. En 2014, utilizaron un dispositivo similar para calcular el factor 56.153.

Así que cualquiera podría pensar que, a este ritmo, los ordenadores cuánticos están a punto de superar a los mejores ordenadores convencionales. Pero esto no es así. Resulta que la factorización cuántica es mucho más difícil en la práctica de lo que se creía. La razón es el ruido, que se convierte en un problema importante para los grandes ordenadores cuánticos. Actualmente, la mejor manera de abordar el ruido se basa en códigos de corrección de errores que requieren importantes cantidades de cúbits adicionales.

Debido a esto, los recursos requeridos para la factorización numérica de 2048 bits aumentan drásticamente. En 2015, un equipo de investigación estimó que un ordenador cuántico necesitaría mil millones de cúbits para realizar esta tarea de manera confiable. Esa cifra es muchísimo más  altaque los 70 cúbits que tienen los ordenadores cuánticos actuales más potentes. Así que, los expertos en ciberseguridad podrían justificar la idea de que pasarán décadas antes de que los mensajes cifrados con RSA de 2048 bits pudieran ser descifrados por un ordenador cuántico.

Pero Gidney y Ekerå acaban de demostrar que un ordenador cuántico podría hacer el cálculo con solo 20 millones de cúbits. De hecho, afirman que tardaría solo ocho horas en completar el cálculo. "[Como resultado], la estimación del peor caso de cuántos cúbits se necesitarán para factorizar los RSA de 2048 bits se ha reducido en casi dos órdenes de magnitud", detallan en su artículo.

Su método se centra en una forma más eficiente de realizar un proceso matemático llamado exponenciación modular. Consiste en encontrar el recordatorio cuando un número se eleva a un cierto nivel y luego se divide por otro número. Este proceso es la operación más costosa a nivel computacional del algoritmo de Shor. Pero Gidney y Ekerå han encontrado varias formas de optimizarlo, lo que reduce significativamente los recursos necesarios para ejecutar el algoritmo.

Se trata de un trabajo interesante que debería tener implicaciones importantes para cualquiera que almacene información para el futuro. Ahora mismo, un ordenador cuántico de 20 millones de cúbits parece un sueño muy lejano. Pero la pregunta que estos expertos deberían hacerse es si tal dispositivo podría existir dentro de los próximos 25 años de almacenamiento de datos. Si la respuesta es afirmativa, entonces necesitan una nueva forma de cifrado.

De hecho, los expertos en ciberseguridad han desarrollado códigos postcuánticos que ni siquiera un ordenador cuántico podrá descifrar. Por lo tanto, ya es posible salvaguardar los datos contra los futuros ataques de los ordenadores cuánticos. Pero estos códigos aún no se utilizan como estándar.

Para cualquier ciudadano de a pie, este hallazgo no supone muchos riesgos. La mayoría de la gente utiliza la encriptación de 2048 bits, o similares, para tareas como envíos de detalles de tarjetas de crédito a través de internet. Si estas transacciones se registran hoy y se descifran en 25 años, el daño será mínimo.

Pero para los gobiernos, la situación resulta más preocupante. Los mensajes que se envían hoy entre embajadas o el ejército podrían ser de gran importancia dentro de 20 años y sería mejor mantenerlos en secreto. Si estos mensajes todavía se envían a través de un cifrado RSA de 2048 bits, o algún similar, estas organizaciones deberían empezar a preocuparse y mucho.

Ref: arxiv.org/abs/1905.09749 : How To Factor 2048 Bit RSA Integers In 8 Hours Using 20 Million Noisy Qubits

Computación

Las máquinas cada vez más potentes están acelerando los avances científicos, los negocios y la vida.

  1. El nuevo chip de Google protege las partes más vulnerables de nube

    OpenTitan es un microprocesador de código abierto que puede ser comprobado en cualquier momento y que incluye un sistema de autodiagnóstico cada vez se que arranca el sistema. Aunque no es perfecto, podría reducir la persistencia de los hackers que ya han logrado acceder a una máquina

  2. El misterio de los barcos que sufren suplantaciones de GPS en China

    Varias embarcaciones en Shanghái han sido víctimas de una novedosa arma que engaña a los sistemas de GPS: falsifica la ubicación de las naves para que parezcan estar en un lugar diferente. Los expertos están asombrados por la complejidad de los ataques y aún no se sabe quién está detrás de ellos

  3. Software espía, la polémica estrella de la gran feria de la vigilancia

    Ejércitos, cuerpos policiales y agencias de vigilancia se han reunido en la feria de seguridad nacional Milipol celebrada en Francia. Aunque la exposición ha acogido armas, granadas o vehículos blindados, las controvertidas herramientas de cibervigilancia ocupan un lugar cada vez más destacado