Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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:
The later condition
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 37th power modulo $N$ requires 7 modular multiplications, versus 5 for the 17th, or 2 for the 3rd.
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).
Update on speculations following research by Bruno Rohée: in SSH 1.0, key generation drew primes $p$ and $q$, then chose $e$ as the smallest odd integer at least $33$ such that $\gcd(e,p-1)=1=\gcd(e,q-1)$. Assuming uniform choice of $p$ and $q$ among primes (I've not checked that), this resulted in $e=33=3⋅11$ with probability $p_{33}=\left(\frac{3-2}{3-1}\frac{11-2}{11-1}\right)^2\approx20\%$; in $e=35=5⋅7$ with probability $p_{35}=(1-p_{33})\left(\frac{5-2}{5-1}\frac{7-2}{7-1}\right)^2\approx31\%$; in $e=37$ with probability $p_{37}=(1-p_{33}-p_{35})\left(\frac{37-2}{37-1}\right)^2\approx46\%$. Hence $e\in\{33,35,37\}$ was by far the most common public exponents in SSH, and well supported. Thus a logical and conservative choice for a key generation procedure making use of prime public exponent $e$ (which simplifies things slightly) was $e=37$, since it used to be common, and was well-supported.
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
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.x). 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.
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.
