How bad is 3 as an RSA public exponent

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 n开发者_如何转开发ote that I use the PKCS#1 padding scheme.

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.

Provided that you use a good padding scheme, then there is no known reason why e=3 should have worse security than any other public exponent. Using a short exponent has issues if you also do not use a good padding scheme, but the problem more lies in the padding scheme than in the exponent.

The "gut feeling" of many researcher is that e=3 is not better than any other public exponent, and e=3 might turn out to be slightly weaker at some unspecified future date, although nothing points at such a weakness right now.

Key length has a much higher practical impact on security. A 768-bit RSA key has been cracked recently (this was not easy ! Four years of work with big computers and bigger brains). A 1024-bit key is deemed adequate for the short term, but long-term uses (e.g. the encrypted data has high value and must still be confidential in year 2030) would mandate something bigger, e.g. 2048 bits. See this site for much information on how cryptographic strength can be estimated and has been estimated by various researchers and organizations.

If you are after very fast asymmetric encryption, you may want to investigate the Rabin-Williams encryption scheme which is faster than RSA, while providing at least the same level of security for the same output length (but there is no easy-to-use detailed standard for that scheme, contrary to RSA with PKCS#1, so you are a bit on your own here).

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.

In their book 'Practical Cryptography', Bruce Schneier and Niels Ferguson suggest using a public exponent of 3 for signatures and 5 for encryption. You should double check on the other criteria they recommend which avoid catastrophes. Section 13.4 covers this (p229ff), and discusses the not very complex requirement that given n = pq (where p and q are random primes), neither (p-1) nor (q-1) can be a multiple of 3 or 5. But still double check the book for the details.

(I believe there is a new edition of the book due out in 2010.)

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.

FYI, see this for a bit of history: http://chargen.matasano.com/chargen/2006/9/18/rsa-signature-forgery-explained-with-nate-lawson-part-iv.html

If your exponent is low and the value of m*e < modulus, you can just take the eth root of the ciphertext to decrypt.

This is from my notes on crypto from two years ago. But, in answer to your question, it would seem that option 2 is better.

Someone who is more eager to do math might be able to give you a better explanation why.