Ho svolto ricerche sugli svantaggi dell'utilizzo di RSA per la crittografia e uno che ho riscontrato ripetutamente è che la decrittazione RSA è lenta, ma non ho visto una spiegazione sul perché. Qualcuno può spiegare perché questo sarebbe?
La decifratura RSA è lenta rispetto alla crittografia poiché l'esponente privato è necessariamente grande, mentre (con l'uso corretto di RSA) non c'è motivo per cui l'esponente pubblico non possa essere scelto come piccolo come 65537 (o anche 3).
La crittografia RSA genera il testo cifrato di m^e mod N , dove (N, e) la tua chiave pubblica e la decrittografia funzionano tramite c^d mod N dove (N, d) è la chiave privata che viene calcolata in modo efficiente quando conosci p e q i numeri primi grandi.
Ecco un esempio di una chiave che ho appena generato. Per semplificare l'esempio, ho usato solo RSA a 256 bit (debole), in realtà dovresti usare almeno RSA a 2048 bit in questi giorni, nel qual caso p, q, N e d avranno ciascuno otto volte il numero di cifre. (Nel frattempo e resterà 65537 anche con RSA a 2048 bit.)
p = 255972651020913583852708738755558492779
q = 315961372360286283221530569994994089667
N = 80877470103268491690225776687889776985485516372419877405296906209811698014593
e = 65537
d = 62101042930507606982857645825838676738862341745400679479964616076341592694761
Puoi verificare che le condizioni RSA siano soddisfatte, p e q sono primi, N == p*q , e e*d % ((p-1)*(q-1)) == 1 (quest'ultima condizione è ciò che consente alla decrittografia RSA di funzionare tramite teorema di Eulero ). Puoi anche verificare che la crittografia funzioni - per un messaggio m = 12345678901234567890, quindi c = m^e mod N è c = 37526865766319703630750491158429044860161927049301804846356525193422406944367 e quindi c^d mod N sarà 12345678901234567890 (nessun collegamento wolframalpha - input troppo lungo per la versione gratuita). Ecco un quaderno ipython che mostra tutti i passaggi - nota in python pow(x, y, N) è la sintassi per x^y mod N .
Da questo risulta abbastanza ovvio che il tempo per calcolare m^e mod N sarà un calcolo molto più veloce di c^d mod N . Per la crittografia, l'esponenziazione di 65537 mediante squadratura ripetuta richiede la quadratura e il modulo 16 volte con una moltiplicazione aggiuntiva come m 65537 = m * m 2 16 (i suoi 16 quadrati come x 2 n = (x 2 ) 2 n-1 ). Per la decrittografia con RSA-256, l'esponenziazione di d richiederà la squadratura 256 volte e circa 128 (il numero di 1 in d in binario escludendo il primo 1) altre moltiplicazioni con RSA-256 e per ogni quadratura è necessario calcolare anche il modulo di N. Va notato che queste moltiplicazione modulo di grandi numeri non è un'operazione a tempo costante ma dipende dalla lunghezza dei bit dei numeri. Nota se hai scelto d di essere piccolo come e , la tua chiave privata potrebbe essere forzata bruta (crittografare un messaggio usando la chiave pubblica, e quindi provare ogni piccolo valore di d fino a quando decodifica correttamente). Anche se d è troppo grande per la forza bruta in questo modo banale, attacca il piccolo d (che significa d < N 1/4 / 3), poi ci sono più attacchi sofisticati che permetteranno a un utente malintenzionato di scoprire l'esponente privato.
(E sì, ho ignorato alcuni fatti RSA del mondo reale. Puoi usare il teorema del remainder cinese usando p e q come parte della chiave privata per accelerare la decrittografia. Inoltre, non usi RSA sul messaggio attuale, è necessario utilizzare il padding sicuro (OAEP) e quindi crittografare solo una chiave simmetrica casuale che viene poi utilizzata per crittografare il messaggio effettivo).
RSA comporta il calcolo con numeri molto grandi, in particolare la decifrazione sta calcolando un grande numero con una grande potenza. Ci sono alcune scorciatoie se conosci i fattori della chiave privata, ma è ancora lento.
I crittosistemi classici (ad esempio, simmetrici) funzionano principalmente ripetendo operazioni bit molto semplici (che possono essere ben bilanciate) molto, ma alla fine fanno molto meno lavoro.
Il modo consigliato di usare RSA è selezionare una chiave simmetrica a caso, cifrare quella con RSA, cifrare il messaggio con quella chiave casuale, collegarla cifrata e inviare sia la loro strada allegra. Chiaramente è quindi fondamentale disporre di un generatore di numeri casuali crittograficamente strong ...
Per prima cosa, devi pensare a cosa significa "decifrare RSA è lento". Lento rispetto a cosa? A quanto pare, la crittografia RSA è lenta, nel senso che riteniamo utile andare alla ricerca di alternative.
La decifrazione RSA è più lenta rispetto al non utilizzare alcuna crittografia. Ovviamente, il vantaggio dell'uso della crittografia è che puoi mantenere riservati i dati, quindi a volte la lentezza è un prezzo che vale la pena pagare.
La decifrazione RSA è più lenta della decodifica AES. Più in generale, per un livello di sicurezza equivalente (vale a dire quanto sarebbe difficile interrompere la crittografia con la forza bruta), la crittografia asimmetrica è significativamente più lenta della crittografia simmetrica. Per quanto ne so, non c'è una ragione matematica fondamentale per cui sia così, è solo che gli algoritmi conosciuti hanno questa proprietà. La crittografia asimmetrica può essere utilizzata simmetricamente (condividendo le chiavi private), quindi è o che la crittografia asimmetrica è veloce quanto la crittografia simmetrica.
Poiché la crittografia e la decodifica RSA sono lente, viene solitamente utilizzata come parte di sistemi di crittografia ibridi . Per crittografare un messaggio, anziché utilizzare la coppia di chiavi RSA per crittografarlo e decrittografarlo, generiamo una chiave simmetrica univoca (in genere una chiave AES), crittografiamo la chiave simmetrica con RSA e crittografiamo il messaggio con AES. In questo modo RSA viene utilizzato solo per crittografare un singolo blocco di alcune centinaia di bit.
La crittografia RSA è in genere più lenta di schemi di crittografia basati su curve ellittiche , a parità di livello di sicurezza (che richiede chiavi più piccole con ECC). ECC è più recente di RSA e sta lentamente ottenendo più adozione.
Un'osservazione a margine: la decrittazione RSA è più lenta della crittografia, come tipicamente utilizzata. La costosa operazione di decrittazione RSA è un esponenziazione: C = P ^ d (mod n). L'operazione di crittografia corrispondente è molto simile - P = C ^ e (mod n). La differenza di velocità deriva dal fatto che possiamo, e facciamo, scegliere l'esponente pubblico e per rendere il calcolo più veloce. L'esponenziazione richiede una moltiplicazione per ogni bit dell'esponente e un'altra moltiplicazione per ogni bit impostato su 1. L'esponente privato d deve essere casuale in modo che non possa essere indovinato, mentre e può essere piccolo (3 e 2 16 +1 sono le scelte più comuni).
Leggi altre domande sui tag cryptography rsa asymmetric