A paper I was shown this morning at NSPW reminded me of what seems ancient history, but in fact was only two years ago: PET 2004, in Toronto. In the coffee breaks, Matthias Bauer and I cooked up a plan to find weak PRNGs by searching for PGP keys that had common factors – apparently an early version of PGP had a PRNG that wasn’t much good, so there was some chance it might have generated the same prime for two different key.
So, the way you do this is to take every pair of PGP keys and take the GCD. If they have a common factor, this will be something other than 1 (in fact, it’ll be the common factor, of course). If I remember correctly there were around a million keys at the time, and my laptop (an IBM A31p, at the time) completed the task in about 24 hours.
Sadly, all we found was a pair of keys with common factor 9 – which means both keys were totally broken. Matthias may remember the key IDs if anyone wants to play, but I don’t.
As far as I remember, we never really wrote this up, so I thought I’d mention it here.