[Cryptography] Generating random values in a particular range

[Peter Gutmann]

Sidney Markowitz <sidney at sidney.com> writes:

>In FIPS 186-4 NIST presents two methods for fixing the problem, I presume
>because the second method they list is encumbered by the patent. Their first
>method is to get a random bit string of length L+64 and then take that mod
>the L bit prime. The idea is that the extra 64 bits before the mod results in
>enough uniformity.

That's the exact method I used, long before NIST made their recommendation
(just in case anyone needs prior art for a patent, this would have been about
1995).  In fact I've never understood why you'd use the alternative Rube-
Goldberg approach, at best you can save a mod q operation but then you've got
a bunch of hashing and nondeterministic behaviour, and doing it on a 160+delta
bit value is pretty cheap anyway.  So the easiest way to avoid the patent would
seem to be to do it the straightforward way.

Peter.