# Why is RSA encryption significantly faster than decryption?

I am designing an implementation of RSA . I recorded computation times in Java by using System.currentTimeMillis(). It returned an encryption time of 0.05 ms and decryption time of 0.55 ms, or a ratio of 1:11.

This seems like a large difference. Is it supposed to be this way?

//here my key has 256 bits
for (;;) {
long begin = System.currentTimeMillis();

for (int i = 0; i < num; i++) {

decrypt();
}

long end = System.currentTimeMillis();

long time = end - begin;

if (time >= 10000) {
System.out.printf("Average Encryption takes: %.2f ms\n",
(double) time / num);
break;
}

num *= 2;
}

p = BigInteger.probablePrime(128, random);
q = BigInteger.probablePrime(128, random);
N=(p.subtract(one)).multiply(q.subtract(one));
e=BigInteger.probablePrime(32, random);
d=e.modInverse(N);
private void encrypt()
{

C= M.modPow(e,N);

}

private void decrypt()
{
RM = C.modPow(d, N);
}

• Hint: consider the size of "e" compared to the size of "d". Feb 18 '13 at 1:41
• ok Thomas. I modify my code
– Mhsz
Feb 18 '13 at 1:48
• I just benchmarked OpenSSL and the ratio was around 14 to 1. Feb 18 '13 at 4:07
• The question as is does not show enough research. The code as given does not compile. It does not seem to implement RSA, for it computes $N$ as $N=(p-1)\cdot(q-1)$ instead of $N=p\cdot q$. Also it does not check that $e$ is coprime with $p-1$ and $q-1$. Also, 128 bit primes are too short for RSA, and that invalidates performance measurements to some degree. No effort is made to speed-up the code by using the CRT. As to the question, examine how modPow works, or better code your own.
– fgrieu
Feb 18 '13 at 6:53
• Even though this question is old, just wanted to say that System.currentTimeMillis should not be used for time diffs as it's not monotonic. Apr 18 '18 at 18:26

Yes. RSA encryption is faster than RSA decryption, assuming you choose the public exponent properly (e.g., you use $e=3$).

This is because raising something to the 3rd power (which is what you do during encryption) is much faster than raising something to the $d$th power, where $d$ is a 2048-bit number (as you do during decryption, assuming a 2048-bit modulus).

The Chinese Remainder Theorem can be used to speed up decryption, but only by a factor of up to $4\times$, which is not large enough to change the bottom-line conclusion.

You can test this for yourself by running openssl speed rsa2048 to test the speed of encryption and decryption using 2048-bit RSA. On my machine, encryption is roughly $35\times$ faster than decryption. Don't take this number too seriously -- the exact speedup factor will depend upon a number of factors -- but it demonstrates the bottom line, which is that in RSA, encryption is faster than decryption.

• $d$ is a number that is not necessarily 2048 bit of course. It may well start with a couple of zeros. Aug 25 '15 at 15:01

Performance issues are subtle, and depend a lot on implementation details, but the following can still be said.

RSA encryption and RSA decryption both use modular exponentiation. There are many algorithms for that, but for typical RSA key sizes, Montgomery multiplication in a square-and-multiply algorithm are typical (the "multiply" steps can be further reduced with window-based optimizations). As a rough approximation, time to compute a modular exponentiation with a modulus of $n$ bits and an exponent of $k$ bits will be proportional to $k·n^2$.

The CRT replace one modular exponentiation with two, but these two exponentiations use half-size modulus and exponents, so each of them is about eight times faster than the non-CRT exponentiation. Thus, CRT speeds up RSA decryption by a factor of about 4. CRT requires knowledge of modulus factorization, so it cannot be applied to encryption, only to decryption.

On the other hand, RSA encryption uses the public exponent, which can be extremely small. A traditional RSA public exponent is 65537, thus 17 bits long. Exponentiation to the power 65537, a 17-bit integer, should be about 60 times faster than exponentiation to a 1024-bit power $d$ (the private exponent). Even with the CTR speed-up, RSA encryption should still be about 15 times faster than RSA decryption.

In practice there are some extra overhead costs in both encryption and decryption (conversions to and from Montgomery representations, CRT reassembly, masking with a random value to protect against timing attacks...) so the "15x" figure can vary quite a lot. Things will also vary depending on the modulus size (you would still use 65537 as public exponent with a 2048-bit modulus, for instance). A 15x ratio is still typical.

• thank you Mr Thomas Pornin then my resul normal?? Sep 24 '13 at 11:38
• @GoldRose yes, it looks normal, for more balanced times you could take a look at Elliptic Curve encryption, but beware that ECC requires a lot of knowledge compared to RSA Sep 24 '13 at 17:18
• ok thank you for all. I have requesting when read some papers talk about RSA algorithm found some comparative I don't understand the comparative between encrypt and decrypt time. in comparative the encryption time take time more than decryption. How that. I know the inversion true. any somebody illustrating about this issue. I very need illustrating this problem. The compare exist into this paper link ijarcsse.com/docs/papers/July2012/Volume_2_issue_7/… Sep 24 '13 at 18:56
• I waiting to any response!! Sep 25 '13 at 17:59
• Well, that paper is pretty terrible overall (Comparing apples and oranges, and one of their 3 ciphers is DES). They did not state how they got those numbers. I suspect, they chose not a small RSA exponent but a random one, and then their result is probably just due to statistical deviation. Thomas answer is correct, your result is normal, and there is no fixed rate between RSA encryption and decryption, it all depends on the actual values of $e$ and $d$ (and their length).
– tylo
May 21 '14 at 8:47

This is a fairly complex question for a number of reasons. First, you can use a small $e$ and larger $d$ to make encryption fast, as well as signature verification. However, as the owner of the private key has the factorization of $pq$, they can use the Chinese Remainder Theorem to accelerate computations.

As a result it is a bit difficult to say for certain which is faster without more information about key sizes and algorithms. However, your code in the question has to do a lot more work raising the message to $d$ compared to raising it to $e$.

The reason of encryption is faster than decryption is that public key ($e$) for encryption can be chosen manually, while the secret key ($d$) is calculated from the public key and other parameters. Therefore an implementer of the RSA would like to choose small value of public key for fast encryption, since smaller the key is, faster encryption/decryption can be achieved. However, a large secrete key is favorable for security.

Print your public key ($e$) and secret key ($d$), and you will see the latter is much bigger.

• Could you indicate what your answer adds to D.W.'s explanation? Note that (small) changes to the explanation can be performed using edits of the existing answer. Of course, you should be relatively sure of your change to edit questions from one of the top 8 players. Aug 25 '15 at 15:04
• @MaartenBodewes Thanks for your comments. Maybe I explain why public key $e$ is normally much smaller than the secrete key $d$, which is the reason why RSA encryption is faster than RSA decryption. Aug 26 '15 at 3:09