# encryption and decryption time for RSA-crt in java?

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);
>
> } }


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.

-
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 at 7:15
I want know the natural ratio between execution time for encrypt and execution time for decrypt. any link for this –  Gold Rose Sep 24 at 10:28

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?? –  Gold Rose Sep 24 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 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 at 18:56
I waiting to any response!! –  Gold Rose Sep 25 at 17:59