Abstract
This paper investigates the problem of factoring RSA modulus N = pq with some known bits from both p and q. In Asiacrypt’08, Herrmann and May presented a heuristic algorithm to factorize N with the knowledge of a random subset of the bits (distributed over small contiguous blocks) of a factor. However, in a real attack, an adversary often obtain some bits which distributed in both primes. This paper studies this extended setting and introduces a lattice-based approach. Our strategy is an extension of Coppersmiths technique on more variables, thus it is a heuristic method, which we heuristically assumed that the polynomials resulting from the lattice basis reduction are algebraically independent. However, in our experiments, we have observed that the well-established assumption is not always true, and for these scenarios, we also propose a method to fix it.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than n 0.292. IEEE Transactions on Information Theory 46(4), 1339–1349 (2000)
Cannon, J., et al.: Magma computional algebraic sydstem (version: V2. 12-16) (2012), http://magma.maths.usyd.edu.au/magma/
Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology 10(4), 233–260 (1997)
Halderman, J.A., Schoen, S.D., Heninger, N., Clarkson, W., Paul, W., Calandrino, J.A., Feldman, A.J., Appelbaum, J., Felten, E.W.: Lest we remember: cold-boot attacks on encryption keys. Communications of the ACM 52(5), 91–98 (2009)
Heninger, N., Shacham, H.: Reconstructing RSA private keys from random key bits. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 1–17. Springer, Heidelberg (2009)
Herrmann, M., May, A.: Solving linear equations modulo divisors: On factoring given any bits. In: Pieprzyk, J. (ed.) ASIACRYPT 2008. LNCS, vol. 5350, pp. 406–424. Springer, Heidelberg (2008)
Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Darnell, M. (ed.) Cryptography and Coding 1997. LNCS, vol. 1355, pp. 131–142. Springer, Heidelberg (1997)
Jochemsz, E., May, A.: A polynomial time attack on RSA with private CRT-exponents smaller than n 0.073. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 395–411. Springer, Heidelberg (2007)
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515–534 (1982)
May, A.: New RSA vulnerabilities using lattice reduction methods. PhD thesis (2003)
Rivest, R.L., Shamir, A.: Efficient factoring based on partial information. In: Pichler, F. (ed.) EUROCRYPT 1985. LNCS, vol. 219, pp. 31–34. Springer, Heidelberg (1986)
Sarkar, S.: Partial key exposure: Generalized framework to attack RSA. In: Bernstein, D.J., Chatterjee, S. (eds.) INDOCRYPT 2011. LNCS, vol. 7107, pp. 76–92. Springer, Heidelberg (2011)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lu, Y., Zhang, R., Lin, D. (2013). Factoring RSA Modulus with Known Bits from Both p and q: A Lattice Method. In: Lopez, J., Huang, X., Sandhu, R. (eds) Network and System Security. NSS 2013. Lecture Notes in Computer Science, vol 7873. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38631-2_29
Download citation
DOI: https://doi.org/10.1007/978-3-642-38631-2_29
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38630-5
Online ISBN: 978-3-642-38631-2
eBook Packages: Computer ScienceComputer Science (R0)