Skip to Main content Skip to Navigation
Conference papers

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

Abstract : 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) .
Document type :
Conference papers
Complete list of metadatas

Cited literature [18 references]  Display  Hide  Download

https://hal-normandie-univ.archives-ouvertes.fr/hal-02320969
Contributor : Abderrahmane Nitaj <>
Submitted on : Sunday, October 20, 2019 - 12:20:30 AM
Last modification on : Monday, April 27, 2020 - 4:14:03 PM
Long-term archiving on: : Tuesday, January 21, 2020 - 12:42:50 PM

File

rsa33final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

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⟩

Share

Metrics

Record views

48

Files downloads

107