I computer quantici renderanno AES obsoleto?

Il calcolo quantico cambierà il gioco di crittografia, ma non è ancora chiaro quanto cambierà. Non è chiaro perché non siamo ancora certi di quali tipi di problemi possano risolvere i computer quantistici. Come accennato, RSA è drasticamente indebolito dal calcolo quantistico perché il factoring dei numeri primi può essere fatto in tempo polinomiale usando l'algoritmo di Shor. Tuttavia, non tutte le routine crittografiche sono note per essere un calcolo debole o quantistico.

Potresti aver sentito parlare di P (tempo polinomiale), NP (tempo polinomiale non deterministico - problemi che hanno la risposta giusta può essere controllato in tempo polinomiale), e NP-Completo (i problemi di NP più difficili). La fattorizzazione primaria di grandi numeri compositi è nota per essere un problema di NP e molti pensano che non sia un problema di tipo P. Ciò significa che un computer convenzionale avrebbe molto probabilmente bisogno di tempo super-polinomiale (al massimo tempo sub-esponenziale come GNFS ) per fare la fattorizzazione e la crittografia RSA dipende da questo. NP-complete è una classe di problemi leggermente più impegnativa. Qualsiasi istanza di un problema NP può essere ridotta a un'istanza di un problema NP-completo. (Questo è vero anche se il problema NP è un altro problema NP-completo.) Questo significa che se hai mai trovato una soluzione polinomiale per un problema NP-completo, avresti una soluzione polinomiale per ogni Problema NP Se lo facessi utilizzando un computer classico, avresti dimostrato P = NP.

I computer quantici hanno una propria classe di complessità. BQP è la classe di problemi che può essere [statisticamente] risolta da un computer quantistico in tempo polinomiale. È noto che la fattorizzazione è in BQP, perché abbiamo l'algoritmo di Shor. Ciò che è ancora sconosciuto è se BQP contiene NP-completo o no. Attualmente è teorizzato che non lo faccia, nel senso che ci sono problemi NP-completi che richiedono ancora tempo esponenziale, anche con un computer quantistico, ma i matematici stanno ancora scricchiolando a quella teoria.

La fattorizzazione di interi si trova in una interessante via di mezzo. Sappiamo che fa parte di BQP (perché abbiamo trovato l'algoritmo di Shor). Sappiamo anche che è un problema all'interno di NP (è NP perché la fattorizzazione può essere dimostrata in tempo polinomiale semplicemente moltiplicando i numeri di nuovo insieme). Quello che non sappiamo ancora è se sia P, NP-but-not-P o NP-complete. Nessuno è stato in grado di dimostrarlo in un modo o nell'altro. Potrebbe effettivamente essere un problema P, risolvibile con un computer classico in tempo polinomiale, rendendolo molto debole ai fini della crittografia. Potrebbe essere un problema NP-completo, che dato che sappiamo che è in BQP, implicherebbe che i computer quantistici possano risolvere il problema di any NP in tempo polinomiale, che sarebbe un duro colpo alla crittografia in generale .

Molti algoritmi di crittografia imminenti stanno iniziando a utilizzare altri problemi oltre alla fattorizzazione primaria come radice. In particolare, si ritiene che una serie di problemi basati su reticoli sia particolarmente difficile da rompere utilizzando i computer quantistici. Se tutti i problemi di NP fanno parte di BQP, questo non sarà di alcun aiuto, ma stiamo ancora cercando di capire quel dettaglio fino ad oggi.

Come risulta, AES non è influenzato dall'algoritmo di Shor. L'algoritmo di Grover consente la forzatura bruta di una chiave di n bit in O (2 ^{n / 2} ) tempo invece del tempo O (2 ⁿ ) richiesto dai computer classici. Pertanto, una chiave AES a 128 bit potrebbe essere forzata bruta in tempo O (2 ⁶⁴ ) da un computer quantistico sufficientemente potente che può eseguire l'algoritmo di Grover con 128+ qubit per 2 ^ 64 volte.

¹ I commentatori saggi e stimolanti di seguito rimproverano l'imprecisione nella mia formulazione. Tecnicamente non è noto se i problemi di NP richiedano tempi esponenziali o meno. È possibile che la classe di problemi NP e la classe P di problemi siano gli stessi. Tuttavia, la maggior parte dei matematici ritiene che sia molto più probabile che P! = NP, semplicemente perché finora non sembra. Se vogliamo parlare in termini di scommesse, guarda solo quanto potresti rispondere alla domanda. se provi che P e NP sono distinti, puoi guadagnare il premio Clay di un milione di dollari, e magari ottenere una comoda offerta di lavoro per essere così intelligente. Se dimostrerai di essere la stessa cosa, mi aspetterei che la NSA sia disposta a pagare molto di più perché tu taccia silenzio alla tua scoperta, e invece consegni i tuoi documenti ai loro matematici.

Se sei molto interessato al tema dell'informatica quantistica e della crittografia, ti consiglio vivamente di leggere le diverse classi di complessità come P e NP. Valgono il tuo tempo.

Non è impossibile decifrare nessuno di questi algoritmi. Il problema non è se si può eseguire la forza bruta AES o meno, si tratta di quanto tempo ci vorrebbe e se è fattibile o meno.

Se vuoi crackare AES con la forza bruta usando normali computer, ti porterebbe a cercare 2 ^ 128 chiavi che richiederanno minimo 2 ^ 128 operazioni.

D'altro canto, usando l'algoritmo quantistico e di ricerca come l'algoritmo Grover sarai in grado di andare attraverso lo stesso numero di chiavi in (2 ^ 128) ^ 0.5 operazioni.

Si noti qui che i computer quantistici possono essere utilizzati per implementare protocolli di sicurezza che sono molto meglio di quello che si può fare usando solo il calcolo classico. Quindi, il vero problema è alla radice che la tecnologia più avanzata (nel caso in cui questa domanda sia il caso ipotetico di calcolo quantistico disponibile) non sia disponibile per tutti.

No. AES è considerato Post-Quantum Cryptography che non sarà reso obsoleto da Quantum Computing (QC resistant).

Potrebbe essere utile considerare la forza della crittografia inversamente proporzionale alla forza di calcolo.

Il livello di crittografia è misurato classicamente in base alla lunghezza della chiave. Gli aumenti esponenziali della forza di crittografia vengono raggiunti raddoppiando la lunghezza della chiave. Ad esempio, AES-256 è esponenzialmente più strong di AES-128.

La comprensione corrente è che il controllo qualità potrebbe rappresentare un aumento esponenziale della potenza di calcolo rispetto al computing classico. Questo ridurrebbe la metà della forza di crittografia classica.

Quindi, una crittografia strong richiederebbe una doppia lunghezza della chiave per neutralizzare la forza di calcolo del QC.

Questo sarebbe lo scenario peggiore. Se la forza del QC è solo più strong in modo esponenziale, un minor aumento della lunghezza della chiave sarebbe sufficiente a neutralizzare qualsiasi vantaggio.

La lunghezza minima della chiave consigliata per la crittografia avanzata dovrebbe quindi aumentare da 90 a 180 bit.

RISULTATO: Nel peggiore dei casi, AES-256 sarebbe stato ridotto da ridicolmente strong a ridicolmente strong, e AES-128 non sarebbe più considerato strong.

Tieni presente che questo risultato sbalorditivo si ottiene solo confrontando la resistenza del calcolo classico della temperatura ambiente (CC) con la forza del QC superaffreddata.

I dispositivi Supercooling CC aumentano anche la potenza di calcolo. I dispositivi QC superconduttori funzionano già a Kelvin vicino allo zero, il limite critico per aumentare la potenza di calcolo con mezzi fisici.

AncheCCsupportaintrinsecamenteunaltogradodiscalabilitàtramiteparallelismo,mentreilQCesistentesupportasolo parallelismo vincolato al meglio .