Abstract
In this paper, we study the security of RSA when there are multiple public/secret exponents (e 1,d 1), …, (e n ,d n ) with the same public modulus N. We assume that all secret exponents are smaller than N β. When n = 1, Boneh and Durfee proposed a polynomial time algorithm to factor the public modulus N. The algorithm works provided that \( \beta<1-1/\sqrt{2}\). So far, several generalizations of the attacks for arbitrary n have been proposed. However, these attacks do not achieve Boneh and Durfee’s bound for n = 1. In this paper, we propose an algorithm which is the exact generalization of Boneh and Durfee’s algorithm. Our algorithm works when \( \beta<1-\sqrt{2/(3n+1)}\). Our bound is better than all previous results for all n ≥ 2. We construct the lattices by collecting as many helpful polynomials as possible. The collections reduce the volume of the lattices and enable us to improve the bound.
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.: A new lattice construction for partial key exposure attack for RSA. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 34–53. Springer, Heidelberg (2009)
Aono, Y.: Minkowski Sum Based Lattice Construction for Multivariate Simultaneous Coppersmith’s Technique and Applications to RSA. In: Boyd, C., Simpson, L. (eds.) ACISP. LNCS, vol. 7959, pp. 88–103. Springer, Heidelberg (2013), http://eprint.iacr.org/2012/675
Blömer, J., May, A.: Low secret exponent RSA revisited. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 4–19. Springer, Heidelberg (2001)
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)
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.: Exposing an RSA private key given a small fraction of its bits. In: ASIACRYPT 1998. LNCS, vol. 1514, pp. 25–34. Springer, Heidelberg (1998)
Cohn, H., Heninger, N.: Approximate common divisors via lattices. In: 10th Algorithmic Number Theory Symposium ANTS-X, 2012. Longer version available as IACR Cryptology ePrint Archive, Report 2011/437 (2011), http://eprint.iacr.org/2011/437
Coppersmith, D.: Finding a Small Root of a univariate modular Equation. In: Maurer, U.M. (ed.) Advances in Cryptology - 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. (ed.) Advances in Cryptology - EUROCRYPT 1996. LNCS, vol. 1070, pp. 178–189. Springer, Heidelberg (1996)
Coppersmith, D.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology 10(4), 233–260 (1997)
Coppersmith, D.: Finding small solutions to small degree polynomials. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 20–31. Springer, Heidelberg (2001)
Coron, J.-S.: Finding Small Roots of Bivariate Integer Equations Revisited. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 492–505. Springer, Heidelberg (2004)
Coron, J.-S.: Finding Small Roots of Bivariate Integer Equations: A Direct Approach. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 379–394. Springer, Heidelberg (2007)
Durfee, G., Nguyên, P.Q.: Cryptanalysis of the RSA Schemes with Short Secret Exponent from Asiacrypt ’99. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 14–29. Springer, Heidelberg (2000)
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)
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)
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)
Herrmann, M., May, A.: Maximizing Small Root Bounds by Linearization and Applications to Small Secret Exponent RSA. In: Nguyen, P.Q., Pointcheval, D. (eds.) PKC 2010. LNCS, vol. 6056, pp. 53–69. Springer, Heidelberg (2010)
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)
Howgrave-Graham, N.: Approximate integer common divisors. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 51–66. Springer, Heidelberg (2001)
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)
Itoh, K., Kunihiro, N., Kurosawa, K.: Small Secret Key Attack on a Variant of RSA (due to Takagi). In: Malkin, T. (ed.) CT-RSA 2008. LNCS, vol. 4964, pp. 387–406. Springer, Heidelberg (2008)
Itoh, K., Kunihiro, N., Kurosawa, K.: Small Secret Key Attack on a Takagi’s Variant of RSA. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sceiences E92-A(1), 33–41 (2008)
Jochemsz, E., May, A.: A Strategy for Finding Roots of Multivariate Polynomials. In: Lai, X., Chen, K. (eds.) ASIACRYPT 2006. LNCS, vol. 4284, pp. 267–282. Springer, Heidelberg (2006)
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)
Kunihiro, N.: Solving Generalized Small Inverse Problems. In: Steinfeld, R., Hawkes, P. (eds.) ACISP 2010. LNCS, vol. 6168, pp. 248–263. Springer, Heidelberg (2010)
Kunihiro, N.: On Optimal Bounds of Small Inverse Problems and Approximate GCD Problems with Higher Degree. In: Gollmann, D., Freiling, F.C. (eds.) ISC 2012. LNCS, vol. 7483, pp. 55–69. Springer, Heidelberg (2012)
Kunihiro, N., Shinohara, N., Izu, T.: A Unified Framework for Small Secret Exponent Attack on RSA. In: Miri, A., Vaudenay, S. (eds.) SAC 2011. LNCS, vol. 7118, pp. 260–277. Springer, Heidelberg (2012)
Lenstra, A.K., Lenstra Jr., H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 515–534 (1982)
May, A.: Secret Exponent Attacks on RSA-type Schemes with Moduli N = p r q. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 218–230. Springer, Heidelberg (2004)
May, A.: Using LLL-reduction for solving RSA and factorization problems: A survey. In: NV10 (2007), http://www.cits.rub.de/permonen/may.html
May, A., Ritzenhofen, M.: Implicit Factoring: On Polynomial Time Factoring Given Only an Implicit Hint. In: Jarecki, S., Tsudik, G. (eds.) PKC 2009. LNCS, vol. 5443, pp. 1–14. Springer, Heidelberg (2009)
Nguyên, P.Q., Stern, J.: The Two Faces of Lattices in Cryptology. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 146–180. Springer, Heidelberg (2001)
Nguyen, P.Q., Vallée, B. (eds.): The LLL Algorithm: Survey and Applications. Information Security and Cryptography. Springer, Heidelberg (2007)
Olver, F.W.J., Lozier, D.W., Boisvert, R.F., Clark, C.W.: NIST handbook of mathematical functions. Cambridge University Press, Cambridge (2010)
Sarkar, S., Sen Gupta, S., Maitra, S.: Partial Key Exposure Attack on RSA - Improvements for Limited Lattice Dimensions. In: Gong, G., Gupta, K.C. (eds.) INDOCRYPT 2010. LNCS, vol. 6498, pp. 2–16. Springer, Heidelberg (2010)
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 exponents. Information Processing Letter 110, 336–340 (2010)
Takayasu, A., Kunihiro, N.: Better Lattice Constructions for Solving Multivariate Linear Equations Modulo Unknown Divisors. In: Boyd, C., Simpson, L. (eds.) ACISP. LNCS, vol. 7959, pp. 118–135. Springer, Heidelberg (2013)
de Weger, B.: Cryptanalysis of RSA with Small Prime Difference, Applicable Algebra in Engineering. Communication and Computing 13, 17–28 (2002)
Wiener, M.J.: Cryptanalysis of Short RSA Secret Exponents. IEEE Transactions on Information Theory 36(3), 553–558 (1990); Firstly appeared In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, p. 372. Springer, Heidelberg (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Takayasu, A., Kunihiro, N. (2014). Cryptanalysis of RSA with Multiple Small Secret Exponents. In: Susilo, W., Mu, Y. (eds) Information Security and Privacy. ACISP 2014. Lecture Notes in Computer Science, vol 8544. Springer, Cham. https://doi.org/10.1007/978-3-319-08344-5_12
Download citation
DOI: https://doi.org/10.1007/978-3-319-08344-5_12
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-08343-8
Online ISBN: 978-3-319-08344-5
eBook Packages: Computer ScienceComputer Science (R0)