Please use this identifier to cite or link to this item:
|Title:||Further improvement of factoring N = p r q s with partial known bits||Authors:||Wang, Shixiong
|Keywords:||Science::Mathematics||Issue Date:||2019||Source:||Wang, S., Qu, L., Li, C. & Wang, H. (2019). Further improvement of factoring N = p r q s with partial known bits. Advances in Mathematics of Communications, 13(1), 121-135. https://dx.doi.org/10.3934/amc.2019007||Journal:||Advances in Mathematics of Communications||Abstract:||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.||URI:||https://hdl.handle.net/10356/151173||ISSN:||1930-5346||DOI:||10.3934/amc.2019007||Rights:||© 2019 AIMS. All rights reserved.||Fulltext Permission:||none||Fulltext Availability:||No Fulltext|
|Appears in Collections:||SPMS Journal Articles|
Updated on Oct 16, 2021
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.