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.
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 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.
Obviously it isn't difficult from the viewpoint of software engineering to specify (cf. AES and AESAVS of NIST) an RSA key generation program unit that has a standard interface to its environment. If this is ISO standardized, 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.
There are certainly a vast number of applications where CAs are practically necessarily to be invoved. This leads to the IMHO verily difficult issue of trust on the CAs (their cooperations with one another, the faithfulness and correctness of the work of their employees, attempts of third parties to excercise diverse malicious influences on their work, etc.) However, if the goal sketched above of the certification of RSA key generation software
could be satisfactoriy achieved, then that's already an extremely essential achievement in countering the security risks currently facing the common
end users resulting from the phenomenon of shared prime factors among RSA moduli employed in practice. Improvements in the issues related to the CAs could be strived at simultaneously, but preferrably with a comparatively
lower priority in my personal opinion.
It may be remarked that backdoors of the genre described above are actually
of a comparatively simple nature. Much more sophisticated and practically impossible to be detected backdoors in non-open-source RSA key generation software are conceivable. One idea of designing such backdoors, sketched by maartin many years ago, was recently explained by me in details in the
Epilogue of a software of mine (PROVABLEPRIME,
http://s13.zetaboards.com/Crypto/topic/7234475/1/). The security risks
stemming from this direction are IMHO more hideous and lie clearly beyond
the feasible realm of studies of the kind done by A. K. Lenstra et al.
M. K. Shen
--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)