[Cryptography] How to counter the security risks of shared prime factors among RSA moduli employed in practice?

[mok-kong shen]

A. K. Lenstra et al. in an extensive examination of the RSA moduli used in
practice (http://infoscience.epfl.ch/record/174943/files/eprint.pdf, p.10)
wrote that they "could not explain the relative frequencies and apprearance
of the occurrence of duplicate RSA moduli and depth one trees" found in
their study.

How could the high security risks arising from this direction be effectively
countered in the current actual practice of RSA applications on the 
Internet?

It is obvious that with the fairly large size of the RSA moduli investigated
in the study, the probability of occurrence of shared prime factors in the
moduli should be very very small, if the software used is appropriately and
correctly written at all. Hence IMHO a highly possible, not to be ignored,
cause of the phenomenon reported could be that a certain non-open-source
RSA key generation software employed in practice contains a backdoor. With
PRNGs it is namely very simple to specify a set of N prime numbers (without
having to explicitly store them in the software) to be pseudo-randomly
selected for use in an RSA key generation session. N could be chosen by the
malice to his advantage to be fairly large without causing difficulties to
his purposes. For the set of N prime numbers can be all pre-generated by 
him,
forming a list at his disposal to probe a given RSA modulus in order to find
his prime factor in case the modulus happens to have been generated by the
RSA software that contains his backdoor.

In view of the comparatively simple algorithmus involved, obviously it isn't
difficult from the viewpoint of software engineering to specify an RSA key
generation (reference) program unit in simple, sufficiently detailed
pseudo-code (cf. AES standard) that has a standard interface to its
environment. If this is ISO standardized, open-source implementations could
be certified independently by national standardization bodies and/or IT
professional associations of diverse countries of the world. While there is
nothing 100.00% perfect in the real world (excepting certain mathematical
theories that are logically impacable, though still contingent on their
axioms), the trustworthiness of such implementations will obviously become
higher, when their number of certifications obtained increases. In this
situation, at least a common end user doing encryption/decryption of his
personal communications could easily have a choice for his RSA key 
generation
between such a certified implementation (which may not run very fast) and
another implementation that is not certified but runs faster and has lots
of convenience features.

M. K. Shen