An attack on N = p2q with partially known bits on the multiple of the prime factors
This paper presents a cryptanalytic study upon the modulus N = p 2q consisting of two large primes that are in the same-bit size. In this work, we show that the modulus N is factorable if e satisfies the Diophantine equation of the form ed − k(N − (ap)2 − apbq + ap) = 1 where ab is an unknown appro...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Published: |
Universiti Putra Malaysia
2021
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/95820/ |
| _version_ | 1848862229241266176 |
|---|---|
| author | Wan Mohd Ruzai, Wan Nur Aqlili Adenan, Nurul Nur Hanisah Kamel Ariffin, Muhammad Rezal Abd Ghafar, Amir Hamzah Mohamat Johari, Mohamat Aidil |
| author_facet | Wan Mohd Ruzai, Wan Nur Aqlili Adenan, Nurul Nur Hanisah Kamel Ariffin, Muhammad Rezal Abd Ghafar, Amir Hamzah Mohamat Johari, Mohamat Aidil |
| author_sort | Wan Mohd Ruzai, Wan Nur Aqlili |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | This paper presents a cryptanalytic study upon the modulus N = p
2q consisting of two large primes that are in the same-bit size. In this work, we show that the modulus N is factorable if e satisfies the Diophantine equation of the form ed − k(N − (ap)2 − apbq + ap) = 1 where ab is an unknown approximation of qp. Our attack is feasible when some amount of Least Significant Bits (LSBs) of ap and bq is known. By utilising the Jochemsz-May strategy as our main method, we manage to prove that the modulus N can be factored in polynomial time under certain specified conditions. |
| first_indexed | 2025-11-15T13:13:42Z |
| format | Article |
| id | upm-95820 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-15T13:13:42Z |
| publishDate | 2021 |
| publisher | Universiti Putra Malaysia |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-958202023-04-03T07:35:56Z http://psasir.upm.edu.my/id/eprint/95820/ An attack on N = p2q with partially known bits on the multiple of the prime factors Wan Mohd Ruzai, Wan Nur Aqlili Adenan, Nurul Nur Hanisah Kamel Ariffin, Muhammad Rezal Abd Ghafar, Amir Hamzah Mohamat Johari, Mohamat Aidil This paper presents a cryptanalytic study upon the modulus N = p 2q consisting of two large primes that are in the same-bit size. In this work, we show that the modulus N is factorable if e satisfies the Diophantine equation of the form ed − k(N − (ap)2 − apbq + ap) = 1 where ab is an unknown approximation of qp. Our attack is feasible when some amount of Least Significant Bits (LSBs) of ap and bq is known. By utilising the Jochemsz-May strategy as our main method, we manage to prove that the modulus N can be factored in polynomial time under certain specified conditions. Universiti Putra Malaysia 2021 Article PeerReviewed Wan Mohd Ruzai, Wan Nur Aqlili and Adenan, Nurul Nur Hanisah and Kamel Ariffin, Muhammad Rezal and Abd Ghafar, Amir Hamzah and Mohamat Johari, Mohamat Aidil (2021) An attack on N = p2q with partially known bits on the multiple of the prime factors. Malaysian Journal of Mathematical Sciences, 15 (spec.1). 63 - 75. ISSN 1823-8343 https://einspem.upm.edu.my/journal |
| spellingShingle | Wan Mohd Ruzai, Wan Nur Aqlili Adenan, Nurul Nur Hanisah Kamel Ariffin, Muhammad Rezal Abd Ghafar, Amir Hamzah Mohamat Johari, Mohamat Aidil An attack on N = p2q with partially known bits on the multiple of the prime factors |
| title | An attack on N = p2q with partially known bits on the multiple of the prime factors |
| title_full | An attack on N = p2q with partially known bits on the multiple of the prime factors |
| title_fullStr | An attack on N = p2q with partially known bits on the multiple of the prime factors |
| title_full_unstemmed | An attack on N = p2q with partially known bits on the multiple of the prime factors |
| title_short | An attack on N = p2q with partially known bits on the multiple of the prime factors |
| title_sort | attack on n = p2q with partially known bits on the multiple of the prime factors |
| url | http://psasir.upm.edu.my/id/eprint/95820/ http://psasir.upm.edu.my/id/eprint/95820/ |