Universidad
Politécnica de Madrid

La física cuántica cuestiona la seguridad informática

Investigadores de la UPM desarrollan un simulador cuántico que analiza el problema de la factorización entera, clave para la seguridad de internet.

28.11.2016

La seguridad de la información que manejamos en nuestros teléfonos, correos electrónicos, gestiones online e internet es fundamental en nuestra sociedad de la información, los recientes ciberataques sufridos, por ejemplo, en las cuentas de correo de Yahoo o la debilidad de la seguridad mostrada por las nuevas generaciones de dispositivos interconectados en la Internet de las cosas, son buenas muestras de esto. Pese a que los usuarios tratemos utilizar contraseñas cada vez más robustas, de poco sirve si los servidores que alojan la información o los mismos dispositivos son vulnerables ante los ataques. Un equipo de investigadores de la Universidad Politécnica de Madrid ha desarrollado un método que, aplicando las leyes cuánticas, muestra una nueva manera de romper los algoritmos en los que se basa la gran mayoría de algoritmos de cifrado usados en la actualidad.

Una de las claves de los procesos de cifrado de las comunicaciones es la factorización. Cuando una persona envía información cifrada a través de internet el proceso que se sigue es complejo. “En primer lugar, los datos son cifrados para enviarlos al lugar de destino y para ello se utilizan pares de claves cuya seguridad descansa finalmente en la dificultad de descomponer un números grande en sus factores primos. Dados dos números primos, es muy fácil calcular su producto, pero dado un número grande, es muy difícil calcular sus factores primos. Es la supuesta complejidad computacional de este problema, aparentemente sencillo pero que ha resistido siglos de investigación en matemáticas, lo que confiere seguridad a la mayoría de algoritmos de cifrado usados en la actualidad" explica Vicente Martín, uno de los autores del estudio y director del Centro de Simulación Computacional de la UPM en la ETS de Ingenieros Informáticos.

Aunque el problema de factorización haya resistido hasta ahora todos los esfuerzos de los criptoanalistas, lo cierto es que su complejidad computacional real es todavía desconocida. Lo que sí se sabe es que, si pudiésemos usar un ordenador cuántico en lugar de uno clásico, el problema sería fácil de resolver.

En 1995 Peter Shor, entonces en el instituto de tecnología de Xerox, desarrolló un algoritmo que resolvía el problema recurriendo a un ordenador capaz de manipular qubits, el análogo cuántico de los bits. El enorme potencial de ruptura de este algoritmo ha sido uno de los principales impulsores del desarrollo de los ordenadores cuánticos, una tecnología compleja que se cree que tardará todavía décadas en realizarse.

Salvando la necesidad del ordenador cuántico

Salvar la necesidad de un ordenador cuántico programable completamente funcional para poder ejecutar el algoritmo de Shor ha sido el problema en el que han trabajado los expertos de la UPM.
Para ello han desarrollado una nueva estrategia basada en el diseño de un simulador cuántico: un sistema físico cuya evolución resuelve el problema. Es el equivalente analógico de un ordenador digital, aquellos viejos dispositivos que resolvían ecuaciones midiendo voltajes en lugar de tener memorias, procesadores y usar lenguajes de programación. Este tipo de dispositivos cuánticos son menos versátiles que un ordenador cuántico pero son equivalentes en lo que hacen y también son, en principio, tecnológicamente más accesibles.

“Lo primero que hicimos fue redefinir el problema de modo que ya no tengamos que esperar a tener un ordenador cuántico completamente operativo para poder utilizar con normalidad el algoritmo creado por Shor. Hemos reformulado el problema de la factorización entera de un número grande en otro aritméticamente equivalente que depende de una función de los factores primos. Esa función puede asociarse con la energía de un dispositivo cuántico que puede medirse para obtener los factores”, explica Jose Luis Rosales, investigador de la UPM que ha desarrollado el estudio, recientemente publicado en Physical Review Letters, junto con Vicente Martín. Estudio que ha tenido eco tanto en Physics Buzz como en Phys.org.

El estudio no solo abre una nueva manera de resolver el problema de factorización. Demostrando que hay un dispositivo físico que tiene acceso a los números primos, se puede estudiar la estadística de los mismos y arrojar luz sobre problemas de matemática puras. En particular la distribución de los números primos entre el resto de los números, problema íntimamente relacionada con la hipótesis de Riemann y cuya demostración es uno de los famosos problemas de Hilbert y uno de los problemas abiertos, nominados como uno de los siete problemas del milenio y premiado con un millón de dólares por el Clay Institute. También muestra que existen algoritmos clásicos de factorización fundamentados en principios completamente distintos de las cribas tradicionales, lo que plantea nuevas dudas sobre la solidez de los métodos tradicionales.

"Tal vez sea el momento de plantearse seriamente en incorporar otros protocolos de seguridad, que no estén basados en complejidad computacional, al arsenal de la criptografía. La misma física nos da la criptografía cuántica, basada en principios que nunca podrá romper ningún ordenador, sea cuántico o clásico", comentan los investigadores. Tema en el que son también expertos dentro del grupo de Investigación en Información y Computación Cuántica, donde han llevado ya esta tecnología a las redes de comunicaciones de mano de compañías como Telefónica I+D.

Este trabajo ha sido parcialmente financiado por el proyecto QUITEMAD, un proyecto PRICIT (Plan Regional de Investigacion en Ciencia y Tecnología) financiado por la Comunidad de Madrid.

Punteros relevantes:
* El artículo en el PRL: http://journals.aps.org/prl/abstract/10.1103/PhysRevLett.117.200502
* Artículo de divulgación en Physics Buzz: http://physicsbuzz.physicscentral.com/2016/11/factoring-quantum-mechanics-into.html 
* Artículo de divulgación en American Institute of Physic: http://phys.org/news/2016-11-quantum-physics-factor.html
* Web del Center for Computational Simulation: www.ccs.upm.es
* Grupo de investigación en Información y Computación Cuántica: http://www.gcc.fi.upm.es/