[cryptography] Duplicate primes in lots of RSA moduli

Ben Laurie ben at links.org
Thu Feb 16 15:59:15 EST 2012

On Thu, Feb 16, 2012 at 7:12 PM, Jeffrey I. Schiller <jis at qyv.net> wrote:
> Hash: SHA1
> On 02/16/2012 01:00 PM, Ben Laurie wrote:
>> However, if line 3 was omitted, then something much worse would
>> happen: if a process forked, then the new process would produce the
>> same PRNG stream as the old one.
>> The problem with the pseudo-code is it doesn't reflect what's really
>> going on (the text explains it, but not why it does it). The purpose
>> of the "extra entropy" is to make the two PRNG streams different, not
>> to increase entropy. You're supposed to have sufficient entropy in the
>> first place.
> But in this particular case (admittedly a degenerate case of poor
> entropy) it makes things worse. I don't understand your comment about
> the process forking. Presumably it shouldn't do this between the two
> calls to generate_random_prime.

I will quote the text you have obviously not bothered to read:

"OpenSSL's RSA key generation functions this way: each time random
bits are produced from the entropy pool to generate the primes p and
q, the current time in seconds is added to the entropy pool."

Or you could read the code.

> As for ensuring that bits are not
> reused, the random state should be tossed and regenerated after the key
> is generated. As I recall, the source for PGP 5.0 did something like this.

I challenge you to give a good justification for this strategy.

> Another way to think about it is to replace generate_random_prime with a
> new function "generate_two_random_primes" that does one call to fetch
> random bits (as long as the modulus), splits the bit-stream itself and
> then uses each half to search/sieve for the next prime number.

More useful would be to allow code to say to OpenSSL "I promise I will
do the right thing when I fork or otherwise replicate state, so don't
bother to mix in extra stuff".

For performance reasons.

As for "one call to fetch random bits" - how do you propose OpenSSL
does this, in general? On an embedded platform? OpenSSL assumes it
gets low quality entropy and adds its own mixing on top of that.

More information about the cryptography mailing list