I want to break square-free: The 4p-1 factorization method and its RSA backdoor viability [SeCrypt 2019]

  @conference{secrypt19,
   author={Vladimir Sedlacek and Dusan Klinec and Marek Sys and Petr Svenda and Vashek Matyas.},
   title={I Want to Break Square-free: The 4p − 1 Factorization Method and Its RSA Backdoor Viability},
   booktitle={Proceedings of the 16th International Joint Conference on e-Business and Telecommunications (ICETE 
   2019) - Volume 2: SECRYPT,},
   year={2019},
   pages={25-36},
   publisher={SciTePress},
   organization={INSTICC},
   doi={10.5220/0007786600250036},
   isbn={978-989-758-378-0},
  }

Abstract:

In this paper, we analyze Cheng's $4p-1$ factorization method as the means of a potential backdoor for the RSA primes generated inside black-box devices like cryptographic smartcards, and we devise three detection methods for such a backdoor. We also audit 44 millions of RSA keypairs generated by 18 different types of cryptographic devices. Finally, we offer an improved, simplified and asymptotically deterministic version of the method, together with a deeper analysis of its performance and we publish a Sage implementation (we are currently not aware of any other public implementation).

The contributions of the paper are the following:

• We analyze and improve a factorization method of integers of special form pq, where p,q are primes and the square-free part of 4p-1 is small. If an RSA key is generated in this form, an attacker can easily factor a modulus with bit length 2048 (and even more).
• If an RSA key is generated properly, such vulnerability almost never occurs. Thus if such a vulnerability is present, it was intentionally created.
• We devised and analyzed several possible methods of detecting such a backdoor and applied these on 44 millions of RSA keypairs generated by 18 different types of cryptographic devices.
• Even though we did not find any indication of a backdoor on the examined devices, we showed that generating vulnerable keys is possible by a clever attacker.

• Factorization implementation, testing code and more

We acknowledge the support of the Czech Science Foundation, project GA16-08565S. The access to the computing and storage resources of National Grid Infrastructure MetaCentrum (LM2010005) is greatly appreciated.