This is an old revision of the document!
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 - 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).
Key insights
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.
Other materials
Acknowledgements
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.