Tempo di decodifica della crittografia

10

Il tempo di crittografia / decrittografia dell'algoritmo rsa varia in modo significativo con una modifica della lunghezza della chiave? Ad esempio, c'è una differenza notevole nel tempo di crittografia / decrittografia tra 512 bit e 2048 bit?

    
posta user1157 23.01.2011 - 18:46
fonte

2 risposte

11

Con le normali implementazioni, raddoppiando la lunghezza della chiave RSA significa che la crittografia sarà quattro volte più lenta, e la decrittazione sarà otto volte più lenta. La crittografia RSA è molto più veloce della decodifica RSA (nel contesto delle firme RSA, la verifica è simile alla crittografia e la generazione è simile alla decrittografia). La teoria dice che per una chiave n -bit, lo sforzo computazionale per la crittografia è proporzionale a n 2 , mentre lo sforzo per la decrittazione è proporzionale a < em> n 3 . In pratica, c'è un po 'di più in RSA rispetto alla semplice esponenziazione modulare, e il sovraccarico non scala nello stesso modo quadratico / cubico, quindi, per un'implementazione specifica, non otterrete esattamente un fattore 8x.

Inoltre, si noti che la crittografia veloce (e il suo comportamento quadratico) si basa sull'uso di un breve esponente pubblico. Questo è il modo in cui viene comunemente usato RSA; è possibile avere una chiave pubblica RSA con un lungo esponente pubblico, che renderà la crittografia lenta quanto la decrittazione. Un lungo esponente pubblico non sembra migliorare la sicurezza, quindi gli esponenti pubblici brevi sono la regola. Alcune implementazioni RSA diffuse non supportano comunque esponenti pubblici lunghi.

OpenSSL viene fornito con uno strumento da riga di comando che può eseguire alcuni benchmark. Prova a eseguire questo:

openssl speed rsa1024 rsa2048

Sul mio PC, questo ha il seguente risultato:

                  sign    verify    sign/s verify/s
rsa 1024 bits 0.000646s 0.000035s   1549.1  28408.6
rsa 2048 bits 0.004097s 0.000120s    244.1   8331.1

così otteniamo i fattori 6.3x e 3.4x per la decodifica e la crittografia, rispettivamente, quando si raddoppia la dimensione della chiave da 1024 a 2048 bit.

    
risposta data 07.02.2011 - 12:19
fonte
7

C'è un buon articolo su Javamex che discute lunghezza delle chiavi RSA . La regola che hanno ricavato dalla loro analisi è che "Con ogni raddoppio della lunghezza della chiave RSA, la decrittografia è 6-7 volte più lenta".

LeggendoattornoadessosembracheconRSAladecifraturasiadisolitopiùlentadellacrittografia,c'èunaspiegazionealragionamento qui . Ho fatto alcuni test rapidi sulla mia macchina, raddoppiando la lunghezza della chiave che sembra raddoppiare il tempo di crittografia.

    
risposta data 24.01.2011 - 10:46
fonte

Leggi altre domande sui tag