Me han dicho que los físicos y los informáticos están trabajando en ordenadores que podrían utilizar la física cuántica para aumentar significativamente la capacidad de cálculo y descifrar cualquier cifra, de modo que la criptografía deje de tener sentido.
¿Es cierto?
No, no lo es.
Los ordenadores cuánticos pueden factorizar grandes números de forma eficiente, lo que permitiría romper muchos de los criptosistemas de clave pública más utilizados, como RSA, que se basan en la dureza de la factorización.
Sin embargo, existen otros criptosistemas como criptografía reticular que no se basan en la dureza de la factorización, y que (según nuestros conocimientos actuales) no serían vulnerables al ataque de un ordenador cuántico.
La computación cuántica tiene un montón de promesas, pero no es infinitamente poderoso.
El (exagerada) de reclamaciones usted ha oído probablemente basado en el más famoso de la computación cuántica, algoritmo, el algoritmo de Shor. Este es un método para el uso de un ordenador cuántico para el factor de enteros en números primos. Como resultado, muchos de los esquemas de cifrado se basan en el hecho de que la factorización de grandes números es muy duro. Los mensajes pueden ser encriptados de forma bastante sencilla de tal manera que sólo alguien que conoce la factorización prima de un número en particular puede descifrar con cualquier cantidad razonable de esfuerzo. Si usted puede rápidamente factor grandes números, tendría que romper muchos de los actuales esquemas de cifrado.
Sin embargo, hay otras técnicas que no están directamente amenazados por las computadoras cuánticas. Si nada más, siempre se puede utilizar una sola vez almohadilla tan larga como el mensaje en sí. Esto es matemáticamente irrompible, ya que cualquier mensaje puede ser "descifrado" de la cifra uno con la estimación apropiada en la clave, así que no hay manera de que un intruso a conocer el verdadero mensaje.
Computación cuántica también puede abrir las puertas a la próxima generación de formas de de forma segura la transmisión de información. Por ejemplo, la mayoría de cifrado hoy en día es más que eso, la codificación de mensajes de manera que sólo el destinatario puede hacer sentido de ella. Pero no puede ser bueno cuántica formas físicamente asegurar que los intrusos no pueden acceder a la transmisión en el primer lugar.
Pero en muchos casos las escuchas no son el problema. Por ejemplo, yo tengo un archivo en mi disco duro que no quiero que nadie lea, aunque me roben la máquina.
@innisfree La mecánica cuántica ayuda más a los encriptadores que a los fisgones, ya que la distribución cuántica de claves hace viables los pads de un solo uso en un canal inseguro. Los sistemas actuales están diseñados de tal manera que cualquier fisgón provocaría un colapso de la función de onda, destruyendo el OTP en el proceso. También hay que tener en cuenta que el algoritmo de Shor es en gran medida una vulnerabilidad teórica (en el momento de escribir esto, el mayor número que se ha factorizado es 56153), mientras que estos sistemas QKD están en uso hoy en día.
De hecho, hay toda una clase de complejidad dedicada a la respuesta, que es "no, no puede romper ningún código". La clase se conoce como BQP o "tiempo polinómico cuántico de error acotado". Es la clase de problemas de decisión que puede resolver un ordenador cuántico en tiempo polinómico, con un margen de error no superior a 1/3 (este término de error se contabiliza en un paso de cálculo clásico que se produce después de la mayoría de los algoritmos cuánticos para verificar que los resultados son correctos).
Se cree que BQP tiene las siguientes relaciones con otros complejos:
(La mayor incógnita de esa lista es que aún no se sabe si P=NP. La lista asume que P!=NP, pero si P=NP, claramente NP y NP-completo también formarían parte de BQP. Tampoco sabemos si NP=BQP o no. ¡queda tanto por descubrir! )
RSA se puede descifrar utilizando ordenadores cuánticos porque la tarea de factorizar grandes números compuestos está en BQP, como demuestra el algoritmo de Shor. El algoritmo de Shor es NP (pero no NP-completo). Hay otros algoritmos NP que se cree que están fuera de BQP y que pueden utilizarse para el cifrado (la respuesta aceptada enlaza con la criptografía basada en celosías, que es una de esas clases de algoritmos).
Las respuestas hasta ahora se han centrado en el cifrado de clave pública, en el que alguien publica una clave pública que puede utilizarse para cifrar los mensajes que se le envían, y que no es secreta. Se sabe que los ordenadores cuánticos son eficientes para romper varios de los problemas más utilizados como base de la criptografía de clave pública. No afecta a todos criptografía de clave pública, sólo los esquemas más populares; sí afecta a los esquemas más populares.
Sin embargo, el cifrado es mucho más que una clave pública. Se cree que los esquemas de cifrado simétrico, en los que las dos partes comparten una clave secreta, no pueden acelerarse más de un cuadrático con ordenadores cuánticos (los ordenadores cuánticos pueden lograr un cuadrático de aceleración para problemas de búsqueda generales, pero no más). Esto equivale a reducir a la mitad la longitud de la clave. A diferencia de los sistemas de clave pública habituales, reducir a la mitad la longitud de la clave es extremadamente fácil: basta con duplicar la longitud de la clave y seguir adelante. El cifrado simétrico es extremadamente común; incluso cuando se utiliza el cifrado de clave pública, la mayoría de las veces sólo se utiliza para intercambiar una clave para el cifrado simétrico.
El sistema simétrico más común, AES, tiene una variante de clave de 256 bits que proporciona 128 bits de seguridad contra los ordenadores cuánticos. Otros sistemas en desarrollo admiten claves de 512 bits, que proporcionarían 256 bits de seguridad efectiva. Se cree que tanto 128 como 256 bits son seguros en un futuro previsible.
Del mismo modo, se cree que las funciones hash criptográficas resisten muy bien a los ordenadores cuánticos. Existe el mismo ataque basado en el algoritmo de Grover, pero al igual que con las funciones de cifrado es fácil de contrarrestar.
Por lo tanto, cualquier afirmación de que la criptografía carece de sentido está totalmente fuera de lugar, porque lo único que es seriamente afectados son los sistemas de clave pública. Los sistemas de clave pública son importantes, pero la criptografía es un campo mucho más amplio.
Y esta respuesta es precisamente la razón por la que creo que esta pregunta está fuera de tema aquí: no hay una gota de física aquí (algo que nosotros espere está en todas las respuestas).
@KyleKanos: Aquí hay una gota de física, en el algoritmo de Grover, que tenía suficiente física en 1997 como para ser publicado en Phys. Rev. Lett. ($$) ( Versión arXiv ) . Lo admito, es sólo una gota de física, pero saber si es física o informática es un problema común (y frustrante) con la información cuántica.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
9 votos
Lectura relacionada: ¿Cómo cambiará la criptografía con la computación cuántica? (y probablemente un poco en Criptografía 's post-quantum-cryptography etiqueta y Seguridad de la información 's informática cuántica tag).
8 votos
Voto por cerrar esta pregunta como off-topic porque la pregunta es sobre verificar la afirmación del uso de un ordenador cuántico y para nada sobre física. Quizás Criptografía o Escépticos podría ser más adecuado para esta pregunta.
9 votos
En realidad no creo que este sea el tema para nosotros. La única relación con la física es saber que un ordenador cuántico puede resolver ciertos problemas en un tiempo inferior al exponencial.
0 votos
No creo que sea para tanto. Respondí a una pregunta similar hace un tiempo, ¿Cómo cambiará la criptografía con la computación cuántica? y el tdlr de ello era que sabemos cómo lidiar con ordenadores cada vez más rápidos: espacios de claves más grandes.
1 votos
@NathanCooper Si puedo construir una máquina cuya capacidad para factorizar crezca más rápido que la capacidad de tu máquina para cifrar/descifrar, entonces los espacios de claves más grandes no ayudan. ¿O me estoy perdiendo algo?
0 votos
@DanielSank si....
0 votos
@emoria por supuesto "si". El punto es que lo que dijo Nathan no tiene sentido para mí.
0 votos
Creo que los 24 upvotes y las múltiples respuestas muy acertadas sugieren que esta pregunta era apropiada. Sugiero reabrirla. Se trata de una pregunta muy popular relacionada con la computación cuántica; sin duda es una pregunta interdisciplinar, pero el hecho de que sea interdisciplinar no significa que no pueda responderse o que esté fuera del tema de este foro.