[Cryptography] Why are Diffie-Hellman key sizes multiples of 64?

[Nicko van Someren]

> On Jan 25, 2026, at 17:16, Jon Callas <jon at callas.org> wrote:
> 
>> On Jan 25, 2026, at 01:14, Pierre Abbat <phma at bezitopo.org> wrote:
>> 
>> Does this requirement come from the library they're using? I don't see what's 
>> wrong with using a 4184-bit or 4235-bit prime, as long as it's a safe prime, 
>> strong prime, or Fouvry prime.
> 
> It's a stupid requirement coming from programmers who don't want to do the work to make it work with any machine word size. Nothing to do with the math.
> 
> Now, speaking out of the other side of my mouth, if you assume your numbers fit neatly into machine words, you can write a simplified, faster algorithm. At least that's what it says on the marketing brochure.

Speaking as someone who was once both the engineer implementing this and the product marketing person (ahh, the joys of start-ups), and so both wrote both the code and the marketing brochure, the back in the 90s when CPUs were orders of magnitude slower than they are now the answer was to a large extent price-performance ratio.

Our devices would handle any key size you wanted, but they went much faster when the size was a multiple of 32. This was because you got to avoid having to do several steps by hand and also because you got to squeeze every last cycle out of the CPU. Montgomery multiplication involves a fair amount of "divide by 2^N" and "modulo 2^N"; these are trivial when N is a multiple of the machine word size and require code when it's not (and the divide is actually tediously slow). Also, multiplying together two 31 bit numbers into a 62 bit result does a few percent less work for you then multiplying together two 32 bit numbers into a 64 bit result, and back then every cycle counted.

> ...
> 
> There's no math reason, it's an engineers-being lazy reason, where "lazy" might be a pejorative way to say "prudent." Or not.

No, it's an engineers saying "if you use it this way it will work better for you" reason. That's not the same as being lazy and not quite the same as prudent either. When you are operating in a highly constrained environment knowing how to make the best use of the resources available is valuable.

Back in 1995 the Sun Netra web server product was capable of handling a whopping 0.9 SSL handshakes per second, almost entirely limited by the speed of the RSA decrypt. The RSA decrypt was that slow because the BSafe library as optimised for portability and flexibility, not performance. By writing optimised code AND telling people how to use it most efficiently we were able to achieve more than an order of magnitude speed-up on the same hardware, and more than two orders of magnitude speed-up on optimised hardware.

For most sensible products having the key sizes a multiple of the word size was always a recommendation, not a requirement. In the of cases where it was an actual requirement then yes, I'll buy Jon's argument that it was lazy, but I think it was probably lazy on the side of product support as well as the engineers, since they didn't want to field calls from customers saying "why the hell is this code running so slow"?

Cheers,
Nicko