UPM Institutional Repository

New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q


Adenan, Nurul Nur Hanisah and Ariffin, Muhammad Rezal Kamel and Sapar, Siti Hasana and Abd Ghafar, Amir Hamzah and Asbullah, Muhammad Asyraf (2021) New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q. Mathematics, 9 (4). art. no. 340. pp. 1-13. ISSN 2227-7390


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 e1 ,e2 < Nγ be the integers such that d1 , d2 < Nδ be their multiplicative inverses. Based on the two key equations e1d1 − k1φ(N) = 1 and e2d2 − k2φ(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 p 180γ + 990α − 180β + 64. Our attack improves the bounds of some previously proposed attacks that makes the RSA variant vulnerable.

Download File

Full text not available from this repository.
Official URL or Download Paper: https://www.mdpi.com/2227-7390/9/4/340

Additional Metadata

Item Type: Article
Divisions: Institute for Mathematical Research
DOI Number: https://doi.org/10.3390/math9040340
Publisher: MDPI
Keywords: Factoring; Least significant bits (LSBs); Most significant bits (MSBs); Multiplicative inverse; Jochemsz–May extended strategy
Depositing User: Ms. Nur Faseha Mohd Kadim
Date Deposited: 07 Apr 2023 03:51
Last Modified: 07 Apr 2023 03:51
Altmetrics: http://www.altmetric.com/details.php?domain=psasir.upm.edu.my&doi=10.3390/math9040340
URI: http://psasir.upm.edu.my/id/eprint/94352
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item