In this paper, we consider a variant of RSA schemes called Prime Power RSA with modulus N = prq for r ≥ 2, where p, q are of the same bit-size. May showed that when private exponent \(d < {N^{\frac{r}{{{{\left( {r + 1} \right)}^2}}}}}\) or \(d < {N^{{{\left( {\frac{{r - 1}}{{r + 1}}} \right)}^2}}}\), N can be factored in polynomial time in PKC 2004. Later in 2014, Sarkar improved the bound for r ≤ 5. We propose a new cryptanalytic method to attack this RSA variant when given two pairs of public and private exponents, namely (e1, d1) and (e2, d2) with the same modulus N. Suppose that we know d1 < Nδ1 and d2 < Nδ2. Our results show that when \({\delta _1}{\delta _2} < {\left( {\frac{{r - 1}}{{r + 1}}} \right)^3}\), Prime Power RSA is insecure.
['Mengce Zheng', 'Honggang Hu']
Cryptanalysis of Prime Power RSA with two private exponents