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 o...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/151173 |
| _version_ | 1826113019339341824 |
|---|---|
| author | Wang, Shixiong Qu, Longjiang Li, Chao Wang, Huaxiong |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Wang, Shixiong Qu, Longjiang Li, Chao Wang, Huaxiong |
| author_sort | Wang, Shixiong |
| collection | NTU |
| description | 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. |
| first_indexed | 2024-10-01T03:16:38Z |
| format | Journal Article |
| id | ntu-10356/151173 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T03:16:38Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | ntu-10356/1511732021-06-11T06:42:31Z Further improvement of factoring N = p r q s with partial known bits Wang, Shixiong Qu, Longjiang Li, Chao Wang, Huaxiong School of Physical and Mathematical Sciences Science::Mathematics RSA Variant 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). 2021-06-11T06:42:31Z 2021-06-11T06:42:31Z 2019 Journal Article 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 1930-5346 https://hdl.handle.net/10356/151173 10.3934/amc.2019007 2-s2.0-85060448507 1 13 121 135 en Advances in Mathematics of Communications © 2019 AIMS. All rights reserved. |
| spellingShingle | Science::Mathematics RSA Variant Partial Known Bits Wang, Shixiong Qu, Longjiang Li, Chao Wang, Huaxiong Further improvement of factoring N = p r q s with partial known bits |
| title | Further improvement of factoring N = p r q s with partial known bits |
| title_full | Further improvement of factoring N = p r q s with partial known bits |
| title_fullStr | Further improvement of factoring N = p r q s with partial known bits |
| title_full_unstemmed | Further improvement of factoring N = p r q s with partial known bits |
| title_short | Further improvement of factoring N = p r q s with partial known bits |
| title_sort | further improvement of factoring n p r q s with partial known bits |
| topic | Science::Mathematics RSA Variant Partial Known Bits |
| url | https://hdl.handle.net/10356/151173 |
| work_keys_str_mv | AT wangshixiong furtherimprovementoffactoringnprqswithpartialknownbits AT qulongjiang furtherimprovementoffactoringnprqswithpartialknownbits AT lichao furtherimprovementoffactoringnprqswithpartialknownbits AT wanghuaxiong furtherimprovementoffactoringnprqswithpartialknownbits |