Abstract
We investigate a lattice construction method for the Coppersmith technique for finding small solutions of a modular equation. We consider its variant for simultaneous equations and propose a method to construct a lattice by combining lattices for solving single equations. As applications, we consider a new RSA cryptanalysis. Our algorithm can factor an RSA modulus from ℓ ≥ 2 pairs of RSA public exponents with the common modulus corresponding to secret exponents smaller than N (9ℓ − 5)/(12ℓ + 4), which improves on the previously best known result by Sarkar and Maitra. For partial key exposure situation, we also can factor the modulus if β − δ/2 + 1/4 < (3ℓ − 1)(3ℓ + 1), where β and δ are bit-lengths / logN of the secret exponent and its exposed LSBs, respectively. Due to the spacing limit, some arguments are omitted; see the full-version [1].
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Aono, Y.: Minkowski sum based lattice construction for multivariate simultaneous Coppersmith’s technique and applications to RSA. Cryptology ePrint Archive, 2012/675 (2012)
Aono, Y., Agrawal, M., Satoh, T., Watanabe, O.: On the Optimality of Lattices for the Coppersmith Technique. In: Susilo, W., Mu, Y., Seberry, J. (eds.) ACISP 2012. LNCS, vol. 7372, pp. 376–389. Springer, Heidelberg (2012); The full-version is available online at Cryptology ePrint Archive, 2012/134
Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than N 0.292. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 1–11. Springer, Heidelberg (1999)
Boneh, D., Durfee, G., Frankel, Y.: An attack on RSA given a small fraction of the private key bits. In: Ohta, K., Pei, D. (eds.) ASIACRYPT 1998. LNCS, vol. 1514, pp. 25–34. Springer, Heidelberg (1998)
Blömer, J., May, A.: New partial key exposure attacks on RSA. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 27–43. Springer, Heidelberg (2003)
Blömer, J., May, A.: A tool kit for finding small roots of bivariate polynomials over the integers. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 251–267. Springer, Heidelberg (2005)
Cox, D., Little, J., O’Shea, D.: Ideals, varieties, and algorithms: An introduction to computational algebraic geometry and commutative algebra. Springer, New York (2007)
Coron, J.-S., Naccache, D., Tibouchi, M.: Fault Attacks Against emv Signatures. In: Pieprzyk, J. (ed.) CT-RSA 2010. LNCS, vol. 5985, pp. 208–220. Springer, Heidelberg (2010)
Coppersmith, D.: Finding a small root of a univariate modular equation. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 155–165. Springer, Heidelberg (1996)
Coppersmith, D.: Finding a small root of a bivariate integer equation; factoring with high bits known. In: Maurer, U.M. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 178–189. Springer, Heidelberg (1996)
Ernst, M., Jochemsz, E., May, A., de Weger, B.: Partial key exposure attacks on RSA up to full size exponents. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 371–386. Springer, Heidelberg (2005)
GiNaC is Not a CAS, http://www.ginac.de/
The GNU MP Bignum Library, http://gmplib.org/
Healy, A.D.: Resultants, Resolvents and the Computation of Galois Groups, http://www.alexhealy.net/papers/math250a.pdf
Herrmann, M.: Improved cryptanalysis of the multi-prime Φ-hiding assumption. In: Nitaj, A., Pointcheval, D. (eds.) AFRICACRYPT 2011. LNCS, vol. 6737, pp. 92–99. Springer, Heidelberg (2011)
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)
Hinek, M.J., Lam, C.C.Y.: Common modulus attacks on small private exponent RSA and some fast variants (in practice). Journal of Mathematical Cryptology 4(1), 58–93 (2010)
Herrmann, M., May, A.: Attacking power generators using unravelled linearization: When do we output too much? In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 487–504. Springer, Heidelberg (2009)
Howgrave-Graham, N., Seifert, J.-P.: Extending Wiener’s attack in the presence of many decrypting exponents. In: Baumgart, R. (ed.) CQRE 1999. LNCS, vol. 1740, pp. 153–166. Springer, Heidelberg (1999)
Jochemsz, E., May, A.: A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 267–282. Springer, Heidelberg (2006)
Kunihiro, N., Kurosawa, K.: Deterministic polynomial time equivalence between factoring and key-recovery attack on Takagi’s RSA. In: Okamoto, T., Wang, X. (eds.) PKC 2007. LNCS, vol. 4450, pp. 412–425. Springer, Heidelberg (2007)
Kunihiro, N.: Solving generalized small inverse problems. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010. LNCS, vol. 6168, pp. 248–263. Springer, Heidelberg (2010)
Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515–534 (1982)
Luo, P., Zhou, H.-J., Wang, D.-S., Dai, Y.-Q.: Cryptanalysis of RSA for a special case with d > e. Science in China Series F: Information Sciences 52(4), 609–616 (2009)
May, A.: Cryptanalysis of unbalanced RSA with small CRT-exponent. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 242–256. Springer, Heidelberg (2002)
May, A., Ritzenhofen, M.: Solving systems of modular equations in one variable: How many RSA-encrypted messages does Eve need to know? In: Cramer, R. (ed.) PKC 2008. LNCS, vol. 4939, pp. 37–46. Springer, Heidelberg (2008)
Maitra, S., Sarkar, S.: A New Class of Weak Encryption Exponents in RSA. In: Chowdhury, D.R., Rijmen, V., Das, A. (eds.) INDOCRYPT 2008. LNCS, vol. 5365, pp. 337–349. Springer, Heidelberg (2008)
Shoup, V.: NTL: A Library for doing Number Theory, http://www.shoup.net/ntl/index.html
Nguyen, P.Q., Vallée, B.: The LLL algorithm: Survey and applications. Springer, Berlin (2009)
Ritzenhofen, M.: On efficiently calculating small solutions of systems of polynomial equations: lattice-based methods and applications to cryptography, Ph.D. thesis, Ruhr University Bochum, http://www-brs.ub.ruhr-uni-bochum.de/netahtml/HSS/Diss/RitzenhofenMaike/diss.pdf
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptsystems. Communications of the ACM 21(2), 120–128 (1978)
Sarkar, S., Maitra, S.: Cryptanalysis of RSA with two decryption exponents. Information Processing Letter 110, 178–181 (2010)
Sarkar, S., Maitra, S.: Cryptanalysis of RSA with more than one decryption exponent. Information Processing Letter 110, 336–340 (2010)
Wiener, M.J.: Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory 36(3), 553–558 (1990)
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
Aono, Y. (2013). Minkowski Sum Based Lattice Construction for Multivariate Simultaneous Coppersmith’s Technique and Applications to RSA. In: Boyd, C., Simpson, L. (eds) Information Security and Privacy. ACISP 2013. Lecture Notes in Computer Science, vol 7959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-39059-3_7
Download citation
DOI: https://doi.org/10.1007/978-3-642-39059-3_7
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-39058-6
Online ISBN: 978-3-642-39059-3
eBook Packages: Computer ScienceComputer Science (R0)