New attacks on RSA with Moduli N=p rq .
Abderrahmane Nitaj, Tajjeeddine Rachidi · 2015
Abstract. We present three attacks on the Prime Power RSA with mod-ulus N = prq. In the first attack, we consider a public exponent e sat-isfying an equation ex − φ(N)y = z where φ(N) = pr−1(p − 1)(q − 1). We show that one can factor N if the parameters |x | and |z | satisfy |xz | < N r(r−1) (r+1)2 thereby extending the recent results of Sakar [16]. In the second attack, we consider two public exponents e1 and e2 and their corresponding private exponents d1 and d2. We show that one can fac-tor N when d1 and d2 share a suitable amount of their most significant bits, that is |d1 − d2 | < N r(r−1) (r+1)2. The third attack enables us to fac-tor two Prime Power RSA moduli N1 = p r 1q1 and N2 = p r 2q2 when p1 and p2 share a suitable amount of their most significant bits, namely, |p1 − p2 | < p12rq1q2.