Why is PuTTYgen-created RSA public exponent(e) not in {3,17,65537}?

Question

As far as I know, RSA public exponent(e) should be one of {3,17,65537}.
However, I found PuTTYgen-created RSA public exponent(e) is 0x25(37) by default,as follows, (PuTTYgen version: 0.66)

I am curious why PuTTY uses 0x25(37) instead of 0x10001(65537), and does 0x25(37) offer adequate security?

Answer 1

The answer is in the source, file sshrsag.c, line 9:

#define RSA_EXPONENT 37 /* we like this prime */

This value $e=37$ matches the conditions for a reasonable fixed RSA public exponent:

• $e$ is odd,
• $e$ is at least $3$,
• $e$ is reasonably small.

The later condition

• is good for speed of operations involving the public key (encryption, and signature verification);
• makes it harder to choose the prime factors of the public modulus so as to get an unnaturally small $d$, which could allow factorization.

That $e=37$ is prime simplifies the choice of the prime factors of the public modulus $N$, as explained in a later comment:

Generate $p$ and $q$: primes with combined length `bits', not congruent to $1$ modulo $e$. (Strictly speaking, we wanted $(p-1)$ and $e$ to be coprime, and $(q-1)$ and $e$ to be coprime, but in general that's slightly more fiddly to arrange. By choosing a prime $e$, we can simplify the criterion.)

The only known drawback of $e=37=2^5+2^2+1$ compared to $e=17=2^4+1$ or $e=3=2^1+1$ is that raising to the 37^th power modulo $N$ requires 7 modular multiplications, versus 5 for the 17^th, or 2 for the 3^rd.

We can speculate that the authors like $e=37$ because it is not of a special form, as are the Fermat primes $F_k=2^{(2^k)}+1$ with $0\le k\le4$, often used as RSA public exponents. A compromise between being large and allowing efficient public-key operation was likely not part of the considerations: the larger $e=41=2^5+2^3+1$ also requires only 7 modular multiplications (and as a bonus, is closer to the Answer).

---

The rest of this answer reports on my incomplete review of the RSA code of PuTTY 0.66, aimed at weakness related to the relatively small $e=37$. I have not identified any if the generated key is used by (that version of) PuTTY, and all other entities relying on the corresponding public key do so properly. Otherwise, I can't rule out that some systems have vulnerabilities that could be more easily exploitable with PuTTY's $e=37$ than the traditional $e=65537$ mandated as the minimum by several security authorities. I'm thinking in particular of

• incorrect verification of PKCS#1 V1.5 type 01 signature, which abound; see Daniel Bleichenbacher's RSA signature forgery based on implementation error (archived account by Hal Finney of Crypto 2006 rump session); Ulrich Kühn, Andrei Pyshkin, Erik Tews, Ralf-Philipp Weinmann Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures; and yet other reports.
• vulnerable (even if conformant) implementations of decryption per PKCS#1 V1.5 of padding type 02, as considered by Daniel Bleichenbacher's Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 (in proceedings of Crypto 2008).

There is no known weakness associated to using small $e$ when RSA is used with good padding (as RSASSA-PSS and RSAES-OAEP in PKCS#1 V2). Other RSA paddings supported in PuTTY include lesser PKCS#1 V1.5 paddings, but I did not find the dreaded padding type 00, which essentially is no padding, unsafe, and even more unsafe for small $e$. PuTTY can use PKCS#1 V1.5 padding type 01 for signature, which has no known vulnerability for correct verification, as performed by PuTTY. It can use PKCS#1 V1.5 padding type 02 for encryption, but does not implement decryption with potentially vulnerable padding check.

Answer 2

Any $e$ such that $\gcd(e, (p-1)(q-1)) = 1$ will do. There is no need for it to be in the set $\{3,17,65537\}$; these last numbers are chosen for speed of encryption, mostly (two set bits leads to faster computation of modular exponentation), and these numbers happen to be prime, so the condition is easily checked. One often encounters other $e$, but many standard packages by default produce one of these three. $37$ is no more or less secure than $17$, essentially.