Perché il processo di decrittografia RSA richiede più tempo del processo di crittografia?

Question

Ho qualche idea che sia dovuto a un calcolo complesso, ma voglio sapere cosa succede esattamente che richiede molto tempo rispetto al processo di crittografia corrispondente. Qualsiasi collegamento a pagina Web o carta sarebbe di grande aiuto.

Grazie

Grazie per le risposte, un dubbio, che cosa circa la firma e la verifica? Questa differenza di orario sarà presente anche per la firma e la verifica? Ex. La firma richiede più tempo della verifica?

Answer 1

In teoria, non è così deve essere. Gli algoritmi di crittografia e decrittografia sono essenzialmente identici. Dato:

d = decryption key 
e = encryption key 
n = modulus (product of primes) 
c = encrypted code group 
m = plaintext code group 

Poi:

1. crittografia c _i = m _i^e (mod n)
2. decrittografia m _i = c _i^d (mod n)

L'algoritmo normale per il passaggio a una potenza è iterativo, quindi il tempo impiegato dipende dalla dimensione dell'esponente. Nella maggior parte dei casi, la coppia funziona con la chiave di decodifica essendo (in genere considerevolmente) più grande della chiave di crittografia.

E 'possibile invertire questo però. Solo per un esempio di giocattolo, considerano:

p=17 
q=23 
n=391 

Ecco un elenco di alcuni coppie di chiavi di cifratura/decifratura validi per questa particolare coppia di numeri primi:

e = 17, d = 145 
e = 19, d = 315 
e = 21, d = 285 
e = 23, d = 199 
e = 25, d = 169 
e = 27, d = 339 
e = 29, d = 85 
e = 31, d = 159 
e = 35, d = 171 
e = 37, d = 333 
e = 39, d = 343 
e = 41, d = 249 
e = 43, d = 131 
e = 45, d = 133 
e = 47, d = 15 
e = 49, d = 273 
e = 51, d = 283 
e = 53, d = 93 
e = 57, d = 105 
e = 59, d = 179 

Di questi 20 coppie di chiavi solo uno, ha una chiave di decodifica più piccola della chiave di crittografia. Negli altri casi, la chiave di decrittografia varia da poco meno del doppio a quasi 17 volte di più.Naturalmente, quando il modulo è piccolo come questo, è facile e veloce generare un sacco di coppie di chiavi, quindi trovare una piccola chiave di decifrazione sarebbe abbastanza facile - con una vera chiave RSA, tuttavia, non è così banale, e generalmente accettiamo solo la prima coppia che troviamo. Come puoi vedere dall'elenco sopra, in questo caso, è molto probabile che tu abbia una chiave di decrittografia notevolmente più grande della tua chiave di crittografia, e quindi la decrittografia finirà più lentamente della crittografia. Quando lavoriamo con numeri di ~ 100 cifre, dovremmo essere abbastanza pazienti a trovare una coppia per la quale la decrittografia sarebbe stata (anche vicino) veloce come la crittografia.

Answer 2

Quanto più a lungo? Hai qualche dettaglio esatto?

Qualsiasi modo, ha senso che la decrittografia è complicata più di crittografia, in quanto la crittografia non è in modo simmetrico, come 123 => ABC e abc> 123.

Per maggiori dettagli Suggerisco a partire here.
Per leggere come funziona la calcolatrice, questo articolo sembra molto buono. http://www.di-mgt.com.au/rsa_alg.html

Answer 3

In breve "moltiplicare = facile, fattore = difficile".

Date un'occhiata a (http://en.wikipedia.org/wiki/RSA#Encryption), che fa riferimento a ottimizzazioni a elevamento a potenza (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Further_applications)

La migliore risorsa che ho trovato è stata la seguente conferenza sulla crittografia da Princeton (http://www.cs.princeton.edu/courses/archive/spr05/cos126/lectures/22.pdf)

Answer 4

Il potere di crittografia viene in genere scelto come primo del modulo 2^n + 1 (17, 63357) che richiede un numero relativamente ridotto di operazioni di moltiplicazione. Il valore di decrittografia sarà un numero molto più grande di conseguenza, e quindi richiederà più lavoro da calcolare.

Answer 5

Ci sono due fattori coinvolti in questo:

Da un lato, l'esponente pubblico può essere scelto per essere un piccolo numero con due soli 1-bit (solitamente 3, 17 o 65537). Ciò significa che l'operazione di crittografia RSA può essere eseguita con poche squadrature e un'aggiunta. Questo non può essere annullato: se imponi che l'esponente privato sia un numero piccolo, la sicurezza del sistema è ovviamente interrotta.

D'altra parte, il titolare della chiave privata può memorizzare alcuni valori precalcolati derivati ​​dai numeri primi originali. Con quelli può usare il CRT algorithm per sostituire il modulo di esponenziazione singolo un numero di n bit con due esponentiazioni modulo un numero di n/2 bit. Questo è circa quattro volte più veloce del modo ingenuo.

Quindi per le coppie di chiavi RSA con esponenti pubblici casuali, le operazioni con le chiavi private possono effettivamente essere più veloci. Ma l'effetto di scegliere un piccolo esponente pubblico è molto più grande dell'effetto dell'algoritmo più veloce, quindi la crittografia è più veloce nella pratica.

Answer 6

chiamata di Let n, d e e il modulo RSA, esponente privato e esponente pubblico, rispettivamente. La velocità di decrittazione RSA è proporzionale a (log d) (log n) (cioè quadratico nella lunghezza del modulo e lineare nella lunghezza dell'esponente privato). Allo stesso modo, la velocità di crittografia RSA è proporzionale a (log e) (log n). Il detentore di chiavi private conosce anche la fattorizzazione di n, che può essere utilizzato per accelerare l'operazione della chiave privata di un fattore di circa 4 (con il Chinese Remainder Theorem). Per dettagli sugli algoritmi coinvolti, vedere Handbook of Applied Cryptography, in particolare il capitolo 14 ("Implementazione efficiente").

Per motivi di sicurezza, l'esponente privato (d) deve essere grande; è stato dimostrato che se è inferiore al 29% della lunghezza del modulo (n), la chiave privata può essere ricostruita. Non sappiamo quale sia la lunghezza minima per evitare tali punti deboli, quindi nella pratica d avrà circa la stessa lunghezza di n. Ciò significa che la decrittografia sarà circa cubica nella lunghezza di n.

Le stesse disposizioni non si applicano al esponente pubblico (e), che può essere piccolo come desiderato, purché rispetti le regole RSA (e deve essere relativamente privilegiata per r- 1 per tutti i fattori primi r di n). Quindi è consuetudine scegliere un piccolissimo e. È talmente abituale che esistono implementazioni ampiamente implementate che non può gestire grandi esponenti pubblici. Ad esempio, l'implementazione di RSA in CryptoAPI di Windows (quella utilizzata ad esempio da Internet Explorer quando connesso a un sito HTTPS con un certificato server RSA) non può elaborare una chiave pubblica RSA se e non si adatta a 32 bit. e = 3 è il migliore possibile, ma e = 65537 è tradizionale (è un errore storico, perché un esponente molto piccolo può indurre una debolezza percepita se RSA viene utilizzato senza il suo padding appropriato e standard, qualcosa che non dovrebbe mai essere fatto comunque). 65537 è un numero intero a 17 bit, mentre una lunghezza tipica per n e d sarà 1024 bit o più. Questo rende le operazioni a chiave pubblica (crittografia dei messaggi, verifica delle firme) molto più veloce delle operazioni a chiave privata (decodifica dei messaggi, generazione delle firme).

Answer 7

RSA Laboratories describes why abbastanza bene

Nelle applicazioni pratiche, è comune a scegliere un piccolo esponente pubblico per la chiave pubblica.

...

Con i tipici algoritmi di elevazione a potenza modulare usati per implementare l'algoritmo RSA, operazioni di chiave pubblica prendere O (k^2) fasi, operazioni chiave privata tiene O (k^3) passi

Answer 8

d e e sono moltiplicativamente numeri inversi modulo phi(n). Ciò significa che non importa stregone dei due che sceglierai per la crittografia, e stregone uno per la decrittazione. Devi solo scegliere una volta prima della crittografia. Se si desidera una decifrazione veloce, scegliere il numero più grande per la crittografia. È così semplice.