Quali tipi di crittografia sono _not_ breakable tramite Quantum Computers?

102

C'è il recente articolo L'NSA cerca di costruire computer quantistici in grado di decifrare la maggior parte dei tipi di crittografia . Ora non sono sorpreso dalla NSA che prova qualcosa di 1 , ma ciò che mi confonde leggermente è la parola "più" - quindi, quali algoritmi di crittografia sono noti e sufficientemente testati sul campo che sono non gravemente vulnerabile al Quantum Computing?

    
posta Tobias Kienzler 03.01.2014 - 15:15
fonte

5 risposte

142

Come al solito, il giornalismo che parla di argomenti tecnici tende a essere confuso sui dettagli ...

Supponendo che sia possibile costruire un vero computer quantistico , quindi:

  • RSA e altri algoritmi che si basano sulla durezza della fattorizzazione di interi (ad esempio Rabin), sono toast. L'algoritmo di Shor influenza i grandi numeri interi in modo molto efficiente.
  • DSA, Diffie-Hellman ElGamal e altri algoritmi che si basano sulla durezza del logaritmo discreto , sono ugualmente spezzati. Si applica anche una variante dell'algoritmo di Shor. Nota che questo è vero per ogni gruppo, quindi le varianti della curva ellittica di questi algoritmi non sono migliori.
  • La crittografia simmetrica è indebolita ; cioè, un computer quantico può cercare attraverso uno spazio di dimensioni 2 n nel tempo 2 n / 2 . Ciò significa che una chiave AES a 128 bit potrebbe essere retrocessa alla forza di una chiave a 64 bit, tuttavia, si noti che si tratta di operazioni 2 64 _quantum-computing_ ; non è possibile applicare cifre provenienti da studi con FPGA e GPU e presupporre ciecamente che se un computer quantistico può essere del tutto , può essere costruito e gestito economicamente .

  • Allo stesso modo, la resistenza alle funzioni hash a vari tipi di attacchi sarebbe ridotta in modo simile. In parole povere, una funzione di hash con un output di n bit resisterebbe alle pre-immagini con forza 2 n / 2 e collisioni fino a 2 n / 3 (figure con computer classici 2 n e 2 n / 2 , rispettivamente). SHA-256 sarebbe ancora strong contro le collisioni come una funzione di hash a 170 bit al giorno d'oggi, cioè meglio di un "perfetto SHA-1".

Quindi la crittografia simmetrica non sarebbe gravemente danneggiata se un computer quantistico risultasse costruito. Anche se potesse essere costruito molto a buon mercato l'algoritmo di crittografia simmetrica e gli algoritmi di funzione hash offrirebbero comunque un bel po 'di resistenza. Per la crittografia asimmetrica, tuttavia, ciò significherebbe un problema. Tuttavia, conosciamo diversi algoritmi asimmetrici per i quali non si conosce un attacco efficiente basato su QC, in particolare algoritmi basati su riduzione del reticolo (ad esempio NTRU) e la venerabile crittografia McEliece . Al giorno d'oggi questi algoritmi non sono molto popolari, per una serie di motivi (le prime versioni di NTRU si sono rivelate deboli, ci sono brevetti, le chiavi pubbliche di McEliece sono enormi e così via), ma alcuni sarebbero ancora essere accettabile.

Lo studio della crittografia sotto l'ipotesi che possano essere costruiti efficienti computer quantistici è chiamato crittografia post-quantistica .

Personalmente non credo che un magro budget di 80 milioni di dollari porterebbe la NSA lontano. IBM ha lavorato su questo argomento per decenni e ha speso molto di più, ei loro migliori prototipi non sono eccezionali. È altamente plausibile che la NSA abbia speso qualche dollaro nell'idea di calcolo quantico; dopotutto, questo è il loro lavoro, e sarebbe uno scandalo se i soldi dei contribuenti non facessero non andare in quel tipo di ricerca. Ma c'è una differenza tra cercare e trovare ...

    
risposta data 03.01.2014 - 16:01
fonte
7

Il calcolo quantico avrà un impatto estremamente drammatico sulla crittografia asimmetrica, ma gli algoritmi simmetrici sono considerati sicuri con una dimensione della chiave sufficientemente grande (256 bit). Quindi, sì, dovremo reinventare x509 / SSL nel momento in cui il calcolo quantico decollerà davvero (che è un TODO abbastanza grande), ma ci saranno ampie aree di crittografia che rimarranno relativamente sicure.

link link

    
risposta data 03.01.2014 - 16:05
fonte
5

Quando i crittografi parlano di computer quantistico e crittografia post-quantica, in realtà parlano del potere di l'algoritmo di Shor in numeri di factoring, quindi i problemi difficili basati sul numero di factoring utilizzati per creare crittosistemi vengono interrotti dall'algoritmo di Shor (computer quantistico) in modo che RSA, DSA, ELGamal, Diffie-Hellman Key Exchabge, ECC siano vulnerabili al Quantum Computing!

Nella crittografia a chiave pubblica, tre schemi sono quantistici:

  1. Crittografia basata su reticolo come NTRUEncrypt; basata su reticoli
  2. crittografia basata su codice come il cryptosystem di McEliece, basato sulla teoria delle informazioni
  3. crittografia multivariata come equazioni di campi nascosti

e in crittografia simmetrica come AES, se scegli una chiave lunga, sei al sicuro contro computer quantistici e NSA!

per la lettura futura: link alla rivista Quanta e libro di crittografia post-quantum

    
risposta data 07.03.2016 - 19:26
fonte
0

1-time pad rimane la crittografia più strong, non craccabile (se usata correttamente). Ovviamente, devi scambiare il pad faccia a faccia, ma credo che il 95% delle persone che richiedono questo livello di sicurezza si incontreranno prima di impostare comunicazioni sicure.

Basta specificare quale chiave a 256 bit utilizzare per un particolare messaggio funziona perfettamente e viene utilizzata dai servizi di sicurezza.

    
risposta data 14.03.2015 - 17:08
fonte
-3

Per una maggiore protezione contro l'NSA, crittografare utilizzando la modalità di cifratura a blocchi di catena AES, quindi crittografare di nuovo il testo cifrato (il risultato della prima crittografia) e ripetere tutte le volte che puoi permetterti di ripetere. L'NSA probabilmente cercherebbe la ricerca di forza bruta per passare attraverso lo spazio di ricerca, e capirà che hanno decifrato il codice determinando l'entropia del risultato per ciascuna delle chiavi che testano. Sanno quando fermarsi quando vedono il testo significativo come risultato. Con la crittografia più volte, è più difficile per loro determinare quando hanno crackato un codice, perché se hanno provato la chiave giusta, allora vedrebbero il guazzabuglio come il risultato, quasi indistinguibile dai risultati delle chiavi errate. Man mano che aumenti il numero di re-encryption, la difficoltà di crackare i contenuti di crittografia diventa più difficile. L'NSA perderà la sua mente cercando di capire quando hanno decifrato il codice.

Software come TrueCrypt possono eseguire più crittografie per te. Ma attenzione alla crittografia ingenua che funziona semplicemente in modalità "Electronic Code Book" (ECB). Avrai bisogno della crittografia che viene eseguita in una delle modalità più sofisticate come "Chain Block Cipher" o "Cipher Feedback". Sì, un computer quantistico renderebbe più semplice per l'NSA passare attraverso le possibili chiavi da provare. Tuttavia, crittografando più volte (con una chiave DIFFERENT per ogni ripetizione della crittografia, ovviamente), si rende difficile la ricerca dello spazio per un fattore della lunghezza della chiave. Speriamo che questo ti aiuti a tenere la tua roba fuori dalla portata della NSA.

    
risposta data 04.01.2014 - 04:38
fonte

Leggi altre domande sui tag