82

In my project I'm using the value of public exponent of 4451h. I thought it's safe and ok until I started to use one commercial RSA encryption library. If I use this exponent with this library, it throws exception.

I contacted developers of this library and got the following reply: "This feature is to prevent some attacks on RSA keys. The consequence is that the exponent value is limited to {3, 5, 17, 257 or 65537}. Deactivating this check is still being investigated, as the risks may be great."

It's the first time in my life I hear that values other than {3, 5, 17, 257 or 65537} are used to break RSA. I knew only of using 3 with improper padding being vulnerable.

Is that really so? Surely, I can use another library, but after such answer I worried about security of my solution.

Mark Davidson
  • 9,367
  • 6
  • 43
  • 61
Vladislav Rastrusny
  • 1,073
  • 1
  • 9
  • 9

6 Answers6

73

There is no known weakness for any short or long public exponent for RSA, as long as the public exponent is "correct" (i.e. relatively prime to p-1 for all primes p which divide the modulus).

If you use a small exponent and you do not use any padding for encryption and you encrypt the exact same message with several distinct public keys, then your message is at risk: if e = 3, and you encrypt message m with public keys n1, n2 and n3, then you have ci = m3 mod ni for i = 1 to 3. By the Chinese Remainder Theorem, you can then rebuild m3 mod n1n2n3, which turns out to be m3 (without any modulo) because n1n2n3 is a greater integer. A (non modular) cube root extraction then suffices to extract m.

The weakness, here, is not the small exponent; rather, it is the use of an improper padding (namely, no padding at all) for encryption. Padding is very important for security of RSA, whether encryption or signature; if you do not use a proper padding (such as the ones described in PKCS#1), then you have many weaknesses, and the one outlined in the paragraph above is not the biggest, by far. Nevertheless, whenever someone refers to an exponent-size related weakness, he more or less directly refers to this occurrence. That's a bit of old and incorrect lore, which is sometimes inverted into a prohibition against big exponents (since it is a myth, the reverse myth is also a myth and is no more -- and no less -- substantiated); I believe this is what you observe here.

However, one can find a few reasons why a big public exponent shall be avoided:

  • Small public exponents promote efficiency (for public-key operations).

  • There are security issues about having a small private exponent; a key-recovery attack has been described when the private exponent length is no more than 29% of the public exponent length. When you want to force the private exponent to be short (e.g. to speed up private key operations), you more or less have to use a big public exponent (as big as the modulus); requiring the public exponent to be short may then be viewed as a kind of indirect countermeasure.

  • Some widely deployed RSA implementations choke on big RSA public exponents. E.g. the RSA code in Windows (CryptoAPI, used by Internet Explorer for HTTPS) insists on encoding the public exponent within a single 32-bit word; it cannot process a public key with a bigger public exponent.

Still, "risks may be great" looks like the generic justification ("this is a security issue" is the usual way of saying "we did not implement it but we do not want to admit any kind of laziness").

Thomas Pornin
  • 320,799
  • 57
  • 780
  • 949
  • 2
    Very well said. IIRC, at some point in its many incarnations, PGP used to generate a random 16 bit public exponent during key generation. – President James K. Polk Mar 02 '11 at 00:59
  • 23
    In a stunning development, this post is now used to justify using 1 as a public exponent https://github.com/saltstack/salt/commit/5dd304276ba5745ec21fc1e6686a0b28da29e6fc#commitcomment-3525158 – Bruno Rohée Jul 09 '13 at 15:48
  • 4
    For the sake of posterity. The key recovery attack that applies when using a small private exponent (or large public exponent) is called [Wiener's attack](https://en.wikipedia.org/wiki/Wiener's_attack). – rlf Oct 19 '17 at 12:54
24

Those five numbers are Fermat primes.

Since they are of the form 2k + 1, encryption is me = m·((m2)2...k times...)2, which is simpler and faster than exponentiation with an exponent of a similar size in the general case.

Since they are primes, the test that e is coprime to (p − 1)(q − 1) is just a test that e doesn't divide it.

So this is more likely about speed or convention than about security. Not that there's anything wrong with being efficient. But to be sure, do ask for a reference as the other answer suggested.

Also see this post.

Community
  • 1
aaz
  • 341
  • 1
  • 2
23

The developers are simply incorrect. There's nothing wrong with the exponent 0x4451 (decimal 17489); it doesn't create any security problems.

Long ago people used to think that small exponents were a problem, because of an attack that Thomas Pornin explained with sending the same message to multiple recipients. But today we understand that the exponents had nothing to do with it; the issue was improper padding. Those attacks are prevented by proper use of padding. Any crypto library worth its salt had darn well better be using proper padding (otherwise you've got far worse problems).

So there is no good reason for a crypto library to flatly forbid use of that exponent.

That said, from a performance perspective, the smaller the exponent, the better the performance. The best choice is e=3, because that gives the best performance and has no known security problems. (Actually, e=2 is even a bit better. It is also known as Rabin encryption. However, that scheme is not as well known and requires slightly different code, so it is not widely used.)

D.W.
  • 98,420
  • 30
  • 267
  • 572
  • Are you sure "e=2 is even a bit better" applies to RSA? With e=2, there isn't an inverse because phi(N) is even. – Yifan Mar 15 '15 at 22:28
  • 2
    @Yifan, you might start by reading https://en.wikipedia.org/wiki/Rabin_cryptosystem. – D.W. Mar 16 '15 at 01:18
  • 1
    For Rabin, decryption is: m=sqrt(c)mod N, given c=m^2 mod N. For RSA, decryption is: m=c^d mod N, given c=m^e mod N. In the case of e=2, there is no inverse mod phi(N) (since 2 and phi(N) are not relatively prime) so you can't find a d such that e*d=1 mod phi(N). – Yifan Mar 16 '15 at 06:02
  • 2
    @Yifan, yes, I understand all of that. I'm not sure where you're going with this. I am saying that Rabin with e=2 is even a bit better still than RSA with e=3. No, Rabin with e=2 is not the same as RSA, but the differences are a detail that is beyond the scope of this particular question. – D.W. Mar 16 '15 at 07:28
  • 8
    Okay, that's the clarification I wanted. To the untrained eye, your answer implies you can choose e=2 for RSA. – Yifan Mar 16 '15 at 17:19
9

I'm not aware of any reason why the public exponent of an RSA key should only be in the set {3,5,17,257,65537}. As you mention, small exponents such as 3 or 5 are riskier to use, because the negative effects of implementation errors (such as improper padding) can be larger. NIST only allows public exponents larger than 2^16, but I don't know a reason for their decision.

You should not be satisfied by the answer given by the developers of the library that you use and ask for a concrete reference. Much too often, it turns out that some paper was misunderstood. I could for example imagine that some developer reads Section 4 of the paper "Can We Trust Cryptographic Software? Cryptographic Flaws in GNU Privacy Guard v1.2.3" by Phong Nguyen and comes to an incorrect conclusion, such as the one above. This paper notices that when the public key generated by GnuPG turns out to be some unusual value such as 65539, then the attacker learns a little information about the secret key. The conclusion there is that GnuPGs key generation algorithm could be improved, but not that 65539 is a bad public key.

8

I couldn't find any reference that other values for the public exponent are vulnerable. Tough using a public exponent close to a power of 2 is advisable for performance reasons, according to the RSA.com guide to the RSA algorithm

According to Wikipedia, NIST doesn't allow a public exponent smaller than 65537, since smaller exponents are a problem if they aren't properly padded.

Andreas Arnold
  • 2,353
  • 19
  • 19
  • It turns out the last paragraph of this answer is flat-out wrong. (Wikipedia is wrong; imagine that!) The problem has nothing to do with small exponents. If you don't use proper padding, you are so screwed (and this is true no matter what exponent you use). If you do use proper padding, small exponents are just as good as large ones. So it is a misconception to think that this has anything to do with the size of the exponent, as opposed to the presence/absence of proper padding. – D.W. Mar 02 '11 at 06:13
  • 3
    As I said, withough proper padding. But I checked the source of the Wikipedia statement, and it is partially wrong. According to SP 800-78 -3 (http://csrc.nist.gov/publications/nistpubs/800-78-3/sp800-78-3.pdf), page 6: " This specification also restricts the size of the RSA exponent that may be associated with PIV keys. Implementations of this specification must choose an exponent that is an odd positive integer greater than or equal to 65,537 and less than 2 256, as specified in Table 3-2". So only for PIV-Keys (Personal Identity Verification) according to FIPS 201. – Andreas Arnold Mar 02 '11 at 06:30
-1

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 is given as a proper padding scheme in the answers below) is vulnerable if public exponent 3 is used.

FaST4
  • 156
  • 4
  • This is not quite an answer. You address just one exponent, and there are other answers posted years before yours that seem to already address this problem in much greater detail. Downvotes do not necessarily mean that you are wrong. Downvotes can simply mean that your answer is "not useful" (as per the tooltip), which I would agree with in this case. – schroeder May 13 '19 at 08:58
  • The previous answer states that "There is no known weakness for any short or long public exponent for RSA" which is factually incorrect. That's what my answer tries to point out. – FaST4 May 14 '19 at 12:33
  • So, this is a response to another answer? – schroeder May 14 '19 at 13:01
  • If you think that the accepted answer is wrong, please post a comment on that answer. I'm sure that Pornin is more than expert enough to assess. – schroeder May 14 '19 at 13:08