Le crittografie sono "rotte" con grande potenza di calcolo?

I crittosistemi a chiave pubblica basano la loro sicurezza su determinati presupposti, uno dei quali è che determinati problemi matematici, mentre teoricamente risolvibili, sono computazionalmente impossibili da risolvere. Esempi tipici sono la fattorizzazione di interi e il problema del logaritmo inverso che vengono utilizzati in crittosistemi come RSA, DSA ed Elgamal. Ad esempio, un utente malintenzionato con una potenza di elaborazione infinita, memoria e tempo, potrebbe derivare una chiave privata solo con una chiave pubblica.

I computer quantistici funzionano con qubit anziché bit, il che significa che ogni bit potrebbe essere in 0, 1 o una sovrapposizione di questi stati simultaneamente, in contrasto con i computer classici in cui ogni bit può essere solo in uno stato alla volta. Questo porta a ciò che è chiamato il parallelismo quantistico.

Il vero problema è trovare come utilizzare questo parallelismo per risolvere i problemi matematici più velocemente. Determinate attività, come la moltiplicazione, non possono essere eseguite molto più velocemente da questo tipo di computer, mentre altre, come la fattorizzazione di un intero, possono farlo. Algoritmi come l'algoritmo di Shor sfruttano la potenza del parallelismo quantistico per eseguire la fattorizzazione di interi in un tempo esponenzialmente inferiore a computer normali. Ad esempio, la fattorizzazione di un numero di 1024 cifre che richiederebbe miliardi di miliardi di anni, con un computer quantico potrebbe richiedere 20 minuti. Ciò significa che i crittosistemi come RSA che si basano sull'informabilità computazionale della rottura di un intero in due numeri primi saranno considerati obsoleti se un computer quantistico (in grado di gestire tale calcolo) sarà costruito.

Per questo motivo, i crittografi stanno già facendo ricerche su cosa accadrebbe in un'era post-quantistica e stanno cercando di trovare come costruire criptosistemi a chiave pubblica che si basano su problemi che non possono essere risolti dai computer quantistici più velocemente di quei computer classici.

Infine, si dovrebbe affermare che la crittografia simmetrica non è influenzata tanto dai computer quantistici. Usando un computer quantistico, l'algoritmo di Grover può rendere la ricerca di una chiave più rapida richiedendo il quadrato radice del tempo di una normale ricerca di forza bruta. Questo è significativo, ma è suggerito che raddoppiare semplicemente la lunghezza della chiave sia sufficiente per mitigare l'attacco.

Alcuni algoritmi crittografici, in particolare la maggior parte degli algoritmi asimmetrici (crittografia asimmetrica, firme), soffrono molto in presenza di un vero computer quantistico. Si noti che la crittografia asimmetrica di McEliece e la controparte della firma digitale ( schema di Niederreiter ) sono, per il momento, immuni al calcolo quantistico (non esiste alcuna prova di immunità, ma per questi non è noto alcun attacco a potenza quantistica).

Un vero computer quantico darebbe anche una spinta agli attacchi su algoritmi simmetrici, ma non mortali. Nel migliore dei casi, renderebbe AES con una chiave a 256 bit non più strong di quella che AES ha con una chiave a 128 bit (vale a dire ancora infrangibile).

La macchina annunciata da D-Wave appare not come un vero computer quantico. Sembra essere progettato per trovare approssimazioni ai problemi di ottimizzazione che si comportano "senza problemi" (cioè si può avere una soluzione "quasi buona" e riconoscerla come tale). Gli algoritmi crittografici sono esattamente l'opposto di tali problemi.

Un vero computer quantistico non è affatto vicino alla potenza di calcolo "infinita". Tuttavia, sono alcuni algoritmi crittografici che resistono all'infinita potenza di calcolo, ad es. One-Time Pad e Shamir's Secret Sharing . Questi algoritmi hanno un range di applicazioni estremamente specifico e limitato, ma temono nessun computer, sia esso tradizionale, quantico o divino.

L'infinito è davvero la parola sbagliata qui - la potenza di calcolo infinita vince, ovviamente. Quindi ridimensionandolo a ciò che intendi veramente: aumenti massicci della potenza di calcolo, sì, ovviamente avrà un effetto. @ John ha menzionato l'effetto diretto dell'informatica quantistica ed esempi di dove accelererà notevolmente le cose e dove non lo farà.

In generale, tuttavia, gli aumenti drammatici della potenza di calcolo generalmente portano a un aumento della lunghezza della chiave e le modifiche apportate al modo in cui la crittografia viene interrotta comportano la necessità di algoritmi nuovi e migliorati.

Quindi, in sintesi, no non mi aspetto che sia necessario il criptaggio - mi aspetto solo chiavi più lunghe, algoritmi migliori e algoritmi potenzialmente più resistenti ai computer quantistici.