New Jochemsz–May Cryptanalytic Bound for RSA System Utilizing Common Modulus N = p 2 q

Nurul Nur Hanisah Adenan, Muhammad Rezal Kamel Ariffin, Siti Hasana Sapar, Amir Hamzah Abd Ghafar and Muhammad Asyraf Asbullah
Additional contact information
Nurul Nur Hanisah Adenan: Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia
Muhammad Rezal Kamel Ariffin: Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia
Siti Hasana Sapar: Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia
Amir Hamzah Abd Ghafar: Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia
Muhammad Asyraf Asbullah: Institute for Mathematical Research, Universiti Putra Malaysia, Serdang 43400, Selangor, Malaysia

Mathematics, 2021, vol. 9, issue 4, 1-13

Abstract: This paper describes an attack on the Rivest, Shamir and Adleman (RSA) cryptosystem utilizing the modulus N = p 2 q where p and q are two large balanced primes. Let e 1 , e 2 < N ? be the integers such that d 1 , d 2 < N ? be their multiplicative inverses. Based on the two key equations e 1 d 1 ? k 1 ? ( N ) = 1 and e 2 d 2 ? k 2 ? ( N ) = 1 where ? ( N ) = p ( p ? 1 ) ( q ? 1 ) , our attack works when the primes share a known amount of least significant bits (LSBs) and the private exponents share an amount of most significant bits (MSBs). We apply the extended strategy of Jochemsz–May to find the small roots of an integer polynomial and show that N can be factored if ? < 11 10 + 9 4 ? ? 1 2 ? ? 1 2 ? ? 1 30 180 ? + 990 ? ? 180 ? + 64 . Our attack improves the bounds of some previously proposed attacks that makes the RSA variant vulnerable.

Keywords: factoring; least significant bits (LSBs); most significant bits (MSBs); multiplicative inverse; Jochemsz–May extended strategy (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/4/340/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/4/340/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:4:p:340-:d:495863

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().