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
add comment

2 Answers

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

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.