[cryptography] Duplicate primes in lots of RSA moduli

Jeffrey I. Schiller jis at qyv.net
Thu Feb 16 21:42:30 EST 2012

Hash: SHA1

On 02/16/2012 03:59 PM, Ben Laurie wrote:
> 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.

I've read the code, I know how it works... That's my point. By adding
additional entropy (in this case the time) between the generation of P
and Q you setup a situation where it is more likely that two hosts
will share a P but not a Q. Without that additional entropy P and Q
would likely be the same.

I'm not placing blame or finding fault. As I said, it is counter
intuitive that adding entropy would ever be a bad thing. But then no
one anticipated this particular attack vector. In fact I am quite
surprised (though probably I shouldn't be) that there are devices
where the entropy is/was so low that identical values would be chosen!

>> 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.

I was probably less precise in my wording then I should have
been. What I mean is that once P and Q are generated, the state of the
pseudo random number generator should be destroyed and never used
again. Although in theory it shouldn't be possible to determine
previous state from current state (i.e., run it backwards to determine
P and Q based on the state when it was done doing so) it is probably
safer to assume that the previous state can be derived.


- --
Jeffrey I. Schiller
MIT Technologist, Consultant, and Cavy Breeder
Cambridge, MA 02139-4307
617.910.0259 - Voice
jis at qyv.net

Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/


More information about the cryptography mailing list