New attacks on RSA with Moduli N = p^r q

Abderrahmane Nitaj (1) , Tajjeeddine Rachidi (2)

1 LMNO - Laboratoire de Mathématiques Nicolas Oresme
2 AUI - Al Akhawayn University in Ifrane

We present three attacks on the Prime Power RSA with mod-ulus N = p^r q. In the first attack, we consider a public exponent e satisfying an equation ex − φ(N)y = z where φ(N) = p^(r−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 factor 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 factor two Prime Power RSA moduli N1 = p1^r q1 and N2 = p2^r q2 when p1 and p2 share a suitable amount of their most significant bits, namely, |p1 − p2| < p1/(2rq1 q2) .

Keywords: RSA; Cryptanalysis; Factorization; Coppersmith's method; Prime Power RSA

Domains: Computer Science [cs]; Cryptography and Security [cs.CR]

Abderrahmane Nitaj, Tajjeeddine Rachidi. New attacks on RSA with Moduli N = p^r q. First International Conference Codes, Cryptology, and Information Security, LNCS Springer, pp. 352-360, 2015, 2015, Rabat, Morocco. ⟨10.1007/978-3-319-18681-8_28⟩. ⟨hal-02320969⟩