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 |
| Summary: | 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 . |
|---|