Abstract
An important attack on multi-power RSA (\(N=p^rq\)) was introduced by Sarkar in 2014, by extending the small private exponent attack of Boneh and Durfee on classical RSA. In particular, he showed that N can be factored efficiently for \(r=2\) with private exponent d satisfying \(d<N^{0.395}\). In this paper, we generalize this work by introducing a new partial key exposure attack for finding small roots of polynomials using Coppersmith’s algorithm and Gröbner basis computation. Our attack works for all multi-power RSA exponents e (resp. d) when the exponent d (resp. e) has full size bit length. The attack requires prior knowledge of least significant bits (LSBs), and has the property that the required known part of LSB becomes smaller in the size of e. For practical validation of our attack, we demonstrate several computer algebra experiments.
This is a preview of subscription content, log in via an institution to check access.
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
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}\). IEEE Transactions on Information Theory 46(4), 1339–1349 (2000)
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)
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)
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.: Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology 10(4), 233–260 (1997)
Coron, J.-S.: Finding small roots of bivariate integer polynomial 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 polynomial equations: a direct approach. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 379–394. Springer, Heidelberg (2007)
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)
Faugère, J.C.: A new efficient algorithm for computing Gröbner Bases without reduction to zero (F5). In: Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation, ISSAC 2002, New York, NY, USA, pp. 75–83. ACM (2002)
Howgrave-Graham, N.: Finding small roots of univariate modular equations revisited. In: Darnell, M. (ed.) Crytography and Coding. Lecture Notes in Computer Science, vol. 1355, pp. 131–142. Springer, Heidelberg (1997)
Huang, Z., Hu, L., Xu, J., Peng, L., Xie, Y.: Partial key exposure attacks on Takagi’s variant of RSA. In: Boureanu, I., Owesarski, P., Vaudenay, S. (eds.) ACNS 2014. LNCS, vol. 8479, pp. 134–150. Springer, Heidelberg (2014)
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)
Joye, M., Lepoint, T.: Partial key exposure on RSA with private exponents larger than N. In: Ryan, M.D., Smyth, B., Wang, G. (eds.) ISPEC 2012. LNCS, vol. 7232, pp. 369–380. Springer, Heidelberg (2012)
Kocher, P.C.: Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 104–113. Springer, Heidelberg (1996)
Lenstra Jr., A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261(4), 515–534 (1982)
Lu, Y., Zhang, R., Lin, D.: New results on solving linear equations modulo unknown divisors and its applications. Cryptology ePrint Archive, Report 2014/343 (2014). http://eprint.iacr.org/
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)
Nguyên, P.Q., Stehlé, D.: Floating-Point LLL revisited. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 215–233. Springer, Heidelberg (2005)
Sarkar, S.: Small secret exponent attack on RSA variant with modulus \(N=p^rq\). Designs, Codes and Cryptography 73(2), 383–392 (2014)
Takagi, T.: Fast RSA-type cryptosystem modulo \(p^kq\). In: Krawczyk, H. (ed.) Advances in Cryptology - CRYPTO ’98. Lecture Notes in Computer Science, vol. 1462, pp. 318–326. Springer, Heidelberg (1998)
Wiener, M.J.: Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory 36, 553–558 (1990)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Esgin, M.F., Kiraz, M.S., Uzunkol, O. (2015). A New Partial Key Exposure Attack on Multi-power RSA. In: Maletti, A. (eds) Algebraic Informatics. CAI 2015. Lecture Notes in Computer Science(), vol 9270. Springer, Cham. https://doi.org/10.1007/978-3-319-23021-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-23021-4_10
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23020-7
Online ISBN: 978-3-319-23021-4
eBook Packages: Computer ScienceComputer Science (R0)