Hundreds of RSA keys factored

[Timo]

There is this scary project listing several hundreds factored pgp/rsa
keys: http://trilema.com/2016/the-phuctoring/

Quote:
"This find exposes significant vulnerabilities in the OpSec practices of
each and every organisation or institution mentioned. The Pirate Party,
German users, something calling itself "The PGP Corporation", the FSF
and Apple particularly badly hit.

Phuctor will continue as a free, open and public service in the
indefinite future. Feel free to verify your future keys against the
ever-growing database. Special thanks to Mr. D. J. Bernstein for
refinements to the algorithm that allowed us to reduce the required
workload considerably.ii"

In theory the software generating the keys should check the generated
primes using algorithms like the Miller-Rabin-Test, which would return
with near perfect security whether the number is prime or not.

On the site I noticed that many of the keys that use nonprime numbers
are generated by gnupg. Given that there are only a few million pgp keys
on the public keyservers and the likelihood of the Rabin-Miller-Test
failing is way lower than this result shown by the mentioned site,
should it not be assumed that there is something wrong with the
implementation?

Maybe someone can put the pieces together for me to understand how this
is possible.

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: OpenPGP digital signature
URL: </pipermail/attachments/20160504/ffab2147/attachment.sig>