Revisiting the Polynomial-Time Equivalence of Computing the CRT-RSA Secret Key and Factoring
Mengce Zheng · Mathematics · 2022
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=pq 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=pq for edp,edq