New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q
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 −...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Published: |
MDPI
2021
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/94352/ |
| _version_ | 1848861974175154176 |
|---|---|
| author | Adenan, Nurul Nur Hanisah Ariffin, Muhammad Rezal Kamel Sapar, Siti Hasana Abd Ghafar, Amir Hamzah Asbullah, Muhammad Asyraf |
| author_facet | Adenan, Nurul Nur Hanisah Ariffin, Muhammad Rezal Kamel Sapar, Siti Hasana Abd Ghafar, Amir Hamzah Asbullah, Muhammad Asyraf |
| author_sort | Adenan, Nurul Nur Hanisah |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-15T13:09:39Z |
| format | Article |
| id | upm-94352 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-15T13:09:39Z |
| publishDate | 2021 |
| publisher | MDPI |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-943522023-04-07T03:51:55Z http://psasir.upm.edu.my/id/eprint/94352/ New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q Adenan, Nurul Nur Hanisah Ariffin, Muhammad Rezal Kamel Sapar, Siti Hasana Abd Ghafar, Amir Hamzah Asbullah, Muhammad Asyraf 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. MDPI 2021-02-08 Article PeerReviewed 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 https://www.mdpi.com/2227-7390/9/4/340 10.3390/math9040340 |
| spellingShingle | Adenan, Nurul Nur Hanisah Ariffin, Muhammad Rezal Kamel Sapar, Siti Hasana Abd Ghafar, Amir Hamzah Asbullah, Muhammad Asyraf New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q |
| title | New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q |
| title_full | New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q |
| title_fullStr | New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q |
| title_full_unstemmed | New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q |
| title_short | New Jochemsz–May Cryptanalytic bound for RSA system utilizing common Modulus N = p2q |
| title_sort | new jochemsz–may cryptanalytic bound for rsa system utilizing common modulus n = p2q |
| url | http://psasir.upm.edu.my/id/eprint/94352/ http://psasir.upm.edu.my/id/eprint/94352/ http://psasir.upm.edu.my/id/eprint/94352/ |