5
$\begingroup$

I discovered the chinese remainder theorem (CRT) version of RSA cryptosystem which is used in many crypto libraries (OpenSSL, Java...).

The use of this theorem improves the speed of decryption so, why is it not always applied? What are the disadvantages of this version which would explain that it's not always implemented?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
7
$\begingroup$

The following potential reasons occur to me why someone might not choose to use the CRT optimization:

  • The implementor worries about induced faults (but not quite enough to implement the obvious protection against it). That is, with the CRT optimization, we process the RSA block both mod p and mod q separately, and then combine them. That means that if the attacker can induce a miscomputation in one of the sides, we'll get the correct answer mod p (say), but not mod q. This can leak the factorization of the modulus

  • The CRT optimization requires us to hold the prime factors; perhaps the implementer has restrictions on the amount of memory that can be used for a private key. Note that it's possible to factor the modulus anyways if you have both the public and private keys, and so security isn't likely to be an issue here.

  • The implementer doesn't care about performance, and instead values simplicity

  • The implementer is clueless, and doesn't know about the CRT optimization

Improve this answer
$\endgroup$
2
  • $\begingroup$ More reasons, especially in Smart Cards: $\;$ a) It is slightly involved to derive the CRT key $(p,q,dp,dp,qInv)$ from $(n,d)$, which may be the specified form for key injection. $\;$ b) If all we know is that the key is per PKCS#1 and $N$ is $k$-bit, $p$ might still be much more than $k/2$ bits, so perhaps for some keys it does not fit the available hardware well and CRT gives no time savings. $\;$ c) As mentioned in answer, the CRT form of the key requires more space, about +75% more since $(N,e)$ needs to be available in order to check the result as a countermeasure against fault attacks. $\endgroup$
    – fgrieu ♦
    Oct 25, 2014 at 15:49
  • 1
    $\begingroup$ @fgrieu I've seen the same validation requirement for straight RSA as well. In general it makes sense as signature verification is relatively fast. $\endgroup$
    – Maarten Bodewes ♦
    Oct 25, 2014 at 18:09
3
$\begingroup$

It is generally applied as far as I know. One thing that makes it tricky to implement in some situations is that it may be more vulnerable to certain side channel and fault injection attacks than "straight" RSA. Those attacks may expose the prime factors and thus the private key.

I cannot see other reasons why it wouldn't be implementable on some platforms, except that it may be somewhat more complex. It may use slightly more memory, but on embedded systems, performance is usually a great good as well.

Note that the private key is usually kept on the system doing the RSA CRT operations. The public key is identical. So you may not always see that it is applied from the outside.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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