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 this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview 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)