Cryptanalysis of RSA with more than one decryption exponent

Abstract

In this paper, we analyze the security of the RSA public key cryptosystem where multiple encryption and decryption exponents are considered with the same RSA modulus N. We consider $N=pq$, where p, q are of the same bit size, i.e., $q<p<2q$. We show that if n many decryption exponents $(d_1,\dots ,d_n)$ are used with the same N, then RSA is insecure when $d_i<N^{\frac{3n-1}{4n+4}}$, for all i, $1⩽i⩽n$ and $n⩾2$. Our result improves the bound of Howgrave-Graham and Seifert (CQRE 1999) for $n⩽42$ and also generalizes our recent work for $n=2$ (IPL 2010).