¿Las computadoras cuánticas harán AES obsoleto?

La computación cuántica cambiará el juego de cifrado, pero aún no está claro cuánto cambiará. No está claro porque todavía no estamos seguros de qué tipo de problemas pueden resolver las computadoras cuánticas. Como se mencionó, la computación cuántica debilita dramáticamente el RSA porque la factorización de los números primos se puede hacer en tiempo polinomial usando el algoritmo de Shor. Sin embargo, no se sabe que todas las rutinas criptográficas sean tan débiles en comparación con la computación cuántica.

Es posible que haya oído hablar de P (tiempo polinomial), NP (tiempo polinomial no determinista: los problemas que se dan con la respuesta correcta pueden verificarse en tiempo polinomial), y NP-Complete (los problemas NP más difíciles). Se sabe que la factorización primaria de grandes números compuestos es un problema de NP y muchos piensan que no es un problema de P. Eso significa que una computadora convencional muy probablemente necesitaría super-polinomio tiempo (en el mejor momento sub-exponencial como GNFS ) para hacer la factorización y el cifrado RSA depende de esto. NP-completo es un problema un poco más exigente. Cualquier instancia de un problema de NP puede reducirse a una instancia de un problema de NP completa. (Esto es cierto incluso si el problema de NP es otro problema de NP-completo). Esto significa que si alguna vez encontró una solución de tiempo polinomial para un problema de NP-completo, tendría una solución de tiempo polinomial para cada Problema de NP Si lo hicieras usando una computadora clásica, habrías probado P = NP.

Las computadoras Quantum tienen su propia clase de complejidad. BQP es la clase de problemas que pueden resolverse [estadísticamente] mediante una computadora cuántica en tiempo polinomial. Se sabe que la factorización está en BQP, porque tenemos el algoritmo de Shor. Lo que aún se desconoce es si BQP contiene NP-completo o no. Actualmente se teoriza que no es así, lo que significa que hay problemas de NP-completos que aún llevan un tiempo exponencial, incluso con una computadora cuántica, pero los matemáticos aún están analizando esa teoría.

La factorización de enteros se encuentra en un interesante punto intermedio. Sabemos que es parte de BQP (porque encontramos el algoritmo de Shor). También sabemos que es un problema dentro de NP (es NP porque la factorización se puede probar en tiempo polinomial simplemente multiplicando los números de nuevo). Lo que aún no sabemos es si es P, NP-pero-no-P, o NP-completo. Nadie ha podido demostrarlo de una manera u otra. En realidad, podría ser un problema de P, solucionable con una computadora clásica en tiempo polinomial, lo que lo hace muy débil para propósitos de cifrado. Podría ser un problema NP-completo, que dado que sabemos que está en BQP, implicaría que las computadoras cuánticas pueden resolver cualquier problema NP en tiempo polinomial, lo que sería un gran golpe para la criptografía en general .

Muchos algoritmos de cifrado próximos están comenzando a usar otros problemas además de la factorización principal como su raíz. En particular, se cree que un conjunto de problemas basados en celosías es particularmente difícil de romper con las computadoras cuánticas. Si todos los problemas de NP son parte de BQP, esto no ayudará, pero todavía estamos resolviendo ese detalle hasta el día de hoy.

Resulta que AES no se ve afectado por el algoritmo de Shor. algoritmo de Grover permite forzar una clave de n bits en O (2 ^{n / 2} ) tiempo en lugar del tiempo O (2 ⁿ ) requerido por las computadoras clásicas. Por lo tanto, una clave AES de 128 bits podría ser forzada bruscamente en tiempo O (2 ⁶⁴ ) por una computadora cuántica suficientemente poderosa que puede hacer el algoritmo de Grover con 128+ qubits durante 2 ^ 64 veces.

¹ Los comentaristas sabios y desafiantes a continuación están eliminando la imprecisión en mi redacción. Técnicamente no se sabe si los problemas de NP requieren tiempo exponencial o no. Es posible que la clase de problemas NP y la clase de problemas P sean iguales. Sin embargo, la mayoría de los matemáticos creen que es mucho más probable que P! = NP, simplemente porque hasta ahora no lo parece. Si queremos hablar en términos de apuestas, solo mire cuánto podría hacer que responda la pregunta. Si demuestra que P y NP son distintos, puede ganar el premio Clay de un millón de dólares y tal vez obtener una oferta de trabajo cómoda por ser tan inteligente. Si demuestras que son iguales, esperaría que la NSA esté dispuesta a pagar mucho más para que guardes silencio sobre tu descubrimiento y, en cambio, entregue tus documentos a sus matemáticos.

Si está muy interesado en el tema de la computación cuántica y el cifrado, le recomiendo leer las diferentes clases de complejidad de como P y NP. Valen su tiempo.

No es imposible descifrar ninguno de esos algoritmos. El problema no es si se puede o no la fuerza bruta AES, se trata de cuánto tiempo tomará y si es factible o no.

Si desea romper AES con fuerza bruta usando computadoras normales, le llevaría buscar 2 ^ 128 claves que requerirán un mínimo de 2 ^ 128 operaciones.

Por otro lado, utiliza una computadora cuántica y un algoritmo de búsqueda como el algoritmo Grover al que podrás acceder a través del mismo número de teclas en (2 ^ 128) ^ 0.5 operaciones.

Aquí se debe tener en cuenta que las computadoras cuánticas pueden usarse para implementar protocolos de seguridad que son mucho mejores que lo que se puede hacer usando solo la informática clásica. Entonces, el verdadero problema está en su raíz de que la tecnología más avanzada (en el caso de esta pregunta, este es el caso hipotético de la disponibilidad de la computación cuántica) no está disponible para todos.

No. AES se considera criptografía post-cuántica que no quedará obsoleta por Quantum Computing (QC resistente).

Podría ser útil considerar la fortaleza del cifrado de manera inversamente proporcional a la fortaleza de la computación.

La fuerza de cifrado se mide clásicamente por la longitud de la clave. Los aumentos exponenciales en la fuerza de encriptación se logran duplicando la longitud de la clave. Por ejemplo, AES-256 es exponencialmente más fuerte que AES-128.

La comprensión actual es que el control de calidad podría representar un aumento exponencial de la potencia de cálculo en comparación con la informática clásica. Esto reduciría la fuerza de encriptación clásica a la mitad.

Por lo tanto, un cifrado sólido requeriría una doble longitud de clave para neutralizar la potencia de la informática de control de calidad.

Este sería el peor de los casos. Si la fuerza del control de calidad solo es sub-exponencialmente más fuerte, los aumentos menores en la longitud de la clave serían suficientes para neutralizar cualquier ventaja.

La longitud de clave mínima recomendada para un cifrado seguro debería aumentar de 90 a 180 bits.

RESULTADO: En el peor de los casos, AES-256 se reduciría de ridículamente fuerte a ridículamente fuerte, y AES-128 ya no se consideraría fuerte.

Tenga en cuenta que este asombroso resultado solo se logra comparando la potencia de la computación clásica (CC) a temperatura ambiente con la potencia de control de calidad sobreenfriado.

Los dispositivos CC de subenfriamiento también aumentan la potencia informática. Los dispositivos de control de calidad superconductores ya operan a casi cero Kelvin, el límite crítico de aumentar la potencia de cómputo por medios físicos.

TambiénCCadmiteinherentementeunaltogradodeescalabilidadatravésdelparalelismo,mientrasqueelQCexistentesoloadmite paralelismo restringido en el mejor de los casos .