Cryptology ePrint Archive: Report 2014/549

New Attacks on the RSA Cryptosystem

Abderrahmane Nitaj, Muhammad Rezal Kamel Ariffin, Dieaa I. Nassr, and Hatem M. Bahig

Abstract: This paper presents three new attacks on the RSA cryptosystem. The rst two attacks work when k RSA public keys (Ni, ei) are such that there exist k relations of the shape eix-yi\phi(Ni)=zi or of the shape eixi-y\phi(Ni)=zi where Ni = piqi, \phi(Ni)=(pi-1)(qi-1) and the parameters x, xi, y, yi, zi are suitably small in terms of the prime factors of the moduli. We show that our attacks enable us to simultaneously factor the k RSA moduli Ni. The third attack works when the prime factors p and q of the modulus N = pq share an amount of their least signicant bits (LSBs) in the presence of two decryption exponents d1 and d2 sharing an amount of their most signicant bits (MSBs). The three attacks improve the bounds of some former attacks that make RSA insecure.

Category / Keywords: foundations / RSA, Cryptanalysis, Factorization, LLL algorithm, Simultaneous diophantine approximations, Coppersmith's method

Original Publication (in the same form): AFRICACRYPT2014
DOI: 10.1007/978-3-319-06734-6_12

Date: received 14 Jul 2014

Contact author: rezal at upm edu my

Available format(s): PDF | BibTeX Citation

Version: 20140718:071544 (All versions of this report)

Short URL: ia.cr/2014/549

Discussion forum: Show discussion | Start new discussion