[cryptography] Duplicate primes in lots of RSA moduli

Jeffrey I. Schiller jis at qyv.net
Thu Feb 16 14:12:43 EST 2012


-----BEGIN PGP SIGNED MESSAGE-----
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. 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.

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.

			-Jeff


- -- 
_______________________________________________________________________
Jeffrey I. Schiller
MIT Technologist, Consultant, and Cavy Breeder
Cambridge, MA 02139-4307
617.910.0259 - Voice
jis at qyv.net
http://jis.qyv.name
_______________________________________________________________________
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/

iD8DBQFPPVUl8CBzV/QUlSsRAoCXAJ9pYSv6Cnt53GlmWA+EQppMVuYjXwCdGo8y
AINMfFzQK/tdMMGNWe0t648=
=unTZ
-----END PGP SIGNATURE-----



More information about the cryptography mailing list