[cryptography] Duplicate primes in lots of RSA moduli

Steven Bellovin smb at cs.columbia.edu
Tue Feb 14 20:58:52 EST 2012

On Feb 14, 2012, at 7:50 14PM, Michael Nelson wrote:

> Paper by Lenstra, Hughes, Augier, Bos, Kleinjung, and Wachter finds that two out of every one thousand RSA moduli that they collected from the web offer no security.  An astonishing number of generated pairs of primes have a prime in common.  Once again, it shows the importance of proper randomness (my remark).
> http://www.nytimes.com/2012/02/15/technology/researchers-find-flaw-in-an-online-encryption-method.html?_r=1&hp
> The paper:
> http://eprint.iacr.org/2012/064.pdf

The practical import is unclear, since there's (as far as is known) no
way to predict or control who has a bad key.

To me, the interesting question is how to distribute the results.  That
is, how can you safely tell people "you have a bad key", without letting
bad guys probe your oracle.  I suspect that the right way to do it is to
require someone to sign a hash of a random challenge, thereby proving
ownership of the private key, before you'll tell them if the
corresponding public key is in your database.

		--Steve Bellovin, https://www.cs.columbia.edu/~smb

More information about the cryptography mailing list