¿Cuántas computadoras el fin de la criptografía?

La computación cuántica es una de esas tecnologías tan extravagantes que los nombres de los personajes de TV lo dejan cuando quieren sonar inteligentes.

La computación cuántica como idea ha existido por un tiempo, la posibilidad teórica fue presentada originalmente por Yuri Manin y Richard Feynman en 1982. Sin embargo, en los últimos años, el campo se ha acercado de manera preocupante a la práctica..

Compañías como Google y Microsoft, así como agencias gubernamentales como la NSA, han estado buscando febrilmente computadoras cuánticas desde hace años. Una compañía llamada D-Wave ha producido y está vendiendo dispositivos que (aunque no son computadoras adecuadas y solo pueden realizar unos pocos algoritmos) explotan propiedades cuánticas, y son otro paso incremental en el camino hacia un Turing completo. ¿La prueba de Turing y será vencida alguna vez? ¿Qué es la prueba de Turing y será vencida alguna vez? La prueba de Turing está destinada a determinar si las máquinas piensan. ¿El programa de Eugene Goostman realmente pasó la prueba de Turing, o los creadores simplemente hicieron trampa? Leer más máquina cuántica.

No parece irrazonable decir que pueden ocurrir avances que permitirán que la primera computadora cuántica a gran escala se construya en una década.

Entonces, ¿por qué todo el interés? ¿Por qué debería importarte? Las computadoras se vuelven más rápidas todo el tiempo ¿Qué es la ley de Moore y qué tiene que ver con usted? [MakeUseOf Explica] ¿Qué es la ley de Moore y qué tiene que ver con usted? [MakeUseOf Explica] La mala suerte no tiene nada que ver con la Ley de Moore. Si esa es la asociación que tenías, la estás confundiendo con la Ley de Murphy. Sin embargo, no estaba muy lejos porque la Ley de Moore y la Ley de Murphy ... Leer más: ¿qué tiene de especial la computadora cuántica??

Para explicar por qué estas máquinas son tan importantes, tendremos que dar un paso atrás y explorar exactamente qué son las computadoras cuánticas y por qué funcionan. Para empezar, hablemos de un concepto llamado “complejidad del tiempo de ejecución.”

¿Qué es la complejidad del tiempo de ejecución??

Una de las grandes sorpresas en los primeros días de la informática fue el descubrimiento de que, si tiene una computadora que resuelve un problema de cierto tamaño en un período de tiempo determinado, duplicar la velocidad de la computadora no necesariamente le permite abordar los problemas. el doble de grande.

Algunos algoritmos aumentan en el tiempo de ejecución total muy, muy rápidamente a medida que aumenta el tamaño del problema; algunos algoritmos pueden completarse rápidamente con 100 puntos de datos, pero completar el algoritmo con 1000 puntos de datos requeriría una computadora del tamaño de la Tierra en funcionamiento mil millones de años La complejidad del tiempo de ejecución es una formalización de esta idea: analiza la curva de la rapidez con la que crece la complejidad de un problema y utiliza la forma de esa curva para clasificar el algoritmo.

En general, estas clases de dificultad se expresan como funciones. Se dice que un algoritmo que se hace proporcionalmente más difícil cuando el conjunto de datos en el que trabaja se incrementa (como una simple función de conteo) es una función con una complejidad de tiempo de ejecución de “norte” (como en, toma norte unidades de tiempo para procesar norte puntos de datos).

Alternativamente, podría llamarse “lineal”, Porque cuando lo graficas, obtienes una línea recta. Otras funciones pueden ser n ^ 2 o 2 ^ n o norte! (n factorial). Estos son polinomiales y exponenciales. En los dos últimos casos, los exponenciales crecen tan rápidamente que en casi todos los casos no pueden resolverse para nada excepto ejemplos muy triviales..

Complejidad en tiempo de ejecución y criptografía

Si escuchas esto por primera vez y suena sin sentido y arcano, vamos a tratar de fundamentar esta discusión. La complejidad del tiempo de ejecución es crítica para la criptografía, que se basa en hacer que el descifrado sea mucho más fácil para las personas que conocen una clave secreta que para las que no. En un esquema criptográfico ideal, el descifrado debe ser lineal si tiene la clave, y 2 ^ k (donde k es el número de bits en la clave) si no lo hace.

En otras palabras, el mejor algoritmo para descifrar el mensaje sin la clave debería ser simplemente adivinar posibles claves, lo cual es intratable para claves de solo unos pocos cientos de bits de longitud..

Para la criptografía de clave simétrica (en la que las dos partes tienen la oportunidad de intercambiar un secreto de forma segura antes de iniciar la comunicación) esto es bastante fácil. Para la criptografía asimétrica, es más difícil.

La criptografía asimétrica, en la que las claves de cifrado y descifrado son diferentes y no se pueden calcular fácilmente unas de otras, es una estructura matemática mucho más difícil de implementar que la criptografía simétrica, pero también es mucho más poderosa: la criptografía asimétrica le permite tener conversaciones privadas ¡Incluso sobre líneas giradas! También te permite crear “firmas digitales” para permitirle verificar de quién proviene un mensaje y que no ha sido manipulado.

Estas son herramientas poderosas y constituyen la base de la privacidad moderna: sin la criptografía asimétrica, los usuarios de dispositivos electrónicos no tendrían una protección confiable contra miradas indiscretas.

Debido a que la criptografía asimétrica es más difícil de construir que la simétrica, los esquemas de encriptación estándar que se usan hoy en día no son tan fuertes como podrían ser: el estándar de encriptación más común, RSA, puede ser descifrado si puede encontrar de manera eficiente los factores primos de gran número. La buena noticia es que es un problema muy difícil..

El algoritmo más conocido para factorizar grandes números en sus primos componentes se llama el tamiz de campo de número general, y tiene una complejidad de tiempo de ejecución que crece un poco más lentamente que 2 ^ n. Como consecuencia, las claves deben ser aproximadamente diez veces más largas para proporcionar una seguridad similar, que es algo que las personas normalmente toleran como un costo de hacer negocios. La mala noticia es que todo el campo de juego cambia cuando las computadoras cuánticas se lanzan a la mezcla.

Quantum Computers: Cambiando el juego criptográfico

Las computadoras cuánticas funcionan porque pueden tener múltiples estados internos al mismo tiempo, a través de un fenómeno cuántico llamado “superposición”. Eso significa que pueden atacar diferentes partes de un problema simultáneamente, divididas entre posibles versiones del universo. También pueden configurarse de modo que las ramas que resuelven el problema terminen con la mayor amplitud, de modo que cuando abra el cuadro en el gato de Schrödinger, la versión del estado interno con la que es más probable que se le presente es una presumida gato mirando un mensaje descifrado.

Para obtener más información sobre las computadoras cuánticas, consulte nuestro artículo reciente sobre el tema ¿Cómo funcionan las computadoras ópticas y cuánticas? ¿Cómo funcionan las computadoras ópticas y cuánticas? La Era Exascal se acerca. ¿Sabe cómo funcionan las computadoras ópticas y cuánticas, y estas nuevas tecnologías se convertirán en nuestro futuro? Lee mas !

El resultado de esto es que las computadoras cuánticas no son solo linealmente más rápidas, como lo son las computadoras normales: obtener dos o diez o cien veces más rápido no ayuda mucho cuando se trata de criptografía convencional que cientos de miles de millones de veces demasiado lento para procesar Las computadoras Quantum admiten algoritmos que tienen complejidades de tiempo de ejecución de menor crecimiento que las que de otra manera serían posibles. Esto es lo que hace que las computadoras cuánticas sean fundamentalmente diferentes de otras tecnologías computacionales futuras, como el grafeno y el cálculo del memrister. La última tecnología informática que debe ver para creer La última tecnología informática que debe ver para creer Consulte algunas de las últimas tecnologías informáticas que se configuran Transformar el mundo de la electrónica y las PC en los próximos años. Lee mas .

Para un ejemplo concreto, el algoritmo de Shor, que solo puede ejecutarse en una computadora cuántica, puede factorizar grandes números en log (n) ^ 3 El tiempo, que es drásticamente mejor que el mejor ataque clásico. Usar el tamiz de campo de número general para factorizar un número con 2048 bits toma aproximadamente 10 ^ 41 unidades de tiempo, lo que equivale a más de un billón de billones de billones de billones. Usando el algoritmo de Shor, el mismo problema solo toma alrededor de 1000 unidades de tiempo..

El efecto se hace más pronunciado cuanto más largas son las teclas. Ese es el poder de las computadoras cuánticas..

No me malinterpretes: las computadoras cuánticas tienen muchos usos potenciales no dañinos. Las computadoras Quantum pueden resolver de manera eficiente el problema de los vendedores ambulantes, lo que les permite a los investigadores construir redes de envío más eficientes y diseñar mejores circuitos. Las computadoras cuánticas ya tienen poderosos usos en inteligencia artificial..

Dicho esto, su papel en la criptografía va a ser catastrófico. Las tecnologías de encriptación que permiten que nuestro mundo siga funcionando dependen de que el problema de factorización de enteros sea difícil de resolver. RSA y los esquemas de encriptación relacionados son lo que te permite confiar en que estás en el sitio web correcto, que los archivos que descargas no están llenos de malware y que la gente no está espiando tu navegación en Internet (si estás usando Tor).

La criptografía mantiene su cuenta bancaria segura y protege la infraestructura nuclear del mundo. Cuando las computadoras cuánticas se vuelven prácticas, toda esa tecnología deja de funcionar. La primera organización en desarrollar una computadora cuántica, si el mundo aún funciona con las tecnologías que utilizamos hoy, se encontrará en una posición terriblemente poderosa..

Entonces, ¿es inevitable el apocalipsis cuántico? Hay algo que podamos hacer al respecto? Pues resulta que ... sí.

Criptografía post-cuántica

Existen varias clases de algoritmos de cifrado que, por lo que sabemos, no son significativamente más rápidos de resolver en una computadora cuántica. Estos se conocen colectivamente como criptografía post-cuántica, y brindan alguna esperanza de que el mundo pueda hacer la transición a sistemas criptográficos que permanecerán seguros en un mundo de encriptación cuántica..

Entre los candidatos prometedores se incluyen el cifrado basado en celosía, como Ring-Learning With Error, que deriva su seguridad de un problema de aprendizaje de máquina demostrablemente complejo, y la criptografía multivariable, que deriva su seguridad de la dificultad de resolver sistemas muy grandes de ecuaciones simples. Puedes leer más sobre este tema en el artículo de Wikipedia. Cuidado: muchas de estas cosas son complejas, y es posible que tengas que mejorar tu formación en matemáticas antes de poder profundizar en los detalles..

Lo que se desprende de mucho de esto es que los criptosquemas post-cuánticos son muy interesantes, pero también muy jóvenes. Necesitan más trabajo para ser eficientes y prácticos, y también para demostrar que están seguros. La razón por la que podemos confiar en los criptosistemas es porque les hemos lanzado suficientes genios clínicamente paranoicos durante el tiempo suficiente para que ya se hubieran descubierto defectos obvios, y los investigadores han demostrado varias características que los hacen fuertes..

La criptografía moderna depende de la luz como desinfectante, y la mayoría de los esquemas criptográficos post-cuánticos son simplemente demasiado nuevos para confiar en la seguridad mundial. Sin embargo, están llegando, y con un poco de suerte y algo de preparación, los expertos en seguridad pueden completar el cambio antes de que la primera computadora cuántica entre en funcionamiento..

Si fallan, sin embargo, las consecuencias pueden ser terribles. La idea de que alguien tenga ese tipo de poder es inquietante, incluso si eres optimista acerca de sus intenciones. La pregunta de quién desarrolla primero una computadora cuántica en funcionamiento es una que todos deberían observar con mucho cuidado a medida que avanzamos hacia la próxima década..

¿Le preocupa la inseguridad de la criptografía en las computadoras cuánticas? ¿Cuál es tu opinión? Comparte tus pensamientos en los comentarios a continuación!

Créditos de imagen: Orbe binario a través de Shutterstock

Explorar más sobre: ​​Seguridad en línea.