How bad is 3 as an RSA public exponent

Question

I'm creating an application where I have to use RSA to encrypt some stuff using a public key. I want this encryption to be really fast. Initially, I tried a 2048 bit key with F4 (=65537) as the exponent but it is not fast enough. So now I'm considering the following 2 options:

1. 2048 bit modulus, e=3
2. 1024 bit modulus, e=65537

Both satisfy my performance requirements but which one provides better security? I should also note that I use the PKCS#1 padding scheme.

Answer 1

If you use random padding such as OAEP in PKCS#1, most (all?) of the known weaknesses from using low exponents are no longer relevant.

Also have you tried using e=17? There's no rule saying you have to choose either 3 or 65537.

Answer 2

While there is currently no known attack against if a correct padding is used, small exponents are more likely to lead to exploits in case of implementation errors. And implementation errors are unfortunately still a threat. E.g. this is a vulnerability that was quite "popular". (Note, this is for signatures. I just want to show that even commercial software can have serious bugs.)

If you have to cut corners, then you have to consider the potential implications of your actions. I.e. choosing a small modulus or a small exponent both have their own drawbacks.

If you choose a small (1024 bit) modulus then you can't assume that your data can be kept confidential for decades.

If you choose a small exponent you might be more susceptible to implementation errors.

In the first case, you pretty much know when your secrets are in danger, since it is quite easy to follow the progress made in factoring. (This assumes of course that agencies that don't publish e.g. NSA is not your enemy). In the second case (implementation errors), you don't know when you made a mistake. You might be safe using e=3 or you might have made a big blunder. I.e. in one case you have a rather good way to estimate your risk, and in the other case you have not.

Therefore, I'd recommend not to use e=3 at all. I'd use more safety margin against those threats that are hard to predict, than those threats that are widely publicized.

Answer 3

To cite Don Coppersmith's 1997 paper "Small Solutions to Polynomial Equations, and Low Exponent RSA Vulnerabilities":

RSA encryption with exponent 3 is vulnerable if the opponent knows two-thirds of the message.

While this may not be a problem if RSA-OAEP padding scheme is used, the PKCS#1 padding scheme (which op is using) is vulnerable if public exponent 3 is used.