[Cryptography] Random numbers for Diffie-Hellman

[Pierre Abbat]

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?

Pierre
-- 
ro nu co'i cortu cu nu co'a certu