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

Shixiong Wang; Longjiang Qu; Chao Li; Huaxiong Wang

doi:10.3934/amc.2019007

Article Contents

2019, Volume 13, Issue 1: 121-135. Doi: 10.3934/amc.2019007

This issue Previous Article Maximum weight spectrum codes Next Article The weight distribution of a class of p-ary cyclic codes and their applications

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
* Corresponding author: Longjiang Qu

Received: May 2018

Revised: September 2018

Published: December 2018

Abstract / Introduction Full Text(HTML) Figure(0) / Table(2) Related Papers Cited by

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 $\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}$.

Keywords:

Mathematics Subject Classification: Primary: 11Y05; Secondary: 94A60.

Citation:

Full Text(HTML)

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 $

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.
[2]	T. Collins, D. Hopkins, S. Langford and M. Sabin, Public key cryptographic apparatus and method, U.S. Patent, (1998), 5848159.
[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.
[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.
[5]	D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities, Journal of Cryptology, 10 (1997), 233-260. doi: 10.1007/s001459900030.
[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.
[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.
[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.
[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.
[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.
[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.
[12]	A. K. Lenstra, H. W. Lenstra and L. Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, 261 (1982), 515-534. doi: 10.1007/BF01457454.
[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.
[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.
[15]	A. May, New RSA Vulnerabilities Using Lattice Reduction Methods, Ph.D. thesis, University of Paderborn, 2003.
[16]	R. L. Rivest, A. 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.
[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.
[18]	T. Takagi, Fast RSA-type cryptosystem modulo $ p^k q$, Advances in Cryptology-CRYPTO 1998, Springer Berlin Heidelberg, 1998,318-326.
[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.
[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.
[21]	SageMath, the Sage Mathematics Software System, the Sage Developers, 2018, http://www.sagemath.org.