Abstract
We show that the attack of de Weger on RSA using continued fractions extends to Multi-Prime RSA. Let (n,e) be a Multi-Prime RSA public-key with private key d, where n = p 1 p 2 ⋯ p r is a product of r distinct balanced (roughly of the same bit size) primes, and p 1 < p 2 < … < p r . We show that if p r − p 1 = n α, 0 < α ≤ 1/r, r ≥ 3 and \(2d^2+1<\frac{n^{2/r - \alpha}}{6r},\) then Multi-Prime RSA is insecure.
Chapter PDF
Similar content being viewed by others
References
Alison, C., Paixão, M.: An efficient variant of the RSA cryptosystem, http://eprint.iacr.org/2003/159
Blömer, J., May, A.: A Generalized Wiener Attack on RSA. In: Bao, F., Deng, R., Zhou, J. (eds.) PKC 2004. LNCS, vol. 2947, pp. 1–13. Springer, Heidelberg (2004)
Boneh, D.: Twenty years of attacks on the RSA cryptosystem. Notices of the American Mathematical Society 46(2), 203–213 (1999)
Boneh, D., Durfee, G.: Cryptanalysis of RSA with private key d less than N 0.292. IEEE Trans. on Information Theory 46(4), 1339–1349 (2000)
Boneh, D., Shacham, H.: Fast Variants of RSA. CryptoBytes 5(1), 1–9 (2002)
Ciet, M., Koeune, F., Laguillaumie, F., Quisquater, J.-J.: Short private exponent attacks on fast variants of RSA. UCL Crypto Group Technical Report Series CG-2003/4, Universite Catholique de Louvain (2003)
Collins, T., Hopkins, D., Langford, S., Sabin, M.: Public key cryptographic apparatus and method. US patent #5, 848, 149 (January 1997)
Coppersmith, D.: Small solutions to polynomial equations and low exponent vulnerabilities. Journal of Cryptology 10(4), 223–260 (1997)
Durfee, G., Nguyen, P.: 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)
Hinek, M.J.: On the security of multi-prime RSA. Journal of Mathematical Cryptology 2(2), 117–147 (2008)
Hinek, M.J.: Cryptanalysis of RSA and its variants. Chapman & Hall/CRC (2010)
Hinek, M.J., Low, M.K., Teske, E.: On Some Attacks on Multi-prime RSA. In: Nyberg, K., Heys, H.M. (eds.) SAC 2002. LNCS, vol. 2595, pp. 385–404. Springer, Heidelberg (2003)
Lenstra, A.K., Lenstra, H.W., Lovasz, L.: Factoring polynomials with rational coefficients. Mathematische Annalen 261, 513–534 (1982)
Lim, S., Kim, S., Yie, I., Lee, H.: A Generalized Takagi-Cryptosystem with a Modulus of the Form p r q s. In: Roy, B., Okamoto, E. (eds.) INDOCRYPT 2000. LNCS, vol. 1977, pp. 283–294. Springer, Heidelberg (2000)
Maitra, S., Sarkar, S.: Revisiting Wiener’s Attack – New Weak Keys in RSA. In: Wu, T.-C., Lei, C.-L., Rijmen, V., Lee, D.-T. (eds.) ISC 2008. LNCS, vol. 5222, pp. 228–243. Springer, Heidelberg (2008)
May, A.: New RSA Vulnerabilities using Lattics Reduction Methods. Ph.D. Dissertation. University of Paderborn (2003)
Nassr, D., Bahig, H.M., Bhery, A., Dauod, S.: A New RSA Vulnerability Using Continued Fractions. In: Proceeding of the Sixth IEEE/ACS International Conference on Computer Systems and Applications (Security and Information Assurance Track), April 31- May 4, pp. 694–701 (2008)
Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Communication of ACM 21, 120–126 (1978)
Rosen, K.H.: Elementary Number Theory. Addison-Wesley, Reading Mass (1984)
Shoup, V.: NTL: A Library for doing Number Theory, http://www.shoup.net/ntl/index.html
Steinfeld, R., Contini, S., Pieprzyk, J., Wang, H.: Converse Results to the Wiener Attack on RSA. In: Vaudenay, S. (ed.) PKC 2005. LNCS, vol. 3386, pp. 184–198. Springer, Heidelberg (2005)
Verheul, E.R., van Tilborg, H.C.A.: Cryptanalysis of ‘less short’ RSA secret exponents. Applicable Algebra in Engineering, Communication and Computing 8, 425–435 (1997)
de Weger, B.: Cryptanalysis of RSA with small prime difference. Applicable Algebra in Engineering, Communication and Computing 13(1), 17–28 (2002)
Wiener, M.: Cryptanalysis of short RSA secret exponents. IEEE Transactions on Information Theory 36, 553–558 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bahig, H.M., Bhery, A., Nassr, D.I. (2012). Cryptanalysis of Multi-Prime RSA with Small Prime Difference. In: Chim, T.W., Yuen, T.H. (eds) Information and Communications Security. ICICS 2012. Lecture Notes in Computer Science, vol 7618. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-34129-8_4
Download citation
DOI: https://doi.org/10.1007/978-3-642-34129-8_4
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-34128-1
Online ISBN: 978-3-642-34129-8
eBook Packages: Computer ScienceComputer Science (R0)