[Cryptography] Generating random values in a particular range

[Sidney Markowitz]

John Levine wrote on 7/08/16 3:08 AM:
> The hard part with these really obvious patents is finding someone who
> documented the technique before the priority date.  Since it's
> obvious, why bother to write it up?

I read the description part of the patent which provides some context for how
it came about.

This has to do with a vulnerability in the DSA implementation standard that
was discovered by Daniel Bleichenbacher and announced in November 2000. FIPS
186-2 described generating a 160-bit prime less than some specific 160-bit
prime p by taking the SHA-1 hash of a larger random number (I got it backwards
when I was speculating in my last email) mod p. Bleichenbacher showed an
attack based on the non-uniformity of that result. This was fixed in FIPS
186-2 Change Notice 1, which was later superseded by FIPS 186-4. The original
approach to fixing the problem involved two hashes. Someone people apparently
managed to file for a patent on the idea of doing one hash and discarding
results that were too big before NIST published the change notice with that
method.

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.

FIPS 186-4, unlike FIPS 186-2, does not specify how the random bits are
generated. One way would be to apply a hash that has the requested bit length
output to the output of a PRNG that has the right number of bits of entropy
for the desired security strength. That would make the second method be
impacted by the patent.

 Sidney