What software commonly generates RSA keys with public exponent 0x23 (35)?

Question

Reviewing the SSH keys of hosts that I connect to (as gathered by PuTTY in registry key HKEY_CURRENT_USER\SoftWare\SimonTatham\PuTTY\SshHostKeys), I find that they all start with 0x10001 (65537) or 0x23 (35), most often followed by 2048-bit composite values with no small factor. I conclude they are RSA keys, and that 0x23 (35) is the second most common public exponent in my sampling.

What software commonly generates RSA keys with that public exponent 0x23 (35)? Why that value, which is not prime, and thus slightly complicates the selection of the factors of the public modulus?

Answer 1

Versions of OpenSSH up to 5.3 AFAICT then they switched to F4=65537. I don't recall seeing an explanation for why they used 35, but I haven't read every line of everything.

Answer 2

The OpenSSH rsa_generate_private_key() function that was changed in version 5.4 to use the more common 65537 (RSA_F4) was introduced in key.c by this commit back in 2000, and already have the public exponent at 35. However, if you go back in time that function already existed in rsa.c before and the first revision from 1999 was already using 35 from the start, its creation part of a large refactoring effort to stop using gmp and to use OpenSSL's libcrypto functions instead.

Trying to see when 35 was first introduced, and found that in the 1.0 release of Tatu Ylönen's SSH the public exponent was generated by the following code (function derive_rsa_keys() called from rsa_generate_key() in rsa.c) which would have stumbled on 35 often, but not always.

  /* Find a suitable e (the public exponent). */
  mpz_set_ui(e, 1);
  mpz_mul_2exp(e, e, ebits);
  mpz_sub_ui(e, e, 1); /* make lowest bit 1, and substract 2. */
  /* Keep adding 2 until it is relatively prime to (p-1)(q-1). */
  do
    {
      mpz_add_ui(e, e, 2);
      mpz_gcd(&aux, e, &phi);
    }
  while (mpz_cmp_ui(&aux, 1) != 0);

That code stayed the same until ssh-1.2.12 which is the most recent OpenSSH ancestor in the original SSH line. In OSSH-1.2.16 (intermediate ancestor to OpenSSH) it also stayed the same, and afterwards it seems during the SSH import in the OpenBSD tree, the refactoring to use libcrypto instead of libgmp in 1999 happened immediately and introduced the fixed 35. If CVS is to be trusted it's Niels Provos that did the work (but likely in close communication with Markus Friedl and others), and as the commit message doesn't mention a reason only him should know for sure why he chose 35.

However, from my point of view, even if it wasn't the best choice for keygen performance (Peter Gutmann going as far as calling it cargo culting) it was the safe conservative choice, as with so many SSH keys in usage already with 35 as public exponent, there was quasi certainty this would not introduce any breakage.