Is RSA key generation really worse than DH key generation?
We performed a sanity check of public keys collected on the web. Our main goal was to test the validity of the assumption that different random choices are made each time keys are generated. We found that the vast majority of public keys work as intended. A more disconcerting finding is that two out of every one thousand RSA moduli that we collected offer no security. Our conclusion is that the validity of the assumption is questionable and that generating keys in the real world for "multiple-secrets" cryptosystems such as RSA is significantly riskier than for "single-secret" ones such as ElGamal or (EC)DSA which are based on Diffie-Hellman.
A closer look at the data in the paper, however, suggests a simple explanation for what was observed: at some point (perhaps even continuing through the present day), some implementation of RSA had a bug in it, and that this bug managed to affect the 0.2% of the keys that the paper describes as being weak.
We'll probably find out one day which buggy implementation ended up creating these weak keys, and we'll also almost certainly find out that this implementation of RSA hadn't been validated by a third party.
That's what certifications like FIPS 140-2 give you. They test to make sure that the implementation of their cryptographic algorithms work like they're supposed to, and that was definitely not the case with the weak keys that this paper describes. So maybe that's the best lesson to be learned from this: don't trust that an implementation of ANY security feature is done correctly, and to rely on third-party validations that security features are indeed correct.
But if it turns out that the buggy implementation was indeed validated, well, that's when things could start to get interesting.