Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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 note that I use the PKCS#1 padding scheme.

like image 687
safsaf32 Avatar asked Dec 28 '09 00:12

safsaf32


People also ask

What is public exponent in RSA?

In the real world, typically the RSA modulus n and the private exponent d are 3072-bit or 4096-bit integers and the public exponent e is 65537.

What is the problem in choosing 2 as public key e in RSA?

The problem is that for N=pq for two primes p and q, the function f:x↦x2modN is not injective. So it is impossible to invert uniquely.

What is the most common number for public exponent e in RSA public key?

A somewhat surprising detail of RSA public key cryptography is that in practice e is nearly always the same number, specifically e = 65537. We will review RSA, explain how this default e was chosen, and discuss why this may or may not be a problem.

Why is the RSA public exponent is selected as 216 1?

It needs exactly n+m multiplications, where n is the total length of the binary written exponent and m is the number of 1-bits in the exponent. Therefore exponentation with 2^16+1 is almost twice as fast as exponentiation with say 2^17-1.


3 Answers

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.

like image 152
Mark Byers Avatar answered Sep 24 '22 03:09

Mark Byers


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.

like image 27
Accipitridae Avatar answered Sep 23 '22 03:09

Accipitridae


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.

like image 45
FaST4 Avatar answered Sep 20 '22 03:09

FaST4