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

[Peter Fairbrother]

On 25/01/2026 09:14, Pierre Abbat wrote:

> * but there's nothing about the protocol itself that requires the number of
> bits in p to be a multiple of anything.

Nope, nothing.


The reason is efficiency, sort-of. Sort-of.

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.

A 704-bit exponentiation would need about 12,100 calculations.

So you might as well use 704 bits rather than 641, ie a prime whose bits 
are a multiple of 64 (or better 128).


I made up those numbers, and the ratio varies according to how the 
calculation is done (and how big p is will change that), but you get the 
picture, I hope.



Peter Fairbrother