SCIENCE CHINA Information Sciences, Volume 61, Issue 3: 032109(2018) https://doi.org/10.1007/s11432-017-9176-5

A better bound for implicit factorization problem with shared middle bits

More info
  • ReceivedFeb 7, 2017
  • AcceptedJun 21, 2017
  • PublishedOct 26, 2017


This paper presents our investigation of the implicit factorization problem,where unknown prime factors of two RSA moduli share a certain number of middle bits.The problem is described as follows.Let $N_1=p_1q_1,~N_2=p_2q_2$ be two different $n$-bit RSA moduli,where $q_1,~q_2$ are both $\alpha~n$-bit prime integers.Suppose that $p_1,~p_2$ share $t~n$ bits at positions from $t_1~n$ to $t_2~n=~(t_1~+t~)n$.Then this problem focuses onthe condition about $t,~\alpha$ to factor $N_1,~N_2$ efficiently.At PKC 2010, Faugère et al. showed that $N_1,~N_2$ can be factored when $t~>~4\alpha$.Subsequently, in 2015, Peng et al. improved this bound to $t~>~4\alpha~-3~{\alpha}^2~$.In this paper,we directly apply Coppersmiths method to the implicit factorization problem with shared middle bits,and a better bound $t~>~4~\alpha~-~4~{\alpha}^{\frac{3}{2}}$ is obtained.The correctness of our approach is verified by experiments.


This work was supported by National Natural Science Foundation of China (Grant Nos. 11531002, 61572026), Basic Research Fund of National University of Defense Technology (Grant No. CJ 13-02-01), Open Foundation of State Key Laboratory of Cryptology, and Program for New Century Excellent Talents in University (NCET).


[1] Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21: 120--126. Google Scholar

[2] Coppersmith D. Finding a small root of a univariate modular equation. In: Advances in Cryptology-EUROCRYPT 1996. Berlin-Heidelberg: Springer, 1996. 155--165. Google Scholar

[3] Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J Cryptol, 1997, 10: 233--260. Google Scholar

[4] Wiener M J. Cryptanalysis of short RSA secret exponents. IEEE Trans Inform Theory, 1990, 36: 553--558. Google Scholar

[5] Boneh D, Durfee G. Cryptanalysis of RSA with private key $d$ less than $N^{0.292}$. In: Advances in Cryptology-EUROCRYPT 1999. Berlin-Heidelberg: Springer, 1999. 1--11. Google Scholar

[6] Boneh D, Durfee G, Frankel Y. An attack on RSA given a small fraction of the private key bits. In: Advances in Cryptology-ASIACRYPT 1998. Berlin-Heidelberg: Springer, 1998. 25--34. Google Scholar

[7] Blomer J, May A. New partial key exposure attacks on RSA. In: Advances in Cryptology-CRYPTO 2003. Berlin-Heidelberg: Springer, 2003. 27--43. Google Scholar

[8] Ernst M, Jochemsz E, May A, et al. Partial key exposure attacks on RSA up to full size exponents. In: Advances in Cryptology-EUROCRYPT 2005. Berlin-Heidelberg: Springer, 2005. 371--386. Google Scholar

[9] Aono Y. A new lattice construction for partial key exposure attack for RSA. In: Public Key Cryptography-PKC 2009. Berlin-Heidelberg: Springer, 2009. 34--53. Google Scholar

[10] Sarkar S, Gupta S S, Maitra S. Partial key exposure attack on RSA-improvements for limited lattice dimensions. In: Progress in Cryptology-INDOCRYPT 2010. Berlin-Heidelberg: Springer, 2010. 2--16. Google Scholar

[11] Sarkar S. Partial key exposure: generalized framework to attack RSA. In: Progress in Cryptology-INDOCRYPT 2011. Berlin-Heidelberg: Springer, 2011. 76--92. Google Scholar

[12] May A. Computing the RSA secret key is deterministic polynomial time equivalent to factoring. In: Advances in Cryptology-CRYPTO 2004. Berlin-Heidelberg: Springer, 2004. 213--219. Google Scholar

[13] Coron J S, May A. Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. J Cryptol, 2007, 20: 39--50. Google Scholar

[14] Luo P, Zhou H J, Wang D S, et al. Cryptanalysis of RSA for a special case with $d~>~e$. Sci China Ser F-Inf Sci, 2009, 52: 609--616. Google Scholar

[15] Zheng M, Hu H, Wang Z. Generalized cryptanalysis of RSA with small public exponent. Sci China Inf Sci, 2016, 59: 032108. Google Scholar

[16] May A, Ritzenhofen M. Implicit factoring: on polynomial time factoring given only an implicit hint. In: Public Key Cryptography-PKC 2009. Berlin-Heidelberg: Springer, 2009. 1--14. Google Scholar

[17] Faugère J C, Marinier R, Renault G. Implicit factoring with shared most significant and middle bits. In: Public Key Cryptography-PKC 2010. Berlin-Heidelberg: Springer, 2010. 70--87. Google Scholar

[18] Coppersmith D. Finding a small root of a bivariate integer equation. Google Scholar

[19] Howgrave-Graham N. Finding small roots of univariate modular equations revisited. In: Darnell M, ed. Crytography and Coding. Berlin: Springer, 1997. 131--142. Google Scholar

[20] Coron J S. Finding small roots of bivariate integer polynomial equations revisited. In: Advances in Cryptology-EUROCRYPT 2004. Berlin-Heidelberg: Springer, 2004. 492--505. Google Scholar

[21] Sarkar S, Maitra S. Approximate integer common divisor problem relates to implicit factorization. IEEE Trans Inform Theory, 2011, 57: 4002--4013. Google Scholar

[22] Lu Y, Zhang R, Lin D. Improved bounds for the implicit factorization problem. Adv Math Commun, 2013, 7: 243--251. Google Scholar

[23] Peng L Q, Hu L, Xu J, et al. Further improvement of factoring RSA moduli with implicit hint. In: Progress in Cryptology-AFRICACRYPT 2014. Berlin: Springer, 2014. 165--177. Google Scholar

[24] Lu Y, Peng L Q, Zhang R, et al. Towards optimal bounds for implicit factorization problem. In: Selected Areas in Cryptography-SAC 2015. Berlin: Springer, 2015. 462--476. Google Scholar

[25] Peng L Q, Hu L, Lu Y, et al. Implicit factorization of RSA moduli revisited (short paper). In: Advances in Information and Computer Security. Berlin: Springer, 2015. 67--76. Google Scholar

[26] Lenstra A K, Lenstra H W, Lov$\mathrm{\acute{a}}$sz L. Factoring polynomials with rational coefficients. Math Ann, 1982, 261: 515--534. Google Scholar

[27] May A. New RSA vulnerabilities using lattice reduction methods. Dissertation for Ph.D. Degree. Paderborn: University of Paderborn, 2003. Google Scholar

[28] Bleichenbacher D, May A. New attacks on RSA with small secret CRT-exponents. In: Public Key Cryptography-PKC 2006. Berlin-Heidelberg: Springer, 2006. 1--13. Google Scholar

  • Figure 1

    Comparison between our result and previous work in [17,25].

  • Table 1   Previous bounds and our contribution to the IFP
    Case [16] [17] [21,22] [23] [24] [25] This paper
    LSBs ($t>\cdot$) $2~\alpha$ $2\alpha-{\alpha}^2$ $4-4\alpha~-4{(1-\alpha)}^{\frac{3}{2}}$ $2\alpha-2{\alpha}^2$
    MSBs ($t>\cdot$) $2~\alpha$ $2\alpha-{\alpha}^2$ $4-4\alpha~-4{(1-\alpha)}^{\frac{3}{2}}$ $2\alpha-2{\alpha}^2$
    Middle bits ($\boldsymbol{t>~\cdot~}$) $\boldsymbol{4~\alpha}$ $\boldsymbol{4~\alpha~-~3~{\alpha}^2}$ $\boldsymbol{4~\alpha~-~4~{\alpha}^{\frac{3}{2}}}$
  • Table 2   The basis matrix $\mathcal{B}$ when $m=3,\tau=2,i=2^{\rm~a)}$
    $h_{j,k}$ $z^2$ $x_1~z$ $x_2~z$ $x_1^2~$ $x_1x_2~$ $x_2^2~$ $x_1^3~y$ $x_1^2x_2~y$ $x_1x_2^2~y$ $x_2^3~y$
    $h_{0,0}$ $N_1^2Z^2$
    $h_{1,0}$ $N_1^2X_1Z$
    $h_{0,1}$ $*$ $*$ $N_1X_2Z$
    $h_{2,0}$ $N_1^2X_1^2$
    $h_{1,1}$ $*$ $*$ $N_1X_1X_2$
    $h_{0,2}$ $*$ $*$ $*$ $*$ $*$ $X_2^2$
    $h_{3,0}$ $N_1^2X_1^3Y$
    $h_{2,1}$ $*$ $*$ $N_1X_1^2X_2Y$
    $h_{1,2}$ $*$ $*$ $*$ $*$ $*$ $X_1X_2^2Y$
    $h_{0,3}$ $*$ $*$ $*$ $*$ $*$ $*$ $*$ $*$ $*$ $X_2^3Y$
    a) Non-zero off-diagonal entries are denoted by *, and blank elements mean zero entries.
  • Table 3   Some experimental results for Theorem
    $n$ $\alpha$ $t$ $t_1$ $t_2$ $m$ $\tau$ $i$ $\dim(\Lambda)$ $\log_2(\det(\Lambda))$ Time for LLL algorithm (s)
    $1000$ $0.250$ $0.650$ $0.050$ $0.700$ $6$ $3$ $3$ $28$ $6.042~\times~10^{4}$ 1.826
    $1500$ $0.230$ $0.670$ $0.020$ $0.690$ $6$ $4$ $2$ $28$ $1.234~\times~10^{5}$ 14.13
    $2000$ $0.270$ $0.630$ $0.075$ $0.705$ $6$ $3$ $3$ $28$ $1.221~\times~10^{5}$ 9.975
    $1000$ $0.310$ $0.660$ $0.010$ $0.670$ $8$ $4$ $4$ $45$ $1.217~\times~10^{5}$ 22.89
    $1500$ $0.290$ $0.640$ $0.020$ $0.660$ $9$ $4$ $5$ $55$ $2.284~\times~10^{5}$ 197.5
    $2000$ $0.300$ $0.650$ $0.030$ $0.680$ $7$ $3$ $4$ $36$ $1.506~\times~10^{5}$ 26.13

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号