I am trying to compare the encryption and decryption speed of the RSA and the DRSA scheme with same public key $(n, e)$ and private key $d$ (using SageMath). For $1024$ bits long $n$, I got the following data

Encryption of RSA(CPU/Wall time in sec): 0.36/0.66

Encryption of DRSA(CPU/Wall time in sec): 0.01/0.03

Decryption of RSA(CPU/Wall time in sec): 0.37/0.60

Decryption of DRSA(CPU/Wall time in sec): 0.71/1.15

I am confused whether this result is correct or not. According to my experimental result, the encryption of DRSA scheme is 36 times faster than the encryption of RSA scheme. In this case, can anyone help me?

| improve this question | | | | |
  • $\begingroup$ Is this ccis2k.org/iajit/PDF/vol.3,no.4/9-Padhey.pdf the DRSA scheme you are referring to? $\endgroup$ – Henrick Hellström Apr 12 '16 at 8:23
  • $\begingroup$ DRSA scheme is based on the computational dependent RSA problem (C-DRSA) problem. For a large composite modulo $n$ and an exponent $e$ relatively prime to $\phi(n)$, the computational dependent RSA problem is to find $(k+1)^e \pmod n$ when given $k^e\pmod n$, where $k\in \mathbb{Z}_n^*$. DRSA scheme is a variant of RSA scheme and it is semantically secure, whereas other variants of RSA are not. At Eurocrypt'99, Pointcheval introduced this new problem and based on this problem he designed DRSA scheme. $\endgroup$ – Pinkimani Goswami Apr 12 '16 at 8:29
  • $\begingroup$ Name of the paper "New public key cryptosystem based on the dependent-RSA problem" by D. Pointcheval, Eurocrypt'99. $\endgroup$ – Pinkimani Goswami Apr 12 '16 at 8:45

Those figures look fishy to me.

Just looking at the RSA figures, well, RSA encryption should be much faster than RSA decryption - you have them at the same speed.

The reason RSA encryption is (typically) much faster is that we can choose a small public exponent without affecting security; the typical value is 65537, but it can be made as low as 3. The fact that your figures show them running about the same speed would make me suspect that you're not doing RSA correctly. In particular, I suspect you're using small $e$ for DRSA but not for RSA.

Also, one optimization that SageMath will not try to take advantage of (unless you specify the operations yourself) is the "CRT" optimization. This is the observation that the holder of the private key can know what the factorization is, and so can work the operations "mod p" and "mod q" separately, and glue them together at the end. This would apply to both RSA and DRSA, and give about the same level of speed up (but a full analysis would involve doing both optimizated, as there might be subtle differences).

| improve this answer | | | | |
  • $\begingroup$ Now I understand. I observe that for a small value of $e$ the encryption speeds of both the schemes are all most same (0.01/0.05, for $n=1024$ bits) but when $e$ is consider randomly and bits length of $e$ and $d$ are almost same then I got the above figures. $\endgroup$ – Pinkimani Goswami Apr 14 '16 at 3:25
  • $\begingroup$ In my previous experiment, I used the same $e$ for both the schemes. Actually, I considered those operations which we can't do in advance. Hence, encryption of RSA required one modular exponentiation and DRSA need one modular multiplication. But still I have doubt, whether I can conclude that both the schemes have same encryption speed or not. $\endgroup$ – Pinkimani Goswami Apr 14 '16 at 3:44
  • $\begingroup$ @PinkimaniGoswami: that DRSA can do most of the encryption computations is useful in some scenarios; however other scenarios can't take advantage of it (as we might need to encrypt a continuous series of messages and so don't have any idle time). However, for both RSA and DRSA, encryption is the fast operation, and so making it even faster may be less of an advantage than if we could somehow precompute the slower decryption operation. $\endgroup$ – poncho Apr 14 '16 at 3:51
  • $\begingroup$ Using CRT, we are able to decrypt a message fast. Is there any other ways? means for faster decryption operation what are the main things we should notice. In this direction, how can I procced further? $\endgroup$ – Pinkimani Goswami Apr 14 '16 at 4:51
  • $\begingroup$ @PinkimaniGoswami: other than multiprime RSA (where the modulus is a product of more than 2 primes; you have to be careful with that), there isn't a good way to make RSA (or DRSA) go faster. Selecting a small $d$ value makes it easier to factor, so you don't want to go there. $\endgroup$ – poncho Apr 15 '16 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.