Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

Does the encryption / decryption time of rsa algorithm vary significantly with a change in key length? For example, is there a noticeable difference in encryption/decryption time between 512 bit and 2048 bit?

share|improve this question

2 Answers 2

There is a good article on Javamex discussing RSA key lengths. The rule they have come up with from their analysis is that 'With every doubling of the RSA key length, decryption is 6-7 times times slower'.

RSA decryption time by key length

Reading around it does seem that with RSA the decryption is usually slower than the encryption, there is an explanation to the reasoning here. I did some quick tests on my machine doubling the key length seems to about double the encryption time.

share|improve this answer

With usual implementations, doubling the RSA key length means that encryption will be four times slower, and decryption will be eight times slower. RSA encryption is much faster than RSA decryption (in the context of RSA signatures, verification is similar to encryption, and generation is similar to decryption). The theory says that for a n-bit key, computational effort for encryption is proportional to n2, while effort for decryption is proportional to n3. In practice, there is a little bit more to RSA than just the modular exponentiation, and the overhead does not scale in the same quadratic/cubic way, hence, for a specific implementation, you will not get exactly an 8x factor.

Also, note that the fast encryption (and its quadratic behaviour) relies on the use of a short public exponent. This is the way RSA is commonly used; it is possible to have a RSA public key with a long public exponent, which will make encryption as slow as decryption. A long public exponent does not seem to improve security, so short public exponents are the rule. Some widespread RSA implementations do not support long public exponents anyway.

OpenSSL comes with a command-line tool which can perform some benchmarks. Try running this:

openssl speed rsa1024 rsa2048

On my PC, this results in the following:

                  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

so we get factors 6.3x and 3.4x for decryption and encryption, respectively, when doubling key size from 1024 to 2048 bits.

share|improve this answer
    
Isn't Karatsuba the usual multiplication algorithm for RSA sized numbers? Since that algorithm scales like n^1.6 for encryption and n^2.6 for decryption, it'd fit the factors of 3 and 6 you observed. –  CodesInChaos Aug 8 at 8:31
    
Karatsuba is fine for multiplying integers, but here we are processing modular integers and the modular reduction does not benefit from the Karatsuba speed-up. Montgomery's multiplication is what is most common for RSA, and it is quadratic. –  Thomas Pornin Aug 8 at 11:48

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.