Improved cryptanalysis of RSA

Dossou-Yovo, Virgile; Nitaj, Abderrahmane; Togbé, Alain

doi:10.47974/JDMSC-1570

Open Access Research Article

Improved cryptanalysis of RSA

Virgile Dossou-Yovodosvirs20@gmail.comInstitut de Mathématiques et de Sciences PhysiquesDangbo, BéninView full profile → , ^*Abderrahmane NitajCorresponding authorabderrahmane.nitaj@unicaen.frNormandie UnivLaboratoire de Mathématiques Nicolas OresmeUniversité de Caen NormandieFrance0000-0002-0372-1757View full profile → , Alain Togbéatogbe@pnw.eduDepartment of Mathematics, StatisticsPurdue University NorthwestWestville, U.S.A.View full profile →

* Corresponding author · click or hover a name for details

pp. 945–961Vol. 27Issue 3April 2024DOI: 10.47974/JDMSC-1570 Crossmark XML

Received:: 08 Jun 2021
Published Online:: 01 May 2024
Article type:: Research Article
Language:: EN
Article no.:: JDMSC-1570
Pages:: 945–961

Abstract

Let N = pq be an RSA modulus and e be a public exponent. Let φ(N) = (p – 1)(q – 1) be the Euler’s totient function. The equation ex2 – φ(N)y2 = z has infinitely many solutions in integers (x, y, z). We show that if x, y and z are suitably small, then one can factor the RSA modulus. Our bounds on the size of the solutions x, y, and z improve the existing bounds of some attacks on RSA such as Wiener’s continued fractions based attack, and Blömer-May’s lattice reduction based attack.

Keywords

RSA Cryptanalysis Factorization Continued fractions

Subject Classifications

94A60

References

[1] J. Blömer and A. May, A generalized Wiener attack on RSA. In Public Key Cryptography - PKC 2004, volume 2947 of Lecture Notes in Computer Science, 1-13. Springer-Verlag.
[2] J. Blömer and A. May, New partial key exposure attacks on RSA, Proceedings of CRYPTO 2003, LNCS 2729 (2003), pp. 27–43. Springer Verlag.
[3] D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices Amer. Math. Soc. 46 (2), pp. 203–213, 1999.
[4] D. Boneh and G. Durfee, Cryptanalysis of RSA with private key d less than Advances in Cryptology Eurocrypt 99, Lecture Notes in Computer Science Vol. 1592, Springer-Verlag, pp. 1–11, 1999.
[5] D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits. In: Ohta, K., Pei, D. (eds.) Advances in Cryptology Asiacrypt’98. Lecture Notes in Computer Science, vol. 1514, pp. 25–34. Springer-Verlag 1998.
[6] D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities. Journal of Cryptology, 10(4), pp. 233–260, 1997.
[7] M. Ernst, E. Jochemsz, A. May and B. de Weger, Partial key exposure attacks on RSA up to full size exponents. In: Cramer, R. (ed.) Advances in Cryptology Eurocrypt 2005. Lecture Notes in Computer Science, vol. 3494, pp. 371–386. Springer-Verlag 2005.
[8] G.H. Hardy and E.M. Wright, An Introduction to the Theory of Numbers. Oxford University Press, London, 1965.
[9] M. Hinek, Cryptanalysis of RSA and Its Variants, Chapman & Hall/CRC, Cryptography and Network Security Series, Boca Raton, (2009).
[10] N. Howgrave-Graham, Finding small roots of univariate modular equations revisited, In Cryptography and Coding, LNCS 1355, pp. 131–142, Springer-Verlag (1997).
[11] E. Jochemsz and A. May, A strategy for finding roots of multivariate polynomials with new applications in attacking RSA variants, in: ASIACRYPT 2006, LNCS, vol. 4284, 2006, pp. 267–282, Springer-Verlag.
[12] A.K. Lenstra, H.W. Lenstra and Lovász, Factoring polynomials with rational coefficients, Mathematische Annalen, Vol. 261, pp. 513–534, 1982.
[13] S. Maitra and S. Sarkar, Revisiting Wiener’s Attack - New Weak Keys in RSA. In: Wu TC., Lei CL., Rijmen V., Lee DT. (eds) Information Security. ISC 2008. Lecture Notes in Computer Science, vol 5222. Springer, Berlin, Heidelberg 2008.
[14] A. May, New RSA Vulnerabilities Using Lattice Reduction Methods. PhD thesis, University of Paderborn (2003). Available at
http://wwwcs.upb.de/cs/ag-bloemer/personen/alex/publikationen/
[15] M. Mumtaz and L. Ping, Forty years of attacks on the RSA cryptosystem: A brief survey, Journal of Discrete Mathematical Sciences and Cryptography, 22:1, pp. 9–29 (2019)
[16] A. Nitaj, Another generalization of Wiener’s attack on RSA, In: Vaudenay, S. (Ed.) Africacrypt 2008. LNCS, vol. 5023, 174–190. Springer, Heidelberg (2008).
[17] A. Nitaj, M.R.K. Ariffin, D.I. Nassr and H.M. Bahig, New Attacks on the RSA Cryptosystem, In: Pointcheval D., Vergnaud D. (eds), Progress in Cryptology - Africacrypt 2014. LNCS, vol. 8469, pp. 178–198. Springer, Cham (2014).
[18] I. Niven, H. S. Zuckerman and H.L. Montgomery, An Introduction to the theory of numbers, John Wiley & Sons, Inc. New York, Chichester, Brisbane, Toronto and Singapore 1991.
[19] A. Rawat, K. Sehgal, A. Tiwari, A. Sharma and A. Joshi, A novel accelerated implementation of RSA using parallel processing, Journal of Discrete Mathematical Sciences and Cryptography, 22:2, pp. 309–322, 2019.
[20] R. Rivest, A. Shamir and L. Adleman, A Method for Obtaining digital signatures and public-key cryptosystems, Communications of the ACM, Vol. 21 (2), pp. 120–126,1978.
[21] R. Steinfeld, S. Contini, H. Wang and J. Pieprzyk, Converse Results to the Wiener Attack on RSA. In: Vaudenay S. (eds) Public Key Cryptography - PKC 2005. PKC 2005. Lecture Notes in Computer Science, vol 3386. Springer, Berlin, Heidelberg 2005.
[22] H.M Sun, Mu-EnWu, R. Steinfeld, J. Guo and H. Wang, Cryptanalysis of Short Exponent RSA with Primes Sharing Least Significant Bits. M.K. Franklin, L.C.K. Hui, D.S. Wong (Eds.): CANS 2008, LNCS 5339, pp. 49–63, 2008.
[23] S. Tanwar and A. Kumar, An efficient and secure identity based multiple signatures scheme based on RSA, Journal of Discrete Mathematical Sciences and Cryptography, 22:6, pp. 953–971, 2019.
[24] M. Wiener, Cryptanalysis of short RSA secret exponents, IEEE Transactions on Information Theory, Vol. 36, pp. 553–558, 1990.

Views: 322Downloads: 69Citations: 0