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

Pre-print PDF

BiBTeX 

@Article{2019-secrypt-sedlacek,
  Title = {I want to break square-free: The 4p-1 factorization method and its RSA backdoor viability},
  Author = {Vladimir Sedlacek, Dusan Klinec, Marek Sys, Petr Svenda, Vashek Matyas},
  booktitle = {14th International Conference on Security and Cryptography (Secrypt'2017)},
  Year = {2019},
  publisher = {SCITEPRESS}
}

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.

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.