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
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.
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.
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

Page view(s)

Updated on Oct 16, 2021

Google ScholarTM




Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.