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

   Authors: Vladimir Sedlacek, Dusan Klinec, Marek Sys, Petr Svenda, Vashek Matyas

 Primary contact: Vladimir Sedlacek <vlada.sedlacek@mail.muni.cz>

 Conference: 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.

We acknowledge the support of the Czech Science Foundation, project GA16-08565S. V.Sedlacek was also supported by the Brno Ph.D. Talent Scholarship (funded by the Brno City Municipality). The access to the computing and storage resources of National Grid Infrastructure MetaCentrum (LM2010005) is greatly appreciated.