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

Text 116412.pdf - Published Version Restricted to Repository staff only Download (374kB) Official URL or Download Paper: https://pu.edu.pk/images/journal/maths/PDF/PUJM_1_...

Actions (login required)

View Item