Another Look at the Security Analysis of the Modulus N = p 2 q by Utilizing an Approximation Approach for ϕ(N)

Abstract

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 2iqi, relying on a good approximation of the Euler’s totient function ϕ(Ni). The initial method for factorization deals with the multiple moduli Ni = p 2iqi 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 = p2iqi 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 = p2q. In contrast, the previous work covers a hypothetical situation of modulus in the form of N = prqs.