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

• Main Authors: Wang, Shixiong, Qu, Longjiang, Li, Chao, Wang, Huaxiong
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2021
• Subjects: Science::Mathematics; RSA Variant; Partial Known Bits
• Online Access: https://hdl.handle.net/10356/151173
• Institution: Nanyang Technological University

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.