Take the 2-minute tour ×
Information Security Stack Exchange is a question and answer site for Information security professionals. It's 100% free, no registration required.

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.

share|improve this question

5 Answers 5

up vote 27 down vote accepted

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").

share|improve this answer
    
Very well said. IIRC, at some point in its many incarnations, PGP used to generate a random 16 bit public exponent during key generation. –  GregS Mar 2 '11 at 0:59
5  
In a stunning development, this post is now used to justify using 1 as a public exponent github.com/saltstack/salt/commit/… –  Bruno Rohée Jul 9 '13 at 15:48

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.)

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
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 2 '11 at 6:13
    
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 (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 2 '11 at 6:30

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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