Ho appena letto un passaggio nel libro di Zeilinger sul mondo dei quanti.
La mia domanda è: Supponiamo che esistano computer quantistici. Dato che un computer quantistico può usare l'algoritmo di Shor, quale lunghezza chiave deve utilizzare un utente oggi per la crittografia RSA sicura?
Qualsiasi chiave RSA di dimensioni ragionevoli verrà rotta da un computer quantistico di dimensioni comparabili usando l'algoritmo di Shor. Non utilizzare RSA se si desidera resistere ai computer quantici, indipendentemente dalla dimensione della chiave.
L'unica rivendicazione di una variante di RSA che sopravvive sono alcune diapositive di Bernstein che menzionano un Chiave RSA 2 ^ 43 bit costituita da 2 ^ 31 numeri primi con 4096 bit ciascuno. Questo è ovviamente ridicolmente impraticabile.
Concrete analysis suggests that RSA with 2^31 4096-bit primes provides > 2^100 security vs. all known quantum attacks. Key almost fits on a hard drive.
Se vuoi la crittografia asimmetrica che sopravvive ai computer quantistici, dovresti cercare altrove. Ad esempio, la cifratura basata su codice o reticolo si crede sia sicura contro i CQ pur avendo proprietà ragionevoli. pqcrypto.org fornisce una ragionevole panoramica dell'impatto dei CQ e quali classi dell'algoritmo sono utili come schemi di crittografia post-quantistica.
Se i computer quantistici generici possono essere ridimensionati per attaccare con facilità RSA di qualsiasi dimensione di chiave modesta (ad esempio, b = 128 bit), quindi RSA a qualsiasi lunghezza della chiave non è sicuro (o presto sarà , a meno che non vi sia qualche importante barriera teorica che consenta di costruire sistemi di queste dimensioni ma impedisca di costruire sistemi più grandi). Per attaccare RSA a 1024 bit è necessario un computer quantistico con b = 1024 qubit. Quindi, dovrebbe essere in grado di interrompere RSA in O (b ^ 3) calcolando il modulo usando l'algoritmo di Shor. Per b = 4096 bit RSA, è solo una modesta scala del sistema quantistico (di un fattore 4 nel numero di qubit) e il tempo di esecuzione è solo 64 volte peggiore. Paragonare alla differenza classica in cui una chiave a 4096 bit che utilizza il miglior algoritmo di fattorizzazione sub-esponenziale è 100.000.000.000 (cioè 10 11 ) volte più strong di una chiave a 1024 bit. Nota anche per gli utenti ordinari del criptosistema, che il tempo di crittografia / decrittografia di RSA a 1024 bit è circa 64 volte più veloce di RSA a 1024/4096 bit, il che significa che non ci sarà una dimensione della chiave più grande in cui un utente classico di RSA ottiene un vantaggio significativo rispetto a un calcolo quantistico attaccante.
Tuttavia, i computer quantistici in grado di eseguire l'algoritmo di Shor per calcolare gli interi di grandi dimensioni sono molto lontani . Le migliori esecuzioni pubblicate dell'algoritmo di Shor hanno preso in considerazione 15 in 3x5 nel 2001 e ci sono voluti più di un decennio prima che un altro gruppo prendesse in considerazione 21 in 3x7 (il record attuale). I sistemi di ricottura quantica dei sistemi DWave sono molto lontani dall'essere un computer quantico di uso generale che può fare l'algoritmo di Shor; possono risolvere solo un problema specifico - il problema di Dwave e non è stato dimostrato che risolvono più velocemente dei problemi di ricottura classica ottimizzati .
Tuttavia, se sei preoccupato dell'informatica quantistica devi eseguire la migrazione dai sistemi PKE basati sulla fattorizzazione di interi o sui logaritmi discreti (inclusi RSA / DSA / El Gamal anche con curve ellittiche) che possono essere attaccati dall'algoritmo di Shor (o una versione leggermente modificata per le curve ellittiche).
Esistono tipi di PKE resistenti all'algoritmo di Shor ma nessuno di essi sembra avere un uso diffuso.
Uno dei più promettenti è McEliece cryptosystem che è più veloce di RSA e può far crescere la sicurezza con le dimensioni della chiave rapidamente , ad eccezione della chiave pubblica è in genere di circa mezzo megabyte.
Un altro è NTRUEncrypt che ha dimensioni e prestazioni ragionevoli della chiave, ma non ha subito la stessa analisi crittografica di RSA (ed è brevettato).
Si noti che sebbene non sia garantito che un nuovo algoritmo quantistico arriverà e romperà questi PKE resistenti a Shor, non è previsto. È possibile dimostrare che questi algoritmi si basano su problemi NP-hard, quindi se vengono interrotti da un nuovo algoritmo quantistico questo sarà un importante passo avanti nella teoria della complessità (non grande quanto la risoluzione di P = NP o P! = NP, ma chiusa) .
Infine, dovremmo notare la differenza tra la crittografia simmetrica e la crittografia asimmetrica per quanto riguarda il calcolo quantistico. Per la crittografia simmetrica (ad esempio, cifrario a blocchi), l'algoritmo di Grover consente di rompere una chiave simmetrica di complessità O (N ) in O (sqrt (N)) tempo. Il significato di una chiave a 128 bit, che richiederebbe il tempo O (2 128 ) alla forza bruta classicamente, richiederebbe solo il tempo O (2 64 ) con un computer quantistico adatto . Quindi, in contesti come la dimensione della tua chiave simmetrica e la dimensione del tuo hash, dovresti semplicemente raddoppiare la lunghezza necessaria in modo classico (cioè migrare da AES-128 ad AES-256 per essere sicuro).
Le diapositive menzionate da CodesInChaos descrivono in dettaglio un metodo per eseguire crypto RSA multi-prime (qualcosa non in uso diffuso) per aggirare il problema principale con RSA rispetto all'algoritmo di Shor: se le operazioni di qbit sono veloci come operazioni di bit, allora Shor's Algorithm può calcolare i primi velocemente quanto RSA può cifrare per qualsiasi dimensione della chiave.
Per aggirare questo problema, il metodo spiegato da DJB utilizza RSA multi-prime per consentire una crittografia più veloce con l'utilizzo di un numero significativamente maggiore di materiale chiave.
Quanto più? 8 Terabyte per ottenere approssimativamente lo stesso livello di sicurezza che abbiamo oggi.
Leggi altre domande sui tag encryption rsa