• How to counter the security risks of shared prime factors among RSA mod

    From Mok-Kong Shen@21:1/5 to All on Thu Jan 14 08:28:01 2016
    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)