[cryptography] Duplicate primes in lots of RSA moduli

Ralph Holz holz at net.in.tum.de
Wed Feb 15 06:25:55 EST 2012


>> Paper by Lenstra, Hughes, Augier, Bos, Kleinjung, and Wachter finds that two
>> 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.
> The title of the paper "Ron was wrong, Whit is right" I think is rather
> misleading, since virtually all the DSA keys were PGP-generated and there was
> only one ECDSA key, while there were vast numbers of RSA keys from all manner
> of software.  So what it should really say is "PGP got DSA keygen right, the
> sample size for ECDSA is too small to make any meaingful comment, and some RSA
> implementations aren't so good".

Their survey seems to be very nice work. But they reach this conclusion
in the abstract that RSA is "significantly riskier" than ElGamal/DSA. In
the body of the paper, they indicate (although they are much more
defensive already) that this is due to the fact that you need two
factors and more randomness to go into the key creation. The larger
number of weak RSA keys is then taken as an indication that this is
inherently a problem of RSA. It's a leap. If you need more input, more
can go wrong; but it does not seem conclusive evidence here. It would be
conclusive if they compared keys created with the help of the same
source of randomness and primality testers.

Interestingly, in their own conclusions section they do not reiterate
the above statement.


Ralph Holz
Network Architectures and Services
Technische Universität München
PGP: A805 D19C E23E 6BBB E0C4  86DC 520E 0C83 69B0 03EF

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 490 bytes
Desc: OpenPGP digital signature
URL: <http://lists.randombit.net/pipermail/cryptography/attachments/20120215/7842c0da/attachment.asc>

More information about the cryptography mailing list