I Want to Break Square-free: The 4p − 1 Factorization Method and Its RSA Backdoor Viability
Vladimír Sedláček, Dušan Klinec, Marek Sýs, Petr Švenda, Vashek Matyáš · 2019
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).