I computer quantistici saranno in grado di crackare facilmente le password?

Is this example just an oversimplification to demonstrate something which tries many possibilities at once; or is there a real potential security concern with the advent of quantum computers?

In primo luogo è solo una semplificazione eccessiva, ma c'è anche un vero problema di sicurezza.

The problem I have with this example, is it assumes that our ValidatePassword function accepts a qubit array as an input; which I suspect people would know better than to do.

Per i server web su Internet, questo è azzeccato. Non puoi inviare qubit su Internet, quindi non c'è modo di inviare questa "sovrapposizione quantistica di password" al server.

Il problema sorge quando ho un algoritmo che in qualche modo mi permette di verificare se una determinata password è corretta o meno. Supponiamo, ad esempio, di aver violato il database del sito Web e di aver trovato un hash delle password salate. Ora posso verificare se una password è corretta salando e taggandola e confrontandola con l'hash che ho trovato.

Supponiamo che ci voglia 1 millisecondo per testare una password e ci sono 1.000.000.000.000.000.000 di password possibili. Con l'informatica classica, se volessi provare tutte le password possibili, mi ci vorrebbero da 1.000.000.000.000.000.000 di millisecondi, vale a dire oltre 30 milioni di anni.

Con l'informatica quantistica, le cose sono diverse. Posso provare tutte le password contemporaneamente e quindi "comprimere il valore corretto", in modo da capire la password in pochi secondi? No, non è così semplice.

Quello che posso fare è usare Algoritmo di Grover . Ora, l'algoritmo di Grover è complicato e non so come funziona. Ma so cosa fa .

Con l'algoritmo di Grover, inizi con una sovrapposizione quantistica. Poi fai "l'alterazione di Grover" un sacco di volte. Effettuare una iterazione di Grover implica l'esecuzione dell'algoritmo di test della password una volta, insieme a un po 'di altre cose. Il numero di volte che devi eseguire l'iterazione di Grover è approssimativamente uguale alla radice quadrata del numero di password possibili, o 1.000.000.000. Perché devi farlo più volte? Non lo so. Poi fai altre cose e, in qualche modo, l'algoritmo di Grover ti dice quale sia la risposta.

Quindi quanto velocemente possiamo rompere la password? Bene, supponiamo che il nostro computer quantistico possa eseguire l'algoritmo di test della password in 1 millisecondo, proprio come un computer classico. (In realtà, sarà probabilmente più lento, perché creare un computer quantistico veloce è più difficile rispetto a un computer classico veloce.) Quindi il tempo necessario per decifrare la password è di circa 1.000.000.000 di millisecondi o di circa 12 giorni. Non male.

Qual è il risultato di tutto questo? L'informatica quantistica non ti permette semplicemente di "provare tutto in una volta", ma rende la ricerca della forza bruta molto più velocemente.

Il computer quantistico non decifra le password; craccatura crittografia

The problem with the currently popular [encryption] algorithms is that their security relies on one of three hard mathematical problems: the integer factorization problem, the discrete logarithm problem or the elliptic-curve discrete logarithm problem. All of these problems can be easily solved on a sufficiently powerful quantum computer running Shor's algorithm.

link

Articoli come questo è fondamentalmente fuorviato; danno al pubblico l'impressione che tutti i sistemi di password si interrompano quando viene creato il primo computer quantistico utilizzabile. Questo non è il caso. Secondo l'ammissione dello stesso articolo, non si tratta di password, ma di crittografia, che riguarda solo le persone che utilizzano la crittografia.

Naturalmente, se riesci a intercettare il tentativo di accesso di una persona su una connessione protetta utilizzando un computer quantistico per interrompere la crittografia della connessione, allora naturalmente hai le credenziali di accesso, ma non è proprio la stessa cosa di " password di cracking. "