¿Los cifrados están "rotos" con gran poder de cómputo?

Los criptosistemas de clave pública basan su seguridad en ciertos supuestos, uno de los cuales es que ciertos problemas matemáticos, aunque teóricamente solucionables, son computacionalmente imposibles de resolver. Los ejemplos típicos son la factorización de enteros y el problema de logaritmo inverso que se utilizan en sistemas criptográficos como RSA, DSA y Elgamal. Por ejemplo, un atacante que tiene una capacidad de procesamiento, memoria y tiempo infinitos, podría obtener una clave privada solo con una clave pública.

Las computadoras Quantum trabajan con qubits en lugar de bits, lo que significa que cada bit podría estar en 0, 1 o en una superposición de estos estados simultáneamente, en contraste con las computadoras clásicas donde cada bit solo puede estar en un estado a la vez. Esto conduce a lo que se llama paralelismo cuántico.

El problema real es encontrar cómo utilizar este paralelismo para resolver problemas matemáticos más rápido. Ciertas tareas, como la multiplicación, no se pueden realizar mucho más rápido con este tipo de computadora, mientras que otras, como la factorización de enteros, sí. Algoritmos como algoritmo de Shor explotan el poder del paralelismo cuántico para realizar la factorización de enteros en exponencialmente menos tiempo que computadoras normales Por ejemplo, factorizar un número de 1024 dígitos que llevaría miles de millones de millones de años, con una computadora cuántica podría tomar 20 minutos. Esto significa que los sistemas criptográficos como RSA que se basan en la inviabilidad computacional de dividir un número entero en dos números primos se considerarán obsoletos si se construye una computadora cuántica (que puede manejar dicho cálculo).

Por esta razón, los criptógrafos ya están investigando lo que sucedería en una era post-cuántica y han estado tratando de encontrar la forma de construir sistemas criptográficos de clave pública que se basen en problemas que las computadoras cuánticas no puedan resolver más rápido que las computadoras clásicas.

Finalmente, se debe decir que la criptografía simétrica no se ve afectada tanto por las computadoras cuánticas. Al usar una computadora cuántica, algoritmo de Grover puede hacer que la búsqueda de una tecla sea más rápida al necesitar el cuadrado Raíz del tiempo de una búsqueda normal de fuerza bruta. Esto es importante, pero se sugiere que simplemente duplicar la longitud de la clave es suficiente para mitigar el ataque.

Algunos algoritmos criptográficos, en particular la mayoría de los algoritmos asimétricos (cifrado asimétrico, firmas), sufren bastante en presencia de una verdadera computadora cuántica. Tenga en cuenta que el cifrado asimétrico McEliece y su homólogo de firma digital ( Niederreiter schema ) son, por el momento, inmunes a la computación cuántica (no hay pruebas de inmunidad, pero no se conoce ningún ataque con poder cuántico).

Una verdadera computadora cuántica también daría un impulso a los ataques a algoritmos simétricos, pero no a uno mortal. En el mejor de los casos, haría que AES con una clave de 256 bits no sea más fuerte que lo que AES con una clave de 128 bits hace hoy (es decir, aún irrompible).

La máquina anunciada por D-Wave parece no ser una verdadera computadora cuántica. Parece estar diseñado para encontrar aproximaciones a problemas de optimización que se comportan "sin problemas" (es decir, puede tener una solución "casi buena" y reconocerla como tal). Los algoritmos criptográficos son exactamente lo contrario de tales problemas.

Una verdadera computadora cuántica no se encuentra cerca de la potencia informática "infinita". Sin embargo, hay algunos algoritmos criptográficos que resisten una potencia de computación infinita, por ejemplo. Pad de una sola vez y El intercambio secreto de Shamir . Estos algoritmos tienen un rango de aplicación extremadamente específico y limitado, pero no temen a ninguna computadora, ya sea tradicional, cuántica o divina.

El infinito es realmente la palabra equivocada aquí: el poder de cómputo infinito gana, obviamente. Así que vuelve a lo que realmente quieres decir: aumentos masivos en el poder de cómputo, sí, obviamente tendrá un efecto. @John ha mencionado el efecto directo de la computación cuántica y ejemplos de dónde acelerará significativamente las cosas y dónde no.

Sin embargo, en general, los aumentos dramáticos en el poder de cómputo generalmente llevan a la necesidad de un aumento en la longitud de la clave, y los cambios de pasos en la forma en que se rompe el cifrado llevan a la necesidad de algoritmos nuevos y mejorados.

En resumen, no, no espero que vaya a necesitar cifrado, solo espero claves más largas, mejores algoritmos y, posiblemente, algoritmos que sean más resistentes a las computadoras cuánticas.