Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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);
    }
share|improve this question
2  
Hint: consider the size of "e" compared to the size of "d". –  Thomas 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. –  David Schwartz Feb 18 '13 at 4:07
3  
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
    
Encryption and signature verification are much faster than decryption and signing when using RSA. The public exponent e is small (typically 17 bits) and the private exponent d (~1024 bits) is large leading to a cheaper calculation for $m^e$. –  CodesInChaos Sep 24 '13 at 7:15
show 1 more comment

3 Answers 3

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.

share|improve this answer
add comment

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.

share|improve this answer
    
thank you Mr Thomas Pornin then my resul normal?? –  Gold Rose 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 –  owlstead 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/… –  Gold Rose Sep 24 '13 at 18:56
    
I waiting to any response!! –  Gold Rose 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 at 8:47
add comment

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 above has to do a lot more work raising to $d$ then to $e$.

share|improve this answer
add comment

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.