I Want to Break Square-free: The 4p - 1 Factorization Method and Its RSA Backdoor Viability

摘要

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. We devise three detection methods for such a backdoor and also audit 44 millions of RSA keypairs generated by 18 different types of cryptographic devices. Finally, we present an improved, simplified and asymptotically deterministic version of the method, together with a deeper analysis of its performance and we offer a public implementation written in Sage.