Computadoras cuánticas: ¿El fin de la criptografía?

Anuncio

La computación cuántica es una de esas tecnologías que es tan misteriosa que los nombres de los personajes de televisión la abandonan cuando quieren sonar de manera inteligente.

La computación cuántica como idea ha existido por un tiempo: la posibilidad teórica fue introducida originalmente por Yuri Manin y Richard Feynman en 1982. Sin embargo, en los últimos años, el campo se ha estado acercando preocupantemente a la practicidad.

Empresas como Google y Microsoft, así como agencias gubernamentales como la NSA, han estado buscando fervientemente computadoras cuánticas durante años. Una compañía llamada D-Wave ha producido y está vendiendo dispositivos que (si bien no son computadoras adecuadas y pueden solo realiza unos pocos algoritmos) explota las propiedades cuánticas y es otro paso incremental en el camino hacia un completamente Turing-complete ¿Qué es la prueba de Turing y alguna vez será superada?La prueba de Turing está destinada a determinar si las máquinas piensan. ¿El programa Eugene Goostman realmente pasó la prueba de Turing, o los creadores simplemente hicieron trampa?

Lee mas máquina cuántica

No parece irrazonable decir que podrían ocurrir avances que permitan construir la primera computadora cuántica a gran escala en una década.

Entonces, ¿por qué tanto interés? ¿Por qué te debe importar? Las computadoras se vuelven más rápidas todo el tiempo ¿Qué es la ley de Moore y qué tiene que ver contigo? [MakeUseOf explica]La mala suerte no tiene nada que ver con la Ley de Moore. Si esa es la asociación que tenía, la está confundiendo con la Ley de Murphy. Sin embargo, no estabas lejos porque la Ley de Moore y la Ley de Murphy ... Lee mas - ¿Qué tienen de especial las computadoras cuánticas?

Para explicar por qué estas máquinas son tan importantes, vamos a tener 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 de 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 tienes una computadora que resuelve un problema de un cierto tamaño en un cierto período de tiempo, duplicar la velocidad de la computadora no necesariamente le permite abordar los problemas el doble de tiempo grande.

Algunos algoritmos aumentan 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 dado 100 puntos de datos, pero completar el algoritmo dado 1000 puntos de datos requeriría una computadora del tamaño de la Tierra funcionando por mil millones años. La complejidad del tiempo de ejecución es una formalización de esta idea: analiza la curva de cuán rápido crece la complejidad de un problema y utiliza la forma de esa curva para clasificar el algoritmo.

Generalmente, estas clases de dificultad se expresan como funciones. Se dice que un algoritmo que se vuelve proporcionalmente más difícil cuando el conjunto de datos funciona (como una función de conteo simple) es una función con una complejidad de tiempo de ejecución de "norte" (como en, se necesita norte unidades de tiempo para procesar norte puntos de datos).

Alternativamente, podría llamarse "lineal", porque cuando lo grafica, obtiene una línea recta. Otras funciones pueden ser n ^ 2 o 2 ^ n o ¡norte! (n factorial). Estos son polinomios y exponenciales. En los últimos dos casos, los exponenciales crecen tan rápido que en casi todos los casos no se pueden resolver para nada, excepto ejemplos muy triviales.

Complejidad de tiempo de ejecución y criptografía

Si escuchas estas cosas por primera vez y suena sin sentido y arcano, intentemos basar 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 los 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 las posibles claves, lo cual es intratable para claves de solo unos 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 comenzar 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 entre sí, es una matemática mucho más difícil estructura para 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 sobredimensionadas ¡líneas! También le 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 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 cifrado más común, RSA, puede descifrarse si puede encontrar eficientemente los factores primos de un número. La buena noticia es que ese es un problema muy difícil.

El algoritmo más conocido para factorizar números grandes en sus números primos componentes se llama tamiz de campo de número general, y tiene una complejidad de tiempo de ejecución que crece un poco más lento que 2 ^ n. Como consecuencia, las claves tienen que ser aproximadamente diez veces más largas para proporcionar una seguridad similar, que es algo que las personas normalmente toleran como 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.

Computadoras cuánticas: 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 en posibles versiones del universo. También se pueden configurar de modo que las ramas que resuelven el problema terminen con la mayor amplitud, de modo que cuando abra la caja El gato de Schrodinger, la versión del estado interno con el que es más probable que te presenten es un gato de aspecto presumido que tiene un desencriptado mensaje.

Para obtener más información sobre computadoras cuánticas, consulte nuestro reciente artículo sobre el tema ¿Cómo funcionan las computadoras ópticas y cuánticas?La era de Exascale se acerca. ¿Sabes 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 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 es cientos de miles de millones de veces demasiado lento para procesar. Las computadoras cuánticas admiten algoritmos que tienen complejidades de tiempo de ejecución cada vez más pequeñas que las que de otro modo serían posibles. Esto es lo que hace que las computadoras cuánticas sean fundamentalmente diferentes de otras tecnologías computacionales futuras, como cálculo de grafeno y memrister La última tecnología informática que debes ver para creerEcha un vistazo a algunas de las últimas tecnologías informáticas que están preparadas para 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 se puede ejecutar en una computadora cuántica, puede factorizar grandes números en log (n) ^ 3 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 lleva aproximadamente 10 ^ 41 unidades de tiempo, lo que equivale a más de un billón de billones de billones. Usando el algoritmo de Shor, el mismo problema solo toma alrededor de 1000 unidades de tiempo.

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

No me malinterpreten: las computadoras cuánticas tienen muchos usos potenciales no malvados. Las computadoras cuánticas pueden resolver eficientemente el problema del vendedor ambulante, permitiendo a los investigadores construir redes de envío más eficientes y diseñar mejores circuitos. Las computadoras cuánticas ya tienen usos poderosos en inteligencia artificial.

Dicho esto, su papel en la criptografía será catastrófico. Las tecnologías de cifrado 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 cifrado relacionados son los que le permiten confiar en que está en el sitio web correcto, que los archivos que las descargas no están plagadas de malware y las personas no están espiando su navegación por Internet (si está usando Colina).

La criptografía mantiene su cuenta bancaria segura y asegura 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 todavía funciona con las tecnologías que usamos hoy, estará en una posición terriblemente poderosa.

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

Criptografía post-cuántica

Existen varias clases de algoritmos de cifrado que, hasta donde 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 criptosistemas que permanecerán seguros en un mundo de encriptación cuántica.

Los candidatos prometedores incluyen el cifrado basado en redes, como Ring-Learning With Error, que deriva su seguridad de un complejo demostrablemente complejo. problema de aprendizaje automático y criptografía multivariada, que deriva su seguridad de la dificultad de resolver sistemas muy grandes de sistemas simples ecuaciones Puede leer más sobre este tema en el Artículo de Wikipedia. Tenga cuidado: muchas de estas cosas son complejas, y es posible que sus conocimientos matemáticos deban reforzarse considerablemente antes de poder profundizar en los detalles.

La conclusión de mucho de esto es que los criptoesquemas post-cuánticos son muy geniales, pero también muy jóvenes. Necesitan más trabajo para ser eficientes y prácticos, y también para demostrar que son seguros. La razón por la que podemos confiar en los criptosistemas es porque les hemos arrojado suficientes genios clínicamente paranoicos durante el tiempo suficiente. que las deficiencias obvias ya se habrían descubierto, y los investigadores han demostrado diversas características que las hacen fuerte.

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 allí, 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.

Sin embargo, si fallan, las consecuencias pueden ser nefastas. La idea de que alguien tenga ese tipo de poder es inquietante, incluso si eres optimista sobre sus intenciones. La cuestión de quién desarrolla primero una computadora cuántica en funcionamiento es una que todos deben observar con mucho cuidado a medida que avanzamos en la próxima década.

¿Le preocupa la inseguridad de la criptografía para 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 Via Shutterstock