Abstract
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 1 q 1, N 2 = p 2 q 2 be two different n-bit RSA moduli, where q 1, q 2 are both αn-bit prime integers. Suppose that p 1, p 2 share tn bits at positions from t 1 n to t 2 n = (t 1 + t)n. Then this problem focuses on the condition about t, α 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α. Subsequently, in 2015, Peng et al. improved this bound to t > 4α−3α 2. In this paper, we directly apply Coppersmith’s 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Rivest R L, Shamir A, Adleman L. A method for obtaining digital signatures and public-key cryptosystems. Commun ACM, 1978, 21: 120–126
Coppersmith D. Finding a small root of a univariate modular equation. In: Advances in Cryptology-EUROCRYPT 1996. Berlin-Heidelberg: Springer, 1996. 155–165
Coppersmith D. Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J Cryptol, 1997, 10: 233–260
Wiener M J. Cryptanalysis of short RSA secret exponents. IEEE Trans Inform Theory, 1990, 36: 553–558
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
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
Bl¨omer J, May A. New partial key exposure attacks on RSA. In: Advances in Cryptology-CRYPTO 2003. Berlin-Heidelberg: Springer, 2003. 27–43
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
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
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
Sarkar S. Partial key exposure: generalized framework to attack RSA. In: Progress in Cryptology-INDOCRYPT 2011. Berlin-Heidelberg: Springer, 2011. 76–92
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
Coron J S, May A. Deterministic polynomial-time equivalence of computing the RSA secret key and factoring. J Cryptol, 2007, 20: 39–50
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
Zheng M, Hu H, Wang Z. Generalized cryptanalysis of RSA with small public exponent. Sci China Inf Sci, 2016, 59: 032108
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
Faug`ere 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
Coppersmith D. Finding a small root of a bivariate integer equation; factoring with high bits known. In: Advances in Cryptology-EUROCRYPT 1996. Berlin-Heidelberg: Springer, 1996. 178–189
Howgrave-Graham N. Finding small roots of univariate modular equations revisited. In: Darnell M, ed. Crytography and Coding. Berlin: Springer, 1997. 131–142
Coron J S. Finding small roots of bivariate integer polynomial equations revisited. In: Advances in Cryptology- EUROCRYPT 2004. Berlin-Heidelberg: Springer, 2004. 492–505
Sarkar S, Maitra S. Approximate integer common divisor problem relates to implicit factorization. IEEE Trans Inform Theory, 2011, 57: 4002–4013
Lu Y, Zhang R, Lin D. Improved bounds for the implicit factorization problem. Adv Math Commun, 2013, 7: 243–251
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
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
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
Lenstra A K, Lenstra H W, Lovász L. Factoring polynomials with rational coefficients. Math Ann, 1982, 261: 515–534
May A. New RSA vulnerabilities using lattice reduction methods. Dissertation for Ph.D. Degree. Paderborn: University of Paderborn, 2003
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
Acknowledgements
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).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Wang, S., Qu, L., Li, C. et al. A better bound for implicit factorization problem with shared middle bits. Sci. China Inf. Sci. 61, 032109 (2018). https://doi.org/10.1007/s11432-017-9176-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11432-017-9176-5