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

[Nicko van Someren]

> On Jan 26, 2026, at 00:33, Peter Fairbrother <peter at tsto.co.uk> wrote:
> 
> The reason is efficiency, sort-of. Sort-of.

The reason is efficiency, full stop.

> The ALU multipliers in modern CPUs generally work on 64-bit chunks (though some GPUs and cryptographic FPGAs use 128-bit ALU multipliers, and 128-bit adders are not unknown - but we are mostly concerned with multiplications here).
> 
> Even if the biggest chunk starts with lots of zeros, you still have to do (most of) the operations for that chunk.
> 
> So if the work needed for calculating an exponentiation modulo a 640-bit prime is 10,000 64-bit unit calculations, the work needed for a 641-bit prime is roughly 12,000 64-bit unit calculations.

The problem is not with the multiplication, it's with the division (which is needed for the modulo reduction). Shifting numbers right by a number of bits that is a multiple of the word size is a zero-cost reindex. Shifting right by a number of bits that is not a multiple of the word size requires two mask and two shifts or rotates per word. On some CPUs that takes more cycles than a word by word multiply. The practical performance difference between 1024 bit and 1023 bit mod-exp is substantial and the impact is proportionally larger on smaller key sizes. Back in the days when the standards were starting to be set people were still using 512 bit RSA for production services, and at that size the performance impact is very noticeable.

Cheers,
Nicko