Feeds:
Entradas
Comentarios

Posts Tagged ‘algoritmo de Shor’

Los computadores cuánticos pueden romper la criptografía moderna

Esta atrevida afirmación, que en alguna ocasión he podido leer y escuchar, está basada muy probablemente en la existencia de ciertos algoritmos como el de Shor.

Poniendo ejemplos concretos, y ya que sale de titular el algoritmo de Shor, hay que hablar de RSA. Este criptosistema de clave pública, presentado en 1977, basa su seguridad en el conocido como “problema de factorización de números enteros“; esto es, la dificultad asociada a la descomposición de un número compuesto en divisores no triviales. Así, existen muchos algoritmos de factorización utilizados habitualmente, si bien todos ellos tienen una complejidad exponencial; lo cual implica que un leve aumento en el tamaño del problema conlleva un aumento muy grande en el tiempo necesario para resolverlo.

En resumen, la seguridad de RSA radica en que resulta sencillo generar claves y operar con ellas en la forma que define el algoritmo (operaciones como multiplicaciones, exponenciaciones, congruencia modular, etc.), pero resulta computacionalmente muy complejo intentar obtener el factor privado de la clave a partir del público y de mensajes del criptosistema (operación de factorización). Si se consiguiera un algoritmo de factorización con una complejidad razonable (por ejemplo, polinómica), un ataque a la criptografía RSA sería mucho más simple.

Y aquí entra en juego el algoritmo de Shor, anunciado en 1995 por Peter Shor. Este algoritmo resuelve el problema de factorización con un coste temporal logarítmico O((log N)3), aunque tiene la pequeña pega de necesitar de un computador cuántico para la ejecución de parte del mismo. Aún cuando hoy en día no existen (o al menos, no se conoce su existencia) computadores cuánticos completos y funcionales, esta tecnología avanza constantemente. De hecho, la gente de IBM demostró en 2001 la corrección del algoritmo de Shor.

Vale, sabemos que el algoritmo de Shor permite factorizar en tiempo logarítmico, sabemos que se ha demostrado su funcionamiento, y que los computadores cuánticos terminarán llegando tarde o temprano. ¿Significa esto la ruptura automática de la criptografía de PKI, y más concretamente en este caso de RSA? Pues no. El hecho de que el algoritmo de Shor permita factorizar números de una forma más eficiente significa exactamente eso: lo hará más rápido. Pero no será instantáneo.

Así, y para el caso de RSA (parece que hay algoritmos equivalentes para DH/ElGamal), el algoritmo de Shor reduciría enormemente la complejidad de lanzar un ataque, pero no acabaría con su seguridad de forma inmediata. Además, debemos tener en cuenta, en primer lugar, que necesitamos de computadores cuánticos para llevar a cabo estos ataques; y que la llegada de este tipo de sistemas estará, con toda seguridad, asociada a la creación de nuevos algoritmos cuánticos criptográficos. De hecho, la criptografía cuántica (que no tiene directamente nada que ver con la computación cuántica) lleva con nosotros, nada más y nada menos, que desde 1984.

Hasta aquí este nuevo mito, que como siempre, espero que os haya resultado interesante.

Read Full Post »

A %d blogueros les gusta esto: