The issue of exponents in RSA

You might perhaps remember this patch :

  /* Find an public exponent.
       Benchmarking the RSA verify function with a 1024 bit key yields
       (2001-11-08):
         e=17    0.54 ms
         e=41    0.75 ms
         e=257   0.95 ms
         e=65537 1.80 ms

       This code used 41 until 2006-06-28 when it was changed to use
       65537 as the new best practice.  See FIPS-186-3.
     */

Well... am I the only one nonplussed by all this "we use «best practices» fixed exponent" bullshit ?

It's an unavoidable magic number, okay. But it's also the sort of magic number that should eminently be a knob for the user to turn. I say a proper PGP implementation would have e user-settable at the key generation phase (with 65536+1 as a default, sure).

Looking into this matter, there are 6544 prime numbers between 1 and 65`536. It should not be too difficult to create the list of prime numbersⁱ of the form p1 * 65536 + p2, where p1 and p2 are prime themselves. Off to the hacks!

[ Assorted cloinking noises and a faint buzzing in the distance... ]

Yes, here we go : a list of all prime numbers of the form p1 * 65536 + p2, where p1 and p2 are prime themselves, up to 100`000`000ⁱⁱ (1.2MB).ⁱⁱⁱ All sorts of interesting looking stuff in there, like 71237, 77699, 100019, 137383, 69696797 etc.

Is this going to be slower than the 65537 default ? Yes. Stop being poor.

Is this going to be less secure than the 65537 default ? No. Because :

If you are able to brew your own set of hardware, such as for instance out of ARM processors, or FPGA boards which you program yourself, or soldered together Z80s or whatever else, it's a great idea to do so. Just as long as you actually know what you're doing, this sort of arrangement increases the costs of attacking your setup astronomically. It's not likely practical for most people, but if it's practical for you then by all means - and in any case the attempt will likely leave you a lot wiser.

When it comes to digital security, you want to not follow the NIST as often as you can get away with it - for the simple reason that the NIST works for the same people the propaganda machine works for, and that's most definitely not you. Decentralisation is the name of the game. While there are places where standards are useful and necessary, their presence anywhere else is absolutely evil. There most certainly SHOULD NOT exist a standard for RSA exponents in the shape of "use X".

Note 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.^iv The point is that you don't know what exact implementation flaws the NSA is or may be relying on, and for this reason giving as little quarter as possible is the correct policy.

1. We want e to always be prime because we're afraid that idiot software implementations assume e to be prime and then check that e is coprime to (p − 1)(q − 1) by simply trying to divide the product. Because hey, "it's faster" hurr durr. [↩]
2. You don't want the public exponent to be too big because de = 1 mod phi(pq) and there are some known attacks for the case where d < ~0.3 * e. Since the product is ~18 digits (2¹⁰ ~= 10³ and therefore 2⁶⁴ > 10¹⁸), picking an e with at most 8 digits ensures d is always larger. [↩]
3. And here is a list of all prime numbers of the form p1 * 65536 + p2, where p1 and p2 smaller than 256 and prime themselves :

   65537, 65539, 65543, 65579, 65609, 65633, 65687, 65699, 65717, 65729, 65777, 131101, 131113, 131143, 131203, 131221, 131251, 131311, 196613, 196661, 196681, 196687, 196709, 196717, 196739, 196771, 196799, 196831, 196837, 327721, 327739, 327829, 327853, 327871, 458789, 458819, 458849, 458879, 458891, 458963, 458981, 458993, 720899, 720901, 720913, 720943, 720997, 721003, 721087, 721129, 851971, 852011, 852149, 852167, 852179, 852191, 852197, 1114117, 1114159, 1114213, 1114249, 1114261, 1114303, 1245187, 1245191, 1245227, 1245281, 1507369, 1507501, 1900597, 1900603, 1900711, 1900777, 2031713, 2031767, 2031779, 2031839, 2424833, 2424839, 2424971, 2425043, 2686979, 2686993, 2687023, 2687029, 2687059, 2687143, 2687149, 2818157, 2818229, 2818271, 3080251, 3080263, 3080359, 3080419, 3080431, 3080443, 3473419, 3473521, 3473557, 3473641, 3473647, 3866627, 3866647, 3866713, 3866791, 3866857, 3997769, 3997859, 3997919, 4391039, 4391063, 4653059, 4653139, 4653169, 4653247, 4653307, 4784141, 4784237, 4784267, 4784279, 4784321, 5177351, 5177363, 5177387, 5177441, 5177453, 5439547, 5439619, 5439667, 5439727, 5832709, 5832763, 6357011, 6357023, 6357101, 6357203, 6357233, 6619139, 6619141, 6619159, 6619219, 6619303, 6619363, 6619369, 6750209, 6750221, 6750251, 6750407, 6750437, 7012363, 7012393, 7012543, 7143443, 7143467, 7143491, 7143581, 7405571, 7405627, 7405639, 8323103, 8323109, 8323151, 8323169, 8323229, 8323253, 8585287, 8585389, 8585449, 8978449, 8978479, 8978491, 8978503, 8978539, 9109547, 9109571, 9109577, 9109613, 9109697, 9109703, 9764971, 9764977, 9765001, 9765037, 9765043, 9765061, 9895939, 9895943, 9896039, 9896147, 10289183, 10289333, 10289351, 10682387, 10682429, 10682471, 10682561, 10682597, 10944523, 10944529, 10944613, 10944649, 10944763, 11337751, 11337757, 11337787, 11337877, 11337961, 11337967, 11337979, 11730949, 11730973, 11730997, 11731033, 11731141, 11731171, 11862029, 11862083, 11862167, 11862239, 12517387, 12517399, 12517489, 12648451, 12648521, 12648659, 12910819, 13041683, 13041767, 13041803, 13041893, 13828109, 13828169, 13828247, 13828253, 14614559, 14614631, 14614709, 14614727, 14614757, 14876713, 14876731, 14876761, 14876773, 14876803, 14876821, 15007781, 15007823, 15007847, 15007901, 15007907, 15007943, 15269911, 15269929, 15269959, 15270019, 15270127, 15270139, 15663121, 15663133, 15663157, 15663211, 15663217, 15663283, 15663331, 15794213, 15794237, 15794243, 15794249, 15794333, 15794369, 16449541, 16449547, 16449703, 16449709. [↩]

4. Or for that matter any other number, provided q and p are then chosen correctly, and leaving aside the issues related to the nefarious interaction of small exponents and bad padding. [↩]