Further improvement of factoring N = p r q s with partial known bits

We revisit the factoring with known bits problem on RSA moduli. In 1996, Coppersmith showed that the RSA modulus N = pq with balanced p, q can be efficiently factored, if the high order ¼log₂ N bits of one prime factor is given. Later, this important result is also generalized to the factorization of RSA variants moduli such as N = p r q or N = p₁ p₂ · · · p n. In 2000, Lim et al. proposed a new RSA variant with the modulus of the form N = p r q s, which is much faster in the decryption process than the standard RSA. Then from 2015 to 2018, in order to investigate the security property of this RSA variant, Lu et al. and Coron et al. have presented three works studying the polynomial-time factorization of N = p r q s with partial known bits of p u q v (or one of the prime factors p, q) for different choices of u, v. In this paper, we present a new lattice construction used for Coppersmith’s method, and thus improve previous results. Namely, our result requires fewer known bits to recover the prime factors p, q. We also generalize our result to the factorization of N = p₁ r1 p₂ r2 · · · pn rn.The work in this paper is supported by the National Natural Science Foundation of China (Grant Nos. 11531002, 61572026 and 61722213), the Open Foundation of State Key Laboratory of Cryptology (Grant No. MMKFKT201617), and the program of China Scholarship Council (CSC) (No. 201703170302)