Choose your own exponents in RSA?

Question

In another interesting post, one of the developers/security researchers behind Phuctor suggests that using different exponents with RSA keys will "[increase] the costs of attacking your setup astronomically."

While the author does state that "it is not said nor implied here that there's any sort of theoretical vulnerability related to using 65537 as an exponent for RSA," this suggestion gets me thinking.

I have a few interrelated questions:

1. Is it possible to generate (PGP|SSH|SSL) RSA keys that use a different exponent?
2. Does a different, larger exponent increase the work effort required for an attacker? Does it increase the work effort required for legitimate uses?
3. If I generate keys with a different exponent, do I lose compatibility with certain systems? ie: if a system supports 2048bit RSA, will it likely also support 2048bit RSA with a different exponent?

Using a different exponent seems interesting to me, but people often have been compromised when they made a choice they didn't fully understand: even when they think they're adding security, they may be, in fact, diminishing it.

Answer 1

RSA itself, as specified in PKCS#1, does not mandate any specific value for the public exponent e. That value e must be relatively prime to both p-1 and q-1 (where p and q are the two factors that constitute the RSA modulus), but there is no other restriction. The exponent e does not even need to be prime. It needs to be an odd integer, because p-1 and q-1 are even (since p and q are big primes, hence odd). The use of 65537 is just a widespread tradition. There is also an idea floating around that this specific value is somehow "more secure" than others (in particular using e = 3), but that's a myth. The most efficient public exponent is e = 3, though this impacts only public-key operations, which are extremely rarely the bottleneck in any given system.

In fact there is no relation whatsoever between that exponent and the attack cost. "Practical" attack methods for RSA try to factor the modulus, and completely disregard the public exponent value. The page you link to appears to want to use an exponent distinct of 65537 for the sole reason that some other people (that the page author does not like) recommend using 65537. This is a fascinating example of human psychology at work, but scientifically it has no value.

Generating an RSA key with an arbitrary public exponent is not harder, and most RSA libraries support it (command-line tools may be more limited). As for interoperability, you should be aware that some widespread RSA implementations, in particular the one on Windows (and thus used for SSL and for certificate validation), require the public exponent to fit into 32 bits -- not for enhanced or lowered security or whatever, but simply because it made life a bit easier for the original developer, who could devote a fixed-width small field for public exponent encoding. If you want to keep your interoperability, you should choose your public exponent in the 3 to 4294967295 range.