Please use this identifier to cite or link to this item:
https://hdl.handle.net/10356/151173
Title: | Further improvement of factoring N = p r q s with partial known bits | Authors: | Wang, Shixiong Qu, Longjiang Li, Chao Wang, Huaxiong |
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 | Schools: | School of Physical and Mathematical Sciences | Rights: | © 2019 AIMS. All rights reserved. | Fulltext Permission: | none | Fulltext Availability: | No Fulltext |
Appears in Collections: | SPMS Journal Articles |
SCOPUSTM
Citations
50
2
Updated on Mar 26, 2024
Web of ScienceTM
Citations
50
2
Updated on Oct 30, 2023
Page view(s)
156
Updated on Mar 29, 2024
Google ScholarTM
Check
Altmetric
Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.