Cryptanalysis of RSA with smooth prime sum
*Meryem Cherkaoui SemmouniCorresponding authorcher.meryem@gmail.comInformation Communication and Embedded Systems Ecole Nationale Supérieure d’Informatique et d’Analyse des Systémes Mohammed V University in RabatRabat, MoroccoView full profile → , Abderrahmane Nitajabderrahmane.nitaj@unicaen.frUNICAEN, CNRS, LMNO Normandie University 14000 CaenNormandie Univ Laboratoire de Mathématiques Nicolas Oresme Université de Caen NormandieCaen, 14000, France0000-0002-0372-1757View full profile → , Mostafa Belkasmimostafa.belkasmi@um5.ac.maInformation Communication and Embedded Systems Ecole Nationale Supérieure d’Informatique et d’Analyse des Systémes Mohammed V University in RabatRabat, MoroccoView full profile →
* Corresponding author · click or hover a name for details
- Received:
- 01 Apr 2021
- Accepted:
- 01 Jul 2021
- Published Online:
- 18 Aug 2022
- Article type:
- Research Article
- Language:
- EN
- Article no.:
- JDMSC-1461
- Pages:
- 2183–2203
Abstract
Keywords
Subject Classifications
References
[1] J. Blömer, A. May (2003) New partial key exposure attacks on RSA. In: Boneh D. (eds) Advances in Cryptology - CRYPTO 2003. CRYPTO 2003. Lecture Notes in Computer Science, vol 2729. Springer, Berlin, Heidelberg. doi.org/10.1007/978-3-540-45146-4_2
[2] J. Blömer, A. May (2004) A generalized Wiener attack on RSA. In: Bao F., Deng R., Zhou J. (eds) Public Key Cryptography PKC 2004. PKC 2004. Lecture Notes in Computer Science, vol 2947. Springer, Berlin, Heidelberg. doi.org/10.1007/978-3-540-24632-9_1
[3] D. Boneh, Twenty years of attacks on the RSA cryptosystem, Notices Amer. Math. Soc. 46 (2), 203-213, (1999)
[4] D. Boneh, G. Durfee (1999) Cryptanalysis of RSA with private key d less than 0.292.N In: Stern J. (eds) Advances in Cryptology EUROCRYPT 99. EUROCRYPT 1999. Lecture Notes in Computer Science, vol 1592. Springer, Berlin, Heidelberg. doi.org/10.1007/3-540-48910-X_1
[5] D. Boneh, G. Durfee and Y. Frankel, An attack on RSA given a small fraction of the private key bits, Advances in Cryptology - ASIACRYPT’98 (Beijing), Lecture Notes in Comput. Sci., Springer, Berlin, 1514 (1998), 25-34. doi: 10.1007/3-540-49649-1_3
[6] E.R Canfield, P. Erdös, C. Pomerance, On a problem of Oppenheim concerning factorisatio numerorum, Journal of Number Theory 17, pp. 1-28 (1983)
[7] D. Coppersmith, Small solutions to polynomial equations, and low exponent RSA vulnerabilities. J. Cryptology 10, 233-260 (1997). doi.org/10.1007/s001459900030
[8] N. Demytko (1994) A new elliptic curve based analogue of RSA. In: Helleseth T. (eds) Advances in Cryptology EUROCRYPT 93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlin, Heidelberg. doi.org/10.1007/3-540-48285-7_4
[9] M. Ernst, E. Jochemsz, A. May, B. de Weger (2005) Partial key exposure attacks on RSA up to full size exponents. In: Cramer R. (eds) Advances in Cryptology EUROCRYPT 2005. EUROCRYPT 2005. Lecture Notes in Computer Science, vol 3494. Springer, Berlin, Heidelberg. doi.org/10.1007/11426639_22
[10] G. H. Hardy, E. M. Wright, An Introduction to Theory of Numbers, 5th Edition, The Clarendon Press Oxford University Press, New York, 1979.
[11] M. Hinek, Cryptanalysis of RSA and Its Variants, Chapman & Hall/CRC, Cryptography and Network Security Series, Boca Raton, (2009)
[12] K. Koyama, U.M. Maurer, T. Okamoto, S.A. Vanstone (1992) New public-key schemes based on elliptic curves over the ring Zn. In: Feigenbaum J. (eds) Advances in Cryptology CRYPTO 91. CRYPTO 1991. Lecture Notes in Computer Science, vol 576. Springer, Berlin, Heidelberg. doi.org/10.1007/3-540-46766-1_20
[13] H. W. Lenstra Jr. (1987) Factoring integers with elliptic curves, Annals of Mathematics, Vol. 126, No. 2, 1987, pp. 649-673. doi:10.2307/1971363
[14] S. Maitra, S. Sarkar (2008) 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. doi.org/10.1007/978-3-540-85886-7_16
[15] G. d. Meulenaer, F. Gosset, G. M. d. Dormale and J. Quisquater, Integer factorization based on elliptic curve method: towards better exploitation of reconfigurable hardware, 15th Annual IEEE Symposium on Field-Programmable Custom Computing Machines (FCCM 2007), 2007, pp. 197-206, doi: 10.1109/FCCM.2007.12
[16] M. Mumtaz, L. Ping (2019) Forty years of attacks on the RSA cryptosystem: a brief survey, Journal of Discrete Mathematical
Sciences and Cryptography, 22:1, 9-29, doi: 10.1080/09720529.2018. 1564201.
[17] A. Nitaj, Another generalization of Wiener’s attack on RSA, Progress in Cryptology-AFRICACRYPT 2008, 174-190, Lecture Notes in Comput. Sci., 5023, Springer-Verlag, 2008 doi.org/10.1007/978-3-540-68164-9_12
[18] A. Nitaj (2013) Diophantine and lattice cryptanalysis of the RSA cryptosystem. In: Yang XS. (eds) Artificial Intelligence, Evolutionary Computing and Metaheuristics. Studies in Computational Intelligence, vol 427. Springer, Berlin, Heidelberg. doi.org/10.1007/978-3-642-29694-9_7
[19] A. Nitaj, A new attack on the KMOV cryptosystem, Bull. Korean Math. Soc. 2014 Vol. 51, No. 5, 1347-1356, doi.org/10.4134/BKMS.2014.51.5.1347
[20] A. Nitaj, E. Fouotsa (2019) A new attack on RSA and Demytko’s elliptic curve cryptosystem, Journal of Discrete Mathematical Sciences and Cryptography, 22:3, 391-409, doi: 10.1080/09720529.2019.1587827
[21] R. Rivest, A. Shamir, L. Adleman, A Method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM Volume 21 Issue 2 Feb. 1978 pp. 120-126 doi.org/10.1145/359340.359342
[22] S. Sarkar, S. Maitra and S. Sarkar, RSA cryptanalysis with increased bounds on the secret exponent using less lattice dimension, IACR Cryptology ePrint Archive (2008) https://eprint.iacr.org/2008/315
[23] H.M Sun, M.-E. Wu, R. Steinfeld, J. Guo, H.Wang, (2008) Cryptanalysis of short exponent rsa with primes sharing least significant bits. In: Franklin M.K., Hui L.C.K., Wong D.S. (eds) Cryptology and Network Security. CANS 2008. Lecture Notes in Computer Science, vol 5339. Springer, Berlin, Heidelberg. doi.org/10.1007/978-3-540-89641-8_4
[24] G. Tenenbaum, Introduction to Analytic and Probabilistic Number Theory, Cambridge Studies in Advanced Mathematics 46. Cambridge University Press, Cambridge, 1995.
[25] B. de Weger, Cryptanalysis of RSA with small prime difference. Applicable Algebra in Engineering, Communication and Computing, 13(1), pp. 17-28, 2002 doi::10.1007/s002000100088
[26] M.J. Wiener (1990) Cryptanalysis of short RSA secret exponents. In: Quisquater JJ., Vandewalle J. (eds) Advances in Cryptology EUROCRYPT 89. EUROCRYPT 1989. Lecture Notes in Computer Science, vol 434. Springer, Berlin, Heidelberg. doi.org/10.1007/3-540-46885-4_36
[27] Y.-D. Zhao, W.-F. Qi, Small private-exponent attack on RSA with primes sharing bits, in Proc. Information Security Conference 2007, ISC 2007, ser. Lecture Notes in Computer Science, J. Garay et al., Eds. Heidelberg: Springer, 2007, vol. 4779, pp. 221-229, (2007)
[28] P. Zimmermann, 50 largest prime factors found by ECM. https://members.loria.fr/PZimmermann/records/top50.html
[29] P. Zimmermann, B. Dodson, 20 years of ECM. In: Hess F., Pauli S., Pohst M. (eds) Algorithmic Number Theory. ANTS 2006. Lecture Notes in Computer Science, vol 4076. Springer, Berlin, Heidelberg (2006) doi: 10.1007/11792086_37
