5
$\begingroup$

I was wondering what is the performance bottleneck in RSA algorithm? Is it the size of message, calculating the modular inverse, exponentiation?

Say I have a fixed value of n to encrypt and decrypt a message would l get a better performace with m being small or large?

Improve this question
$\endgroup$
2
  • $\begingroup$ You shouldn't encrypt the message itself with RSA (at least for long messages). Create a random AES key,encrypt message with that key, encrypt AES key with RSA. That way you only pay the much smaller AES cost for the message, and only a single costly RSA encryption. $\endgroup$
    – CodesInChaos
    Commented Dec 3, 2013 at 18:26
  • $\begingroup$ I am not doing an implementation. Just studying for my exam , while reviewing the material this question came to my mind :) thanks anyway $\endgroup$
    – Ajit
    Commented Dec 3, 2013 at 18:33

2 Answers 2

Reset to default
7
$\begingroup$

In RSA encryption as practiced (that is, to encipher a message which is a short symmetric key), the message size after padding is fixed and equal to the modulus size. Thus the size of the message has no impact on performance.

Calculating a modular inverse is performed only during key generation, that is seldom. Also, it has low cost compared to generating the primes and testing their primality.

The performance bottleneck (key generation aside) is typically modular exponentiation (or the few ones, when using the CRT for decryption). In typical implementations, exponentiation has cost $O(n^2)$ for encryption and $O(n^3)$ for decryption, where $n$ is the bit size of the public modulus. This can be lowered slightly using Karatsuba multiplication, or even more advanced techniques.

Update: there is simply no universally accepted way to encipher a message longer than the modulus size directly with RSA, thus asking "Theoretically, would the length of the message affect the performance?" is not well defined.

If we do a single RSA encryption, we have to make $n$ proportional to the message size $m$, thus cost increases as $O(m^2)$ for encryption and $O(m^3)$ for decryption, for typical implementations.

If we make $n$ constant and only use RSA, we must truncate the message into chunks separately RSA-enciphered, and for practical message size cost grows as $O(m)$ for both encryption an decryption.

Again the accepted/right practice is hybrid encryption, and there time spent doing RSA is independent of message size, with the overall cost $O(m)$ for symmetric encryption and decryption.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @Ajit If you were to somehow encrypt a long message with RSA, the performance would decrease linearly with the length of the message. Since RSA is pretty expensive, that'd be rather slow (perhaps 100kB/s). But almost nobody does that (use hybrid encryption instead), and the common RSA standards don't specify how to do so. $\endgroup$
    – CodesInChaos
    Commented Dec 3, 2013 at 21:29
5
$\begingroup$

The performance bottleneck with RSA is the modular exponentiation operation.

On the other hand, if you are interested in public key encryption performance, perhaps RSA is not the correct tool. RSA is actually fairly fast during its encryption operation; however it is quite slow during the decryption. If you care about decryption performance, you may want to consider something like ECIES; that is much faster during decryption (and while it is slower during encryption, it is not that much slower).

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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