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 try compute execution time for encrypt and decrypt data has 1024 bit = 128 byte in RSA-crt algorithm. I need this results. But I believe this result wrong. because big diffrent between execution time for encrypt and execution time for decrypt. My code is following

>  public static void main(String[] args) {
> System.out.println("-----------CRT RSA--------");
> n=1024;//key size
>  CRTRSA crtrsa = new CRTRSA();
 int num=10; 
for (int i = 0; i < 200; i++)
 {   crtrsa.keygen(); }
 for (;;) {
>     long begin = System.currentTimeMillis();
>     for (int i = 0; i < num; i ++) 
{   crtrsa.keygen();
>      }
>     long end = System.currentTimeMillis();
>     long time = end - begin;
>     if (time >= 2000) {
>         System.out.printf("average Key generation takes: %.2f ms",
>             (double)time / num);
>         System.out.println();
>         break;
>     }
>     num *= 2; } //encrypt
> 
> num=10; for (int i = 0; i < 200; i ++) {   crtrsa.encrypt(); } for
> (;;) {
>     long begin = System.currentTimeMillis();
>     for (int i = 0; i < num; i ++) {
>     crtrsa.encrypt();
>      }
>     long end = System.currentTimeMillis();
>     long time = end - begin;
>     if (time >= 2000) {
>         System.out.printf("average Encryption takes: %.2f ms",
>             (double)time / num);
>         System.out.println();
>         break;
>     }
>     num *= 2; }
 //Decrypt 
      num =10; for (int i = 0; i < 200; i ++) {   crtrsa.decrypt(); } for (;;) {
>     long begin = System.currentTimeMillis();
>     for (int i = 0; i < num; i ++) {
>       crtrsa.decrypt();
>     }
>     long end = System.currentTimeMillis();
>     long time = end - begin;
>     if (time >= 2000) {
>         System.out.printf("average Decryption takes: %.2f ms",
>             (double)time / num);
>         System.out.println();
>         break;
>     }
>     num *= 2; } }
 private void keygen()
 { p = BigInteger.probablePrime(n/2, random);
   q = BigInteger.probablePrime(n/2, random);
> 
> N=p.multiply(q);
> 
> phi_n=(p.subtract(one)).multiply(q.subtract(one));
  e=new
> BigInteger("65537");
 while(e.gcd(phi_n).intValue()!=1)
> e=BigInteger.probablePrime(32, random);       
>          d=e.modInverse(phi_n);
>  dp=d.mod(p.subtract(one)); 
dq=d.mod(q.subtract(one)); }
> 
> private void encrypt() 
{ M=new BigInteger(1024,random); C=
> M.modPow(e,N);
> }
> 
> private void decrypt() {
> Mp=C.modPow(dp, p);
 Mq=C.modPow(dq, q);
> 
> RM=(((Mp.multiply(q).multiply(q.modInverse(p))).add(Mq.multiply(p).multiply(p.modInverse(q)))).mod(N));
> } }

On my laptop when run program it give me the follow average Key generation takes: 58.60 ms average Encryption takes: 0.09 ms average Decryption takes: 1.89 ms I note big difference between 0.09 ms and 1.89 ms I want tell me where my wrong or any link about this issue.

share|improve this question
    
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
    
possible duplicate of Why is RSA encryption significantly faster than decryption? –  CodesInChaos Sep 24 '13 at 7:18
    
I want know the natural ratio between execution time for encrypt and execution time for decrypt. any link for this –  Gold Rose Sep 24 '13 at 10:28
add comment

1 Answer

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
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.