encryption - duro - Compilación de Quantum y Encriptación
desencriptar disco duro symantec (10)
Aún más bizarro. es el algoritmo de Grover. Como entrada, obtenemos aquí una matriz desordenada de enteros con arraylength = n. ¿Cuál es el tiempo de ejecución esperado de un algoritmo, que encuentra el valor mínimo de este conjunto? Bien clásicamente, al menos debemos verificar cada elemento 1..n de la matriz, lo que da como resultado un tiempo de ejecución esperado de n. No es así para las computadoras cuánticas, en una computadora cuántica podemos resolver esto en el tiempo de ejecución esperado de máxima raíz (n), esto significa que ni siquiera tenemos que verificar cada elemento para encontrar la solución garantizada ...
Hace un tiempo leí que Quantum Computers puede romper la mayoría de los tipos de cifrado y hash que se usan actualmente en un tiempo muy corto (creo que fueron solo unos minutos). ¿Como es posible? Intenté leer artículos al respecto, pero me pierdo en a quantum bit can be 1, 0, or something else . ¿Alguien puede explicar cómo se relaciona esto con descifrar tales algoritmos en inglés simple sin todas las matemáticas sofisticadas?
Casi todas nuestras encriptaciones de clave pública (por ejemplo, RSA) se basan únicamente en matemática, dependiendo de la dificultad de factorization o discrete-logarithms . Ambos se romperán eficientemente usando computadoras cuánticas (aunque incluso después de un bachillerato en CS y Matemáticas, y haber tomado varias clases de mecánica cuántica, todavía no entiendo el algoritmo).
Sin embargo, los algoritmos de hash (Ej. SHA2) y los cifrados de clave simétrica (por ejemplo, AES) , que se basan principalmente en difusión y confusión , aún son seguros.
El artículo de Wikipedia hace un muy buen trabajo al explicar esto.
En resumen, si tiene N bits, su computadora cuántica puede estar en 2 ^ N estados al mismo tiempo . Similar conceptualmente a tener CPU de 2 ^ N procesando con bits tradicionales (aunque no exactamente lo mismo).
En los términos más básicos, una computadora no cuántica normal funciona operando en bits (encendidos o apagados) siguiendo la lógica booleana. Hace esto muy rápido por montones y montones de bits y puede resolver cualquier problema en una clase de problemas que son computables.
Sin embargo, son "límites de velocidad", es decir, algo llamado complejidad computacional. Esto significa que para un algoritmo determinado, usted sabe que el tiempo que lleva ejecutar un algoritmo (y el espacio de memoria requerido para ejecutar el algoritmo) tiene un límite mínimo . Por ejemplo, un algoritmo que es O (n ^ 2) significa que para un tamaño de datos de n requerirá n ^ 2 tiempo para ejecutarse.
Sin embargo, este tipo de mensaje sale por la ventana cuando tenemos qbits (bits cuánticos) cuando se realizan operaciones en qbits que pueden tener valores "intermedios". los algoritmos que tendrían una complejidad computacional muy alta (como factorizar números enormes, la clave para descifrar muchos algoritmos de cifrado) se pueden hacer en una complejidad computacional mucho más baja. Esta es la razón por la cual la computación cuántica podrá descifrar órdenes cifradas de órdenes de magnitud más rápido que las computadoras normales.
Es altamente teórico en este punto. Quantum Bits podría ofrecer la capacidad de romper el cifrado, pero es evidente que aún no está en ese punto.
En el nivel cuántico, las leyes que rigen el comportamiento son diferentes a las del nivel macro.
Para responder a su pregunta, primero debe comprender cómo funciona el cifrado.
En un nivel básico, el cifrado es el resultado de multiplicar dos números primos extremadamente grandes juntos. Este resultado súper grande es divisible por 1, sí mismo, y estos dos números primos.
Una forma de romper el cifrado es adivinar los dos números primos mediante la fuerza bruta, haciendo la factorización del número primo.
Este ataque es lento y se frustra al seleccionar números primos cada vez más grandes. Usted sabe de tamaños clave de 40bits, 56bits, 128bits y ahora 256,512bits y más. Esos tamaños corresponden al tamaño del número.
El algoritmo de fuerza bruta (en términos simplificados) podría parecerse
for(int i = 3; i < int64.max; i++)
{
if( key / i is integral)
{
//we have a prime factor
}
}
Entonces, ¿quieres probar con fuerza bruta los números primos? Bueno, eso llevará un tiempo con una sola computadora. Así que puedes intentar agrupar un montón de computadoras para dividir y conquistar. Eso funciona, pero todavía es lento para tamaños de teclas muy grandes.
Como una dirección de bit cuántico esto es que ambos son 0 y 1 al mismo tiempo. Así que supongamos que tienes 3 bits cuánticos (no te preocupes, pequeña).
Con 3 qbits, su programa puede tener los valores de 0-7 simulativamente
(000,001,010,011 etc.)
, que incluye los números primos 3,5,7 al mismo tiempo.
entonces, usando el algoritmo simple anterior, en lugar de aumentar i por 1 cada vez, puedes dividir una vez y verificar
0,1,2,3,4,5,6,7
todo al mismo tiempo.
Por supuesto, los bits cuánticos aún no han llegado a ese punto; todavía hay mucho trabajo por hacer en el campo; pero esto debería darle una idea de que si pudiéramos programar utilizando cuantos, cómo podríamos tratar de descifrar el cifrado.
Este circuito es un buen comienzo para entender cómo funciona el paralelismo de qubit. La entrada de 2 qubits está en el lado izquierdo. El qubit superior es x y el qubit inferior es ist y. El y qubit es 0 en la entrada, al igual que un bit normal. El x qubit por otro lado está en superposición en la entrada. y (+) f (x) se encuentra aquí para el módulo de adición 2, que significa 1 + 1 = 0, 0 + 1 = 1 + 0 = 1. Pero la parte interesante es que, dado que x-qubit está en superposición, f (x) es f (0) yf (1) al mismo tiempo y podemos realizar la evaluación de la función f para todos los estados simultáneamente sin usar ninguna (tiempo) bucles. Teniendo suficientes quibits podemos ramificar esto en curcuits infinitamente complicados.
Primero que nada, la computación cuántica apenas está fuera de la etapa teórica. Se están realizando muchas investigaciones y algunas células y circuitos cuánticos experimentales, pero aún no existe una "computadora cuántica".
Segundo, lea el artículo de wikipedia: http://en.wikipedia.org/wiki/Quantum_computer
En particular, "En general, una computadora cuántica con n qubits puede estar en una superposición arbitraria de hasta 2 ^ n estados diferentes simultáneamente (esto se compara con una computadora normal que solo puede estar en uno de estos 2 ^ n estados en cualquier momento ). "
Lo que hace que la criptografía sea segura es el uso de claves de encriptación que son números muy largos que tardarían mucho tiempo en factorizarse en sus primos constituyentes, y las claves son lo suficientemente largas como para intentar todos los valores clave posibles. también toma mucho tiempo para completar.
Dado que la computación cuántica puede (teóricamente) representar muchos estados en un pequeño número de células de qubits y operar en todos esos estados simultáneamente, parece que existe la posibilidad de utilizar la computación cuántica para realizar pruebas de fuerza bruta -todo lo posible-. pares clave-valor en un tiempo muy corto.
Si tal cosa es posible, podría ser el final de la criptografía tal como la conocemos.
Una computadora cuántica puede implementar el algoritmo de Shor que puede realizar rápidamente la factorización prima. Los sistemas de cifrado se basan en la suposición de que los primos grandes no se pueden factorizar en una cantidad de tiempo razonable en una computadora clásica.
Preámbulo: las computadoras cuánticas son bestias extrañas que realmente no hemos domesticado hasta el punto de utilidad. La teoría que los sustenta es abstracta y matemática, por lo que cualquier discusión acerca de cómo pueden ser más eficientes que las computadoras clásicas será inevitablemente larga y complicada. Necesitarás al menos una comprensión de pregrado de álgebra lineal y mecánica cuántica para comprender los detalles, pero trataré de transmitir mi comprensión limitada.
La premisa básica de la computación cuántica es la superposición cuántica . La idea es que un sistema cuántico (como un bit cuántico, o qubit , el análogo cuántico de un bit normal) puede, como usted dice, existir no solo en los estados 0 y 1 (llamados estados de base computacional del sistema) , pero también en cualquier combinación de los dos (para que cada uno tenga una amplitud asociada). Cuando alguien observa el sistema, el estado del qubit collapses en uno de sus estados básicos (es posible que hayas oído hablar del experimento de pensamiento felino de Schrödinger , que está relacionado con esto).
Debido a esto, un registro de n qubits tiene 2^n estados de base propios (estos son los estados en los que se puede observar que está el registro, imagine un entero clásico de n bits). Dado que el registro puede existir en una superposición de todos estos estados a la vez, es posible aplicar un cálculo a los 2^n estados de registro en lugar de solo uno de ellos. Esto se llama paralelismo cuántico .
Debido a esta propiedad de las computadoras cuánticas, puede parecer que son una bala de plata que puede resolver cualquier problema exponencialmente más rápido que una computadora clásica. Pero no es tan simple: el problema es que una vez que observa el resultado de su cálculo, colapsa (como mencioné anteriormente) en el resultado de solo uno de los cálculos, y pierde todos los demás.
El campo de los algoritmos / algoritmos cuánticos tiene que ver con intentar solucionar este problema manipulando fenómenos cuánticos para extraer información en menos operaciones de lo que sería posible en una computadora clásica. Resulta que es muy difícil idear un "algoritmo cuántico" que sea más rápido que cualquier contraparte clásica posible.
El ejemplo que preguntas es el del criptoanálisis cuántico. Se cree que las computadoras cuánticas podrían "romper" ciertos algoritmos de encriptación: específicamente, el algoritmo RSA, que se basa en la dificultad de encontrar los factores primos de enteros muy grandes. El algoritmo que permite esto se llama algoritmo de Shor , que puede factorizar enteros con complejidad de tiempo polinomial. Por el contrario, el mejor algoritmo clásico para el problema tiene una complejidad de tiempo (casi) exponencial, por lo que el problema se considera " intractable ".
Si desea una comprensión más profunda de esto, obtenga algunos libros sobre álgebra lineal y mecánica cuántica y póngase cómodo. Si quieres alguna aclaración, ¡veré lo que puedo hacer!
Aparte : para comprender mejor la idea de la superposición cuántica, piense en términos de probabilidades. Imagine que lanza una moneda y la atrapa en su mano, tapada para que no pueda verla. Como una analogía muy tenue , se puede pensar que la moneda está en una superposición de los "estados" de las cabezas y las colas: cada una tiene una probabilidad de 0.5 (y, naturalmente, dado que hay dos estados, estas probabilidades suman 1 ) Cuando quitas la mano y observas la moneda directamente, se colapsa en el estado de las cabezas o las colas, y entonces la probabilidad de este estado se convierte en 1, mientras que la otra se convierte en 0. Una forma de pensarlo, supongo, es un conjunto de escalas que se equilibra hasta la observación, en cuyo punto se inclina hacia un lado a medida que aumenta nuestro conocimiento del sistema y un estado se convierte en el estado "real".
Por supuesto, no pensamos en la moneda como un sistema cuántico: para todos los propósitos prácticos, la moneda tiene un estado definido, incluso si no podemos verlo. Para los sistemas cuánticos genuinos, sin embargo (como una partícula individual atrapada en una caja ), no podemos pensar en ello de esta manera. Bajo la interpretación convencional de la mecánica cuántica, la partícula fundamentalmente no tiene una posición definida , pero existe en todas las posiciones posibles a la vez. Solo después de la observación se encuentra su posición restringida en el espacio (aunque solo en un grado limitado, véase el principio de incertidumbre ), e incluso esto es puramente aleatorio y está determinado solo por la probabilidad.
Por cierto, los sistemas cuánticos no están restringidos a tener solo dos estados observables (los que sí lo hacen se llaman sistemas de dos niveles ). Algunos tienen un número grande pero finito, algunos tienen un número infinito contable (como una "partícula en una caja" o un oscilador armónico ), y algunos incluso tienen un número incontable infinito (como la posición de una partícula libre , que no es infinita). restringido a puntos individuales en el espacio).
computadoras cuánticas, etc. todas mentiras. No creo en estas revistas de ciencia ficción. de hecho, el sistema de rsa se basa en dos números primos y su multiplicación. p1, p2 es enorme primos p1xp2 = N módulo. el sistema rsa es así, elige un número primo ... puede ser pequeña su clave pública E (p1-1) * (p2-1) = R encuentra un número D que hace que E * D = 1 mod (R) que estamos compartiendo (E , N) datos como clave pública públicamente estamos guardando de forma segura (D, N) como privados.
Para resolver este sistema Rsa, el cracker necesita encontrar factores primos de N. * la masa del Universo está más cerca de 10 ^ 53 kg * la masa del electrón es 9.10938291 × 10 ^ -31 kilogramos si dividimos el universo en electrones podemos crear 10 ^ 84 electrones . los electrones tienen velocidades más lentas que la luz. su frecuencia de movimiento puede ser de 10 ^ 26 si alguien produce buscadores de factor primo rsa paralelos de tamaño de electrones de toda la masa del universo. todo el universo puede manejar (10 ^ 84) * (10 ^ 26) = 10 ^ 110 números / por segundo.
rsa tiene bits de limitadores de números primos alternativos. tal vez 4096 bits 4096 bits rsa tiene 10 ^ 600 posibles números primos para la fuerza bruta. por lo que su solucionador de quantum en masa del universo necesita hacer pruebas durante 10 ^ 500 años.
rsa vs universe quantum mass computer 1 - 0
tal vez la computadora cuántica puede romper contraseñas de 64/128 bits. porque la contraseña de 128 bits tiene 10 ^ 39 posibles nodos de fuerza bruta.