[Cryptography] Random numbers for Diffie-Hellman

[Viktor Dukhovni]

On Thu, Nov 28, 2024 at 01:57:21AM -0500, Pierre Abbat wrote:

> Suppose Alice and Bob share a field F[p], where p=nq+1, n is small, and p and q 
> are prime, and a generator g whose order is q. (Or they could use an elliptic 
> curve group of size nq.) Ideally they want to generate random numbers a and b 
> in the interval (0,q), but since q-1 is not a power of 2, it's impossible to 
> do this without wasting some random bits. Suppose m is the largest number such 
> that 2^m<q. How does it affect the security if
> 
> * they pick random m-bit numbers and add 1?
> 
> * they pick random (m+1)÷2-bit numbers and add 1?
> 
> * they pick random numbers of a bit length between those and add 1?
> 
> How would you pick random numbers from 1 to k, where k is not a power of 2, to 
> minimize wastage of random bits?

AFAIK, this sort of thing should be OK for (EC)DH, but is definitely NOT
OK for ECDSA (Schnorr signing in general), where non-uniformity in the
nonce generation is problematic.

-- 
    Viktor.