[Cryptography] Generating random values in a particular range

[dj at deadhat.com]

> Jerry Leichter wrote on 6/08/16 7:39 AM:
>> Guess what:  The use of that second technique *for generating a random
>> element of a group of order q for use in cryptograpnhy* is the subject
>> of a
>> patent, filed in 2000, https://www.google.com/patents/US7372961.
>> Blackberry is asserting it (among others that I haven't looked at)
>> against
>> Avaya.
>
> That patent link says that it has a priority date of Dec 27, 2000 (with a
> disclaimer that Google has not performed a legal analysis to come up with
> that
> date).
>

My reading of the patent is that it says - Instead of pulling a random
number until we find one where H(rn)<q, we pull one random number, seed a
PRNG with it and pull from the PRNG until we find one where  H(rn)<q.

The PRNG they propose is CTR mode, but using a hash instead of a block
cipher.

This is no different to pulling from a RNG that presents a PRNG seeded
from an entropy source until you get one where H(rn) < q. It's just moving
the boundary.