[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:

https://freedom-to-tinker.com/blog/nadiah/new-research-theres-no-need-panic-over-factorable-keys-just-mind-your-ps-and-qs

Explains how it can be done in linear time.



More information about the cryptography mailing list