Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N)
Newly developed techniques have been recently documented, which capitalize on the security provided by prime power modulus denoted as N = p r q s where 2 ≤ s < r. Previous research primarily concentrated on the factorization of the modulus of type at minimum N = p 3 q 2 . In contrast, within the...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Department of Mathematics, University of the Punjab
2024
|
| Online Access: | http://psasir.upm.edu.my/id/eprint/116412/ http://psasir.upm.edu.my/id/eprint/116412/1/116412.pdf |
| _version_ | 1848866999352950784 |
|---|---|
| author | Aqlili Ruzai, Wan Nur Nek Abd Rahman, Normahirah Asbullah, Muhammad Asyraf |
| author_facet | Aqlili Ruzai, Wan Nur Nek Abd Rahman, Normahirah Asbullah, Muhammad Asyraf |
| author_sort | Aqlili Ruzai, Wan Nur |
| building | UPM Institutional Repository |
| collection | Online Access |
| description | Newly developed techniques have been recently documented, which capitalize on the security provided by prime power modulus denoted as N = p r q s where 2 ≤ s < r. Previous research primarily concentrated on the factorization of the modulus of type at minimum N = p 3 q 2 . In contrast, within the context of 2 ≤ s < r, we address scenarios in the modulus N = p 2 q (i.e. r = 2 and s = 1) still need to be covered, showing a significant result to the field of study. This work presents two factorization approaches for the multiple moduli Ni = p 2 i qi , relying on a good approximation of the Euler’s totient function ϕ(Ni). The initial method for factorization deals with the multiple moduli Ni = p 2 i qi derived from m public keys (Ni , ei) and is interconnected through the equation eid − kiϕ(Ni) = 1. In contrast, the second factorization method is associated with the eidi − kϕ(Ni) = 1. By reorganizing the equations as a simultaneous Diophantine approximation problem and implementing the LLL algorithm, it becomes possible to factorize the list of moduli Ni = p 2 i qi concurrently, given that the unknowns d, di , k, and ki are sufficiently small. The key difference between our results and the referenced work is that we cover a real-world cryptosystem that uses the modulus N = p 2 q. In contrast, the previous work covers a hypothetical situation of modulus in the form of N = p r q s . |
| first_indexed | 2025-11-15T14:29:31Z |
| format | Article |
| id | upm-116412 |
| institution | Universiti Putra Malaysia |
| institution_category | Local University |
| language | English |
| last_indexed | 2025-11-15T14:29:31Z |
| publishDate | 2024 |
| publisher | Department of Mathematics, University of the Punjab |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | upm-1164122025-04-07T06:44:21Z http://psasir.upm.edu.my/id/eprint/116412/ Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N) Aqlili Ruzai, Wan Nur Nek Abd Rahman, Normahirah Asbullah, Muhammad Asyraf Newly developed techniques have been recently documented, which capitalize on the security provided by prime power modulus denoted as N = p r q s where 2 ≤ s < r. Previous research primarily concentrated on the factorization of the modulus of type at minimum N = p 3 q 2 . In contrast, within the context of 2 ≤ s < r, we address scenarios in the modulus N = p 2 q (i.e. r = 2 and s = 1) still need to be covered, showing a significant result to the field of study. This work presents two factorization approaches for the multiple moduli Ni = p 2 i qi , relying on a good approximation of the Euler’s totient function ϕ(Ni). The initial method for factorization deals with the multiple moduli Ni = p 2 i qi derived from m public keys (Ni , ei) and is interconnected through the equation eid − kiϕ(Ni) = 1. In contrast, the second factorization method is associated with the eidi − kϕ(Ni) = 1. By reorganizing the equations as a simultaneous Diophantine approximation problem and implementing the LLL algorithm, it becomes possible to factorize the list of moduli Ni = p 2 i qi concurrently, given that the unknowns d, di , k, and ki are sufficiently small. The key difference between our results and the referenced work is that we cover a real-world cryptosystem that uses the modulus N = p 2 q. In contrast, the previous work covers a hypothetical situation of modulus in the form of N = p r q s . Department of Mathematics, University of the Punjab 2024 Article PeerReviewed text en http://psasir.upm.edu.my/id/eprint/116412/1/116412.pdf Aqlili Ruzai, Wan Nur and Nek Abd Rahman, Normahirah and Asbullah, Muhammad Asyraf (2024) Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N). Punjab University Journal of Mathematics, 56 (5). pp. 123-134. ISSN 1016-2526; eISSN: 1016-2526 https://pu.edu.pk/images/journal/maths/PDF/PUJM_1_56_5_2024.pdf 10.52280/pujm.2024.56(5)01 |
| spellingShingle | Aqlili Ruzai, Wan Nur Nek Abd Rahman, Normahirah Asbullah, Muhammad Asyraf Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N) |
| title | Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N) |
| title_full | Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N) |
| title_fullStr | Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N) |
| title_full_unstemmed | Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N) |
| title_short | Another look at the security analysis of the modulus N = p 2 q by utilizing an approximation approach for ϕ(N) |
| title_sort | another look at the security analysis of the modulus n = p 2 q by utilizing an approximation approach for ϕ(n) |
| url | http://psasir.upm.edu.my/id/eprint/116412/ http://psasir.upm.edu.my/id/eprint/116412/ http://psasir.upm.edu.my/id/eprint/116412/ http://psasir.upm.edu.my/id/eprint/116412/1/116412.pdf |