Encryption decryption time

Question

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?

Answer 1

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'.

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.

Answer 2

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 n², while effort for decryption is proportional to n³. 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.