[cryptography] Duplicate primes in lots of RSA moduli
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