Acabo de leer un pasaje en el libro de Zeilinger sobre el mundo cuántico.
Mi pregunta es: Supongamos que existen ordenadores cuánticos. Dado que una computadora cuántica puede usar el algoritmo de Shor, ¿Qué longitud de clave debe usar un usuario hoy para el cifrado RSA seguro?
Cualquier clave RSA de tamaño razonable se romperá con una computadora cuántica de tamaño comparable utilizando el algoritmo de Shor. No use RSA si quiere resistir las computadoras cuánticas, sin importar el tamaño de la clave.
La única reclamación de una variante de RSA que sobrevive son algunas diapositivas de Bernstein que mencionan una La clave RSA de 2 ^ 43 bits consta de 2 ^ 31 primos con 4096 bits cada uno. Esto es obviamente ridículamente poco práctico.
El análisis concreto sugiere que RSA con 2 ^ 31 primos de 4096 bits proporciona > 2 ^ 100 de seguridad Contra todos los ataques cuánticos conocidos. La llave casi cabe en un disco duro.
Si desea una criptografía asimétrica que sobreviva a las computadoras cuánticas, debería buscar en otra parte. Por ejemplo, se cree que el código o la criptografía basada en celosía son seguros contra QC mientras que tienen propiedades razonables. pqcrypto.org ofrece una visión general razonable sobre el impacto de los QC y qué clases de algoritmos son útiles como esquemas de criptografía postcuántica.
Si las computadoras cuánticas de propósito general pueden ampliarse para atacar de manera factible el RSA de cualquier tamaño de clave modesto (por ejemplo, b = 128 bits), entonces el RSA en cualquier longitud de clave no es seguro (o pronto será , a menos que exista alguna barrera teórica importante que permita la construcción de sistemas de ese tamaño pero que impida la construcción de sistemas más grandes). Para atacar el RSA de 1024 bits necesita una computadora cuántica con b = 1024 qubits. Entonces, debería poder romper RSA en O (b ^ 3) factorizando el módulo usando el algoritmo de Shor. Para b = 4096 bit RSA, es solo una modesta ampliación del sistema cuántico (por un factor de 4 en el número de qubits) y el tiempo de ejecución es solo 64 veces peor. Compare con la diferencia clásica donde una clave de 4096 bits que usa el mejor algoritmo de factorización sub-exponencial es 100 000 000 000 (es decir, 10 11 ) veces más fuerte que una clave de 1024 bits. También tenga en cuenta para los usuarios normales del sistema de cifrado, que el tiempo de cifrado / descifrado de RSA de 1024 bits es aproximadamente 64 veces más rápido que el RSA de 1024/4096 bits, lo que significa que no habrá un tamaño de clave mayor en el que un usuario clásico de RSA obtenga una ventaja significativa sobre la computación cuántica agresor.
Sin embargo, las computadoras cuánticas que pueden ejecutar el algoritmo de Shor para calcular enteros grandes están muy lejos . Las mejores ejecuciones publicadas del algoritmo de Shor tuvieron en cuenta 15 en 3x5 en 2001, y tomó más de una década antes de que otro grupo incluyera 21 en 3x7 (el registro actual). Los sistemas de recocido cuántico de los sistemas DWave están muy lejos de ser computadoras cuánticas de propósito general que pueden hacer el algoritmo de Shor; solo pueden resolver un problema específico: el problema Dwave y no se ha demostrado que resuelvan más rápido que los problemas de recocido clásico optimizado .
Sin embargo, si le preocupa la computación cuántica, debe migrar desde sistemas PKE basados en factorización de enteros o logaritmos discretos (incluido RSA / DSA / El Gamal incluso con curvas elípticas) que pueden ser atacados por el algoritmo de Shor (o una versión ligeramente modificada para curvas elípticas).
Existen tipos de PKE resistentes al algoritmo de Shor pero ninguno de ellos parece tener un uso generalizado.
Uno de los más prometedores es el McEliece cryptosystem que es más rápido que RSA y puede hacer que la seguridad crezca con el tamaño de la clave rápidamente , excepto que la clave pública suele ser de aproximadamente medio megabyte.
Otro es NTRUEncrypt que tiene un tamaño y un rendimiento de clave razonables, pero no ha pasado tanto por criptoanálisis como RSA (y está patentado).
Tenga en cuenta que si bien no hay garantía de que un nuevo algoritmo cuántico aparezca y rompa estos PKE resistentes a Shor, no se espera. Puede mostrar que estos algoritmos se basan en problemas NP-difíciles, por lo que si se rompen con un nuevo algoritmo cuántico, este será un gran avance en la teoría de la complejidad (no tan grande como resolver P = NP o P! = NP, pero cerca) .
Finalmente, debemos notar la diferencia entre el cifrado simétrico y el cifrado asimétrico con respecto a la computación cuántica. Para el cifrado simétrico (por ejemplo, cifrado de bloque), algoritmo de Grover permite romper una clave simétrica de complejidad O (N ) en tiempo O (sqrt (N)). El significado de una clave de 128 bits, que tomaría el tiempo O (2 128 ) a la fuerza bruta clásicamente, solo tomaría el tiempo O (2 64 ) con una computadora cuántica adecuada . Por lo tanto, en contextos como el tamaño de su clave simétrica y el tamaño de su hash, simplemente debe duplicar la longitud necesaria clásicamente (es decir, migrar de AES-128 a AES-256 para estar seguro).
Las diapositivas mencionadas por CodesInChaos detallan un método para realizar criptografía RSA multiprofesional (algo que no se usa ampliamente) para solucionar el problema principal de RSA con respecto al algoritmo de Shor: si las operaciones de qbit son tan rápidas como las operaciones de bits, El algoritmo de Shor puede factorizar números primos tan rápido como RSA puede cifrar para cualquier tamaño de clave dado.
Para evitar esto, el método explicado por DJB utiliza RSA multiprincipal para permitir un cifrado más rápido con, al mismo tiempo que utiliza significativamente más material clave.
¿Cuánto más? 8 terabytes para obtener aproximadamente el mismo nivel de seguridad que tenemos hoy.
Lea otras preguntas en las etiquetas encryption rsa