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.
_______________________________________________
cryptography mailing list
cryptography@randombit.net
http://lists.randombit.net/mailman/listinfo/cryptography
