How to counter the security risks of shared prime factors among RSA moduli employed in pra...

Do you have a question? Post it now! No Registration Necessary.  Now with pictures!

A. K. Lenstra et al. in an extensive examination of the RSA moduli used in
practice ( , 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  
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  
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, /). 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

Site Timeline