Revisiting the Polynomial-Time Equivalence of Computing the CRT-RSA Secret Key and Factoring

Mengce Zheng
Additional contact information
Mengce Zheng: College of Information and Intelligence Engineering, Zhejiang Wanli University, Ningbo 315100, China

Mathematics, 2022, vol. 10, issue 13, 1-21

Abstract: The Rivest–Shamir–Adleman (RSA) cryptosystem is currently the most influential and commonly used algorithm in public-key cryptography. Whether the security of RSA is equivalent to the intractability of the integer factorization problem is an interesting issue in mathematics and cryptography. Coron and May solved the above most fundamental problem and proved the polynomial-time equivalence of computing the RSA secret key and factoring. They demonstrated that the RSA modulus N = p q can be factored in polynomial time when given RSA key information ( N , e , d ) . The CRT-RSA variant is a fast technical implementation of RSA using the Chinese Remainder Theorem (CRT), which aims to speed up the decryption process. We focus on the polynomial-time equivalence of computing the CRT-RSA secret key and factoring in this paper. With the help of the latest partial key exposure attack on CRT-RSA, we demonstrate that there exists a polynomial-time algorithm outputting the factorization of N = p q for e d p , e d q < N 3 / 2 when given the CRT-RSA key information ( N , e , d p , d q ) . We apply Coppersmith’s lattice-based method as a basic mathematical tool for finding the small root solutions of modular polynomial equations. Furthermore, we provide validation experiments to illustrate the correctness of the CRT-RSA modulus factorization algorithm, and show that computing the CRT-RSA secret key and factoring its modulus is polynomial-time equivalent by using concrete numerical examples.

Keywords: CRT-RSA; cryptanalysis; factorization; lattice-based method; polynomial-time equivalence (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/13/2238/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/13/2238/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:13:p:2238-:d:848117

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().