Perché la ECC è più vulnerabile della RSA in un mondo post-quantico?

14

Perdonami se questo dovrebbe essere nel sub cripto, ma a volte le risposte sono molto matematiche e preferirei avere una risposta un po 'più leggera in matematica.

Stavo guardando il pannello di Cryptographer da RSA 2013 e a circa 33 minuti in cui hanno menzionato che ECC è più vulnerabile di RSA in un mondo post-quantico. Qualcuno può spiegare perché l'ECC è più vulnerabile alla RSA in un mondo post-quantico?

    
posta JZeolla 22.03.2013 - 18:09
fonte

2 risposte

16

La sfida attuale nella costruzione di un computer quantistico è di aggregare abbastanza "qubit", impigliati insieme a un livello quantico per abbastanza lungo. Per interrompere un modulo RSA a 1024 bit, è necessario un computer quantistico con 1024 qubit. Per rompere una curva ellittica a 160 bit, che ha una "forza simile" (rispetto ai computer classici), hai bisogno di qualcosa come 320 qubit. Non è che le curve ellittiche siano intrinsecamente più deboli; al contrario, sembrano ancora un po 'più forti di RSA per la stessa "dimensione". Piuttosto, il rapporto di forza per una data dimensione non è lo stesso quando si considerano computer classici contro computer quantistici.

    
risposta data 22.03.2013 - 20:01
fonte
14

Il fattore limitante per un utente malintenzionato che utilizza un computer quantistico è il numero di qubit che possono rimanere invischiati abbastanza a lungo da eseguire un calcolo. I qubit necessari per decifrare le chiavi RSA sono stimati per essere 2 • bit mentre ECC è approssimativamente 6 • bit, ma le chiavi RSA sono generalmente molto più lunghe e quindi finiscono per prendere più qubit; circa 3 volte sulla fascia bassa (2048 vs 224) e 10x sulla fascia alta (4096 vs 384) vedi nota .

Ecco una tabella strongmente semplificata che confronta il rough numero di qubit richiesto per decifrare le lunghezze delle chiavi comuni:

|           RSA       |           ECC       |
| Key Length | qubits | Key Length | qubits |
|------------|--------|------------|--------|
| 1024       | 2048   | 163        | 1000   |
| 2048       | 4096   | 224        | 1300   |
| 3072       | 6144   | 256        | 1500   |
| 4096       | 8192   | 383        | 2300   |
| 15360      | 30720  | 512        | 3000   |

Negli ultimi 20 anni, non abbiamo capito come costruire un computer quantistico a tutti gli effetti con più di una manciata di qubit. Quindi per confrontare quanto tempo ci vorrà un computer quantico per decifrare una chiave RSA rispetto ad una chiave ECC "equivalente", dobbiamo sostanzialmente supporre che un costruttore possa determinare la decoerenza in un modo che può essere scalato. Quindi diventa una questione di quanto velocemente si verificherà il ridimensionamento.

Assumendo tassi lineari di crescita (con 2048 RSA vs 224 ECC bassi alla fine e 4096 RS vs 384 ECC alla fascia alta) RSA ottiene un bonus di ~ 5-10 anni a 500 qubits / anno, ~ 3-5 anni a 1 K qubits / anno e ~ 1,5-3 anni a 2 K qubit / anno.

Se assumiamo tassi esponenziali di crescita, una volta che siamo in grado di rompere una chiave ECC a 224 bit (la chiave ECC più debole comune) siamo a una generazione dal cracking di una chiave RSA a 4096 bit (la più comune chiave RSA comune). Al ritmo della legge di Moore (~ 2 anni) RSA ottiene un bonus di 2 anni. Sebbene il computer quantistico adiabatico di DWAVE non sia utile per questi tipi di problemi, sono stati raddoppiando il numero di qubit all'incirca ogni 4 anni .

Quindi la differenza è in realtà relativamente piccola: 2-5 anni + tempo per l'innovazione produttiva.

Nota 4096 bit RSA e 383 ECC non sono direttamente confrontabili in termini di forza della chiave simmetrica. La chiave RSA 4096 bit equivale approssimativamente a una chiave simmetrica a 142 bit mentre una chiave ECC a 383 bit equivale a una chiave simmetrica 192. Li confronto direttamente sopra perché sono le dimensioni di chiave più comunemente supportate.

    
risposta data 14.08.2015 - 23:53
fonte

Leggi altre domande sui tag