6

I've been researching the disadvantages of using RSA for encryption, and one I've found repeatedly is that RSA decryption is slow, but I haven't seen an explanation as to why this is. Can anyone explain why this would be?

  • 2
    Are you asking why RSA is slow or why breaking RSA is slow? (the title and the body of the question seems to be asking for different things) – Alessandro May 3 '14 at 14:59
  • 1
    Speed cannot be the sole argument - cleartext decrpytion is unbeatably fast. – Hagen von Eitzen May 3 '14 at 15:00
  • its meant to ask why is RSA slow? – Harry May 3 '14 at 15:03
  • 1
    Because math is hard. – tylerl May 8 '14 at 5:11
6

RSA decryption is slow compared to encryption as d the private exponent is necessarily large, while (with proper use of RSA) there's no reason the public exponent can't be chosen to be small like 65537 (or even 3).

RSA encryption generates the ciphertext by m^e mod N, where (N, e) are your public key and decryption works via c^d mod N where (N, d) are the private key which is calculated efficiently when you know p and q the large primes.

Here's an example of a key I just generated. To keep the example simpler, I only used 256-bit RSA (weak), in reality you should use at least 2048-bit RSA these days, in which case have p, q, N, and d will each have eight times the number of digits. (Meanwhile e will stay 65537 even with 2048-bit RSA.)

p = 255972651020913583852708738755558492779
q = 315961372360286283221530569994994089667
N = 80877470103268491690225776687889776985485516372419877405296906209811698014593
e = 65537
d = 62101042930507606982857645825838676738862341745400679479964616076341592694761

You can check that the RSA conditions are satisfied, p and q are prime, N == p*q, and e*d % ((p-1)*(q-1)) == 1 (this last condition is what allows RSA decryption to work via Euler's theorem ). You can also test that encryption works -- for a message m = 12345678901234567890, then c = m^e mod N is c = 37526865766319703630750491158429044860161927049301804846356525193422406944367 and then c^d mod N will be 12345678901234567890 (no wolframalpha link -- input too long for free version). Here's a ipython notebook demonstrating all the steps -- note in python pow(x, y, N) is the syntax for x^y mod N.

From this it appears quite obvious that the time to calculate m^e mod N will be a much quicker calculation than c^d mod N. For encryption, exponentiation by 65537 by repeated squaring will require squaring and taking the modulus 16 times with one additional multiplication as m65537 = m * m216 (its 16 squarings as x2n = (x2)2n-1). For decryption with RSA-256, exponentiation by d will require squaring 256 times and about 128 (the number of 1s in d in binary excluding the first 1) other multiplications with RSA-256 and for each squaring you need to also calculate the modulus of N. It should be noted that these modulo multiplications of large numbers is not a constant time operation but depends on the bit-length of the numbers. Note if you chose d to be small like e then your private key could be brute forced (encrypt a message using the public key, and then try every small value of d until it decrypts properly). Even if d is too large to brute force in this trivial manner, attacks on small d (meaning d < N1/4/3), then there are more sophisticated attacks that will allow an attacker to discover the private exponent.

(And yes, I ignored some real world RSA facts. You can use Chinese remainder theorem by using p and q as part of the private key to speed up decryption. Also, you do not use RSA on the actual message, you need to use secure padding (OAEP) and then only encrypt a random symmetric key which is then used to encrypt the actual message).

2

RSA involves doing computation with very large numbers, in particular deciphering is computing a large number to a huge power. There are some shortcuts if you know the private key's factors, but it still is slow.

Classical (i.e., symmetric) cryptosystems work mostly by repeating very simple bit operations (that can be parallelized nicely) a lot, but in the end doing much less work.

The recommended way to use RSA is to select a symmetric key at random, cypher that with RSA, cypher the message with that random key, attach it enciphered, and send both their merry way. Clearly it is then critical to have a cryptographically strong random number generator...

2

First, you need to think about what “RSA decryption is slow” means. Slow compared to what? As it turns out, RSA encryption is slow in the sense that we find it worthwhile to go looking for alternatives.

RSA decryption is slower than not using any encryption. Obviously, the advantage of using encryption is that you can keep data confidential, so sometimes the slowness is a price worth paying.

RSA decryption is slower than AES decryption. More generally, for an equivalent level of security (i.e. how hard it would be to break encryption by brute force), asymmetric cryptography is significantly slower than symmetric cryptography. As far as I know, there is no fundamental mathematical reason why this is so, it's just that the known algorithms have this property. Asymmetric cryptography can be used symmetrically (by sharing private keys), so it's either that or asymmetric cryptography is as fast as symmetric cryptography.

Because RSA encryption and decryption is slow, it is usually used as part of hybrid cryptosystems. To encrypt a message, rather than use the RSA key pair to encrypt and decrypt it, we generate a unique symmetric key (typically an AES key), we encrypt the symmetric key with RSA, and we encrypt the message with AES. This way RSA is only used to encrypt a single block of a few hundred bits.

RSA encryption is typically slower than encryption schemes based on elliptic curves, for an equal security level (which requires smaller keys with ECC). ECC is newer than RSA and is slowly getting more adoption.

A side remark: RSA decryption is slower than encryption, as typically used. The expensive operation of RSA decryption is an exponentiation: C = P^d (mod n). The corresponding encryption operation is very similar — P = C^e (mod n). The speed difference comes from the fact that we can, and do, choose the public exponent e to make the computation faster. Exponentiation requires one multiplication for each bit of the exponent, and another multiplication for each bit that is set to 1. The private exponent d has to be random so that it cannot be guessed, while e can be small (3 and 216+1 are the most common choices).

  • @drjimbob Ouch. Thanks. Did I get them all? (Feel free to edit in such cases, by the way.) – Gilles 'SO- stop being evil' May 8 '14 at 6:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy