[cryptography] Duplicate primes in lots of RSA moduli

Jonathan Katz jkatz at cs.umd.edu
Wed Feb 15 22:34:55 EST 2012

On Wed, 15 Feb 2012, Steven Bellovin wrote:

> On Feb 15, 2012, at 11:56 45AM, Ben Laurie wrote:
>> I did this years ago for PGP keys. Easy: take all the keys, do
>> pairwise GCD. Took 24 hours on my laptop for all the PGP keys on
>> keyservers at the time. I'm trying to remember when this was, but I
>> did it during PETS at Toronto, so that should narrow it down. With
>> Matthias XXX (I've forgotten his surname!).
> How many keys?  They had 11M keys, meaning there are 121e12 pairs.  That's
> a lot of GCD operations...

The blog post here:


Explains how it can be done in linear time.

More information about the cryptography mailing list