February  2019, 13(1): 121-135. doi: 10.3934/amc.2019007

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

1. 

College of Computer, National University of Defense Technology, Changsha 410073, China

2. 

School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore 637371, Singapore

3. 

State Key Laboratory of Cryptology, Beijing 100878, China

4. 

College of Liberal Arts and Sciences, National University of Defense Technology, Changsha 410073, China

* Corresponding author: Longjiang Qu

Received  May 2018 Revised  September 2018 Published  December 2018

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 $\frac{1}{4} \log_2 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_1 p_2 ··· 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_1^{r_1}p_2^{r_2}··· p_n^{r_n}$.

Citation: Shixiong Wang, Longjiang Qu, Chao Li, Huaxiong Wang. Further improvement of factoring $ N = p^r q^s$ with partial known bits. Advances in Mathematics of Communications, 2019, 13 (1) : 121-135. doi: 10.3934/amc.2019007
References:
[1]

D. Boneh, G. Durfee and N. Howgrave-Graham, Factoring $ N = p^r q$ for large $ r$, Advances in Cryptology-CRYPTO 1999, Springer Berlin Heidelberg, 1666 (1999), 326-337. doi: 10.1007/3-540-48405-1_21. Google Scholar

[2]

T. Collins, D. Hopkins, S. Langford and M. Sabin, Public key cryptographic apparatus and method, U.S. Patent, (1998), 5848159.Google Scholar

[3]

D. Coppersmith, Finding a small root of a univariate modular equation, Advances in Cryptology-EUROCRYPT 1996, Springer Berlin Heidelberg, 1070 (1996), 155-165. doi: 10.1007/3-540-68339-9_14. Google Scholar

[4]

D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, Advances in Cryptology-EUROCRYPT 1996, Springer Berlin Heidelberg, 1070 (1996), 178-189. doi: 10.1007/3-540-68339-9_16. Google Scholar

[5]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030. Google Scholar

[6]

J. S. Coron, J. C. Faugère, G. Renault and R. Zeitoun, Factoring $ N = p^rq^s$ for large $ r$ and $ s$, Cryptographers' Track at the RSA Conference, Springer, Cham, 9610 (2016), 448-464. doi: 10.1007/978-3-319-29485-8_26. Google Scholar

[7]

J. S. Coron and R. Zeitoun, Improved factorization of $ N = p^rq^s$, Cryptographers' Track at the RSA Conference, Springer, Cham, 2018, 65-79. Google Scholar

[8]

M. Herrmann and A. May, On factoring arbitrary integers with known bits, IACR Cryptology ePrint Archive, 2007, 374, https://eprint.iacr.org/2007/374.Google Scholar

[9]

M. J. Hinek, On the security of multi-prime RSA, Journal of Mathematical Cryptology, 2 (2008), 117-147. doi: 10.1515/JMC.2008.006. Google Scholar

[10]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Crytography and Coding, Springer Berlin Heidelberg, 1335 (1997), 131-142. doi: 10.1007/BFb0024458. Google Scholar

[11]

N. Howgrave-Graham, Approximate integer common divisors, Cryptography and Lattices, Springer Berlin Heidelberg, 2146 (2001), 51-66. doi: 10.1007/3-540-44670-2_6. Google Scholar

[12]

A. K. LenstraH. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515-534. doi: 10.1007/BF01457454. Google Scholar

[13]

S. Lim, S. Kim, I. Yie and H. Lee, A generalized Takagi-cryptosystem with a modulus of the form $ p^r q^s$, Progress in Cryptology-INDOCRYPT 2000, Springer Berlin Heidelberg, 1977 (2000), 283-294. doi: 10.1007/3-540-44495-5_25. Google Scholar

[14]

Y. Lu, L. Peng and S. Sarkar, Cryptanalysis of an RSA variant with moduli $ N = p^rq^l$, The 9th International Workshop on Coding and Cryptography 2015, WCC 2015.Google Scholar

[15]

A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, Ph.D. thesis, University of Paderborn, 2003.Google Scholar

[16]

R. L. RivestA. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342. Google Scholar

[17]

B. Santoso, N. Kunihiro, N. Kanayama and K. Ohta, Factorization of square-free integers with high bits known, Progress in Cryptology-VIETCRYPT 2006, Springer, Berlin, Heidelberg, 2006,115-130.Google Scholar

[18]

T. Takagi, Fast RSA-type cryptosystem modulo $ p^k q$, Advances in Cryptology-CRYPTO 1998, Springer Berlin Heidelberg, 1998,318-326.Google Scholar

[19]

H. Zhang and T. Takagi, Attacks on multi-prime RSA with small prime difference, Australasian Conference on Information Security and Privacy, Springer, Berlin, Heidelberg, 2013, 41-56.Google Scholar

[20]

M. Zheng, N. Kunihiro and H. Hu, Improved factoring attacks on multi-prime RSA with small prime difference, Australasian Conference on Information Security and Privacy, Springer, Cham, 2017,324-342.Google Scholar

[21]

SageMath, the Sage Mathematics Software System, the Sage Developers, 2018, http://www.sagemath.org.Google Scholar

show all references

References:
[1]

D. Boneh, G. Durfee and N. Howgrave-Graham, Factoring $ N = p^r q$ for large $ r$, Advances in Cryptology-CRYPTO 1999, Springer Berlin Heidelberg, 1666 (1999), 326-337. doi: 10.1007/3-540-48405-1_21. Google Scholar

[2]

T. Collins, D. Hopkins, S. Langford and M. Sabin, Public key cryptographic apparatus and method, U.S. Patent, (1998), 5848159.Google Scholar

[3]

D. Coppersmith, Finding a small root of a univariate modular equation, Advances in Cryptology-EUROCRYPT 1996, Springer Berlin Heidelberg, 1070 (1996), 155-165. doi: 10.1007/3-540-68339-9_14. Google Scholar

[4]

D. Coppersmith, Finding a small root of a bivariate integer equation; factoring with high bits known, Advances in Cryptology-EUROCRYPT 1996, Springer Berlin Heidelberg, 1070 (1996), 178-189. doi: 10.1007/3-540-68339-9_16. Google Scholar

[5]

D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030. Google Scholar

[6]

J. S. Coron, J. C. Faugère, G. Renault and R. Zeitoun, Factoring $ N = p^rq^s$ for large $ r$ and $ s$, Cryptographers' Track at the RSA Conference, Springer, Cham, 9610 (2016), 448-464. doi: 10.1007/978-3-319-29485-8_26. Google Scholar

[7]

J. S. Coron and R. Zeitoun, Improved factorization of $ N = p^rq^s$, Cryptographers' Track at the RSA Conference, Springer, Cham, 2018, 65-79. Google Scholar

[8]

M. Herrmann and A. May, On factoring arbitrary integers with known bits, IACR Cryptology ePrint Archive, 2007, 374, https://eprint.iacr.org/2007/374.Google Scholar

[9]

M. J. Hinek, On the security of multi-prime RSA, Journal of Mathematical Cryptology, 2 (2008), 117-147. doi: 10.1515/JMC.2008.006. Google Scholar

[10]

N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, Crytography and Coding, Springer Berlin Heidelberg, 1335 (1997), 131-142. doi: 10.1007/BFb0024458. Google Scholar

[11]

N. Howgrave-Graham, Approximate integer common divisors, Cryptography and Lattices, Springer Berlin Heidelberg, 2146 (2001), 51-66. doi: 10.1007/3-540-44670-2_6. Google Scholar

[12]

A. K. LenstraH. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515-534. doi: 10.1007/BF01457454. Google Scholar

[13]

S. Lim, S. Kim, I. Yie and H. Lee, A generalized Takagi-cryptosystem with a modulus of the form $ p^r q^s$, Progress in Cryptology-INDOCRYPT 2000, Springer Berlin Heidelberg, 1977 (2000), 283-294. doi: 10.1007/3-540-44495-5_25. Google Scholar

[14]

Y. Lu, L. Peng and S. Sarkar, Cryptanalysis of an RSA variant with moduli $ N = p^rq^l$, The 9th International Workshop on Coding and Cryptography 2015, WCC 2015.Google Scholar

[15]

A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, Ph.D. thesis, University of Paderborn, 2003.Google Scholar

[16]

R. L. RivestA. Shamir and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 21 (1978), 120-126. doi: 10.1145/359340.359342. Google Scholar

[17]

B. Santoso, N. Kunihiro, N. Kanayama and K. Ohta, Factorization of square-free integers with high bits known, Progress in Cryptology-VIETCRYPT 2006, Springer, Berlin, Heidelberg, 2006,115-130.Google Scholar

[18]

T. Takagi, Fast RSA-type cryptosystem modulo $ p^k q$, Advances in Cryptology-CRYPTO 1998, Springer Berlin Heidelberg, 1998,318-326.Google Scholar

[19]

H. Zhang and T. Takagi, Attacks on multi-prime RSA with small prime difference, Australasian Conference on Information Security and Privacy, Springer, Berlin, Heidelberg, 2013, 41-56.Google Scholar

[20]

M. Zheng, N. Kunihiro and H. Hu, Improved factoring attacks on multi-prime RSA with small prime difference, Australasian Conference on Information Security and Privacy, Springer, Cham, 2017,324-342.Google Scholar

[21]

SageMath, the Sage Mathematics Software System, the Sage Developers, 2018, http://www.sagemath.org.Google Scholar

Table 1.  Comparison between the Result in [7] and Our Result when $\log_2 p \approx \log_2 q $
$\log_2 N$ $ r, s $ the Choice of $ u, v $ the Result in [7] Our Result
$5000$ $ 5, 4 $ $ 4, 3$ $ \zeta > 108.0 $ $ \zeta > 61.73 $
$5000$ $ 7, 3 $ $ 5, 2$ $ \zeta > 70.00 $ $ \zeta > 50.00 $
$2000$ $ 3, 2 $ $ 2, 1$ $ \zeta > 120.0 $ $ \zeta > 80.00 $
$2000$ $ 7, 5 $ $ 3, 2$ $ \zeta > 23.15 $ $ \zeta > 13.89 $
$10000$ $ 7, 5 $ $ 3, 2$ $ \zeta > 115.7 $ $ \zeta > 69.44 $
$10000$ $ 13, 12 $ $ 12, 11$ $ \zeta > 30.67 $ $ \zeta > 16.00 $
$\log_2 N$ $ r, s $ the Choice of $ u, v $ the Result in [7] Our Result
$5000$ $ 5, 4 $ $ 4, 3$ $ \zeta > 108.0 $ $ \zeta > 61.73 $
$5000$ $ 7, 3 $ $ 5, 2$ $ \zeta > 70.00 $ $ \zeta > 50.00 $
$2000$ $ 3, 2 $ $ 2, 1$ $ \zeta > 120.0 $ $ \zeta > 80.00 $
$2000$ $ 7, 5 $ $ 3, 2$ $ \zeta > 23.15 $ $ \zeta > 13.89 $
$10000$ $ 7, 5 $ $ 3, 2$ $ \zeta > 115.7 $ $ \zeta > 69.44 $
$10000$ $ 13, 12 $ $ 12, 11$ $ \zeta > 30.67 $ $ \zeta > 16.00 $
Table 2.  Experimental Examples for the Method in [7] and Our Method when $\log_2 p \approx \log_2 q $
$\log_2 N$
$(r,s),\ (u,v) $
Methods Bits Required At Least $m,t_1,t_2$ $\dim(\Lambda)$ Time (LLL Algorithm)
$2000$ [7] $222$ bits $10,9,9$ $11$ $0.189$ seconds
$(3,2),\ (2,1) $ Ours $196$ bits $10,9,10$ $11$ $0.170$ seconds
$2000$ [7] $179$ bits $20,18,18$ $21$ $15.98$ seconds
$(3,2),\ (2,1) $ Ours $141$ bits $20,18,20$ $21$ $8.517$ seconds
$2000$ [7] $162$ bits $30,27,27$ $31$ $264.6$ seconds
$(3,2),\ (2,1) $ Ours $118$ bits $30,27,30$ $31$ $94.78$ seconds
$1000$ [7] $ 33$ bits $36,35,35$ $37$ $36.82$ seconds
$(7,5),\ (3,2) $ Ours $ 30$ bits $36,35,36$ $37$ $31.85$ seconds
$2000$ [7] $132$ bits $16,15,15$ $17$ $0.906$ seconds
$(5,3),\ (2,1) $ Ours $120$ bits $16,15,16$ $17$ $0.557$ seconds
$3000$ [7] $191$ bits $21,20,20$ $22$ $35.49$ seconds
$(4,3),\ (3,2) $ Ours $161$ bits $21,20,21$ $22$ $21.91$ seconds
$\log_2 N$
$(r,s),\ (u,v) $
Methods Bits Required At Least $m,t_1,t_2$ $\dim(\Lambda)$ Time (LLL Algorithm)
$2000$ [7] $222$ bits $10,9,9$ $11$ $0.189$ seconds
$(3,2),\ (2,1) $ Ours $196$ bits $10,9,10$ $11$ $0.170$ seconds
$2000$ [7] $179$ bits $20,18,18$ $21$ $15.98$ seconds
$(3,2),\ (2,1) $ Ours $141$ bits $20,18,20$ $21$ $8.517$ seconds
$2000$ [7] $162$ bits $30,27,27$ $31$ $264.6$ seconds
$(3,2),\ (2,1) $ Ours $118$ bits $30,27,30$ $31$ $94.78$ seconds
$1000$ [7] $ 33$ bits $36,35,35$ $37$ $36.82$ seconds
$(7,5),\ (3,2) $ Ours $ 30$ bits $36,35,36$ $37$ $31.85$ seconds
$2000$ [7] $132$ bits $16,15,15$ $17$ $0.906$ seconds
$(5,3),\ (2,1) $ Ours $120$ bits $16,15,16$ $17$ $0.557$ seconds
$3000$ [7] $191$ bits $21,20,20$ $22$ $35.49$ seconds
$(4,3),\ (3,2) $ Ours $161$ bits $21,20,21$ $22$ $21.91$ seconds
[1]

Henry Cohn, Nadia Heninger. Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. Advances in Mathematics of Communications, 2015, 9 (3) : 311-339. doi: 10.3934/amc.2015.9.311

[2]

Valery Y. Glizer, Oleg Kelis. Asymptotic properties of an infinite horizon partial cheap control problem for linear systems with known disturbances. Numerical Algebra, Control & Optimization, 2018, 8 (2) : 211-235. doi: 10.3934/naco.2018013

[3]

Lingchen Kong, Naihua Xiu, Guokai Liu. Partial $S$-goodness for partially sparse signal recovery. Numerical Algebra, Control & Optimization, 2014, 4 (1) : 25-38. doi: 10.3934/naco.2014.4.25

[4]

Alessandro Ferriero. A direct proof of the Tonelli's partial regularity result. Discrete & Continuous Dynamical Systems - A, 2012, 32 (6) : 2089-2099. doi: 10.3934/dcds.2012.32.2089

[5]

Michele Barbi, Angelo Di Garbo, Rita Balocchi. Improved integrate-and-fire model for RSA. Mathematical Biosciences & Engineering, 2007, 4 (4) : 609-615. doi: 10.3934/mbe.2007.4.609

[6]

Christopher M. Kellett. Classical converse theorems in Lyapunov's second method. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2333-2360. doi: 10.3934/dcdsb.2015.20.2333

[7]

Matthias Eller. A remark on Littman's method of boundary controllability. Evolution Equations & Control Theory, 2013, 2 (4) : 621-630. doi: 10.3934/eect.2013.2.621

[8]

Darya V. Verveyko, Andrey Yu. Verisokin. Application of He's method to the modified Rayleigh equation. Conference Publications, 2011, 2011 (Special) : 1423-1431. doi: 10.3934/proc.2011.2011.1423

[9]

Christopher Bose, Rua Murray. The exact rate of approximation in Ulam's method. Discrete & Continuous Dynamical Systems - A, 2001, 7 (1) : 219-235. doi: 10.3934/dcds.2001.7.219

[10]

Lars Grüne, Peter E. Kloeden, Stefan Siegmund, Fabian R. Wirth. Lyapunov's second method for nonautonomous differential equations. Discrete & Continuous Dynamical Systems - A, 2007, 18 (2&3) : 375-403. doi: 10.3934/dcds.2007.18.375

[11]

Bernd Hofmann, Barbara Kaltenbacher, Elena Resmerita. Lavrentiev's regularization method in Hilbert spaces revisited. Inverse Problems & Imaging, 2016, 10 (3) : 741-764. doi: 10.3934/ipi.2016019

[12]

Roberto Camassa, Pao-Hsiung Chiu, Long Lee, W.-H. Sheu. A particle method and numerical study of a quasilinear partial differential equation. Communications on Pure & Applied Analysis, 2011, 10 (5) : 1503-1515. doi: 10.3934/cpaa.2011.10.1503

[13]

Xin Yu, Guojie Zheng, Chao Xu. The $C$-regularized semigroup method for partial differential equations with delays. Discrete & Continuous Dynamical Systems - A, 2016, 36 (9) : 5163-5181. doi: 10.3934/dcds.2016024

[14]

Ali Hamidoǧlu. On general form of the Tanh method and its application to nonlinear partial differential equations. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 175-181. doi: 10.3934/naco.2016007

[15]

Figen Özpinar, Fethi Bin Muhammad Belgacem. The discrete homotopy perturbation Sumudu transform method for solving partial difference equations. Discrete & Continuous Dynamical Systems - S, 2019, 12 (3) : 615-624. doi: 10.3934/dcdss.2019039

[16]

Chunming Tang, Jinbao Jian, Guoyin Li. A proximal-projection partial bundle method for convex constrained minimax problems. Journal of Industrial & Management Optimization, 2019, 15 (2) : 757-774. doi: 10.3934/jimo.2018069

[17]

Ying Zhang, Ling Ma, Zheng-Hai Huang. On phaseless compressed sensing with partially known support. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-8. doi: 10.3934/jimo.2019014

[18]

Nobuyuki Kato, Norio Kikuchi. Campanato-type boundary estimates for Rothe's scheme to parabolic partial differential systems with constant coefficients. Discrete & Continuous Dynamical Systems - A, 2007, 19 (4) : 737-760. doi: 10.3934/dcds.2007.19.737

[19]

Kun-Jen Chung, Pin-Shou Ting. The inventory model under supplier's partial trade credit policy in a supply chain system. Journal of Industrial & Management Optimization, 2015, 11 (4) : 1175-1183. doi: 10.3934/jimo.2015.11.1175

[20]

Rua Murray. Ulam's method for some non-uniformly expanding maps. Discrete & Continuous Dynamical Systems - A, 2010, 26 (3) : 1007-1018. doi: 10.3934/dcds.2010.26.1007

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (61)
  • HTML views (302)
  • Cited by (0)

Other articles
by authors

[Back to Top]