Paper 2008/228

Revisiting Wiener's Attack -- New Weak Keys in RSA

Subhamoy Maitra and Santanu Sarkar

Abstract

In this paper we revisit Wiener's method (IEEE-IT 1990) of continued fraction (CF) to find new weaknesses in RSA. We consider RSA with $N=pq$, $q<p<2q$, public encryption exponent $e$ and private decryption exponent $d$. Our motivation is to find out when RSA is insecure given $d$ is $O(N^{\delta })$, where we are mostly interested in the range $0.3\le \delta \le 0.5$. Given $\rho$ $(1\le \rho \le 2)$ is known to the attacker, we show that the RSA keys are weak when $d=N^{\delta }$ and $\delta <\frac{1}{2}-\frac{\gamma }{2}$, where $|\rho q-p|\le \frac{N^{\gamma }}{16}$. This presents additional results over the work of de Weger (AAECC 2002). We also discuss how the lattice based idea of Boneh-Durfee (IEEE-IT 2000) works better to find weak keys beyond the bound $\delta <\frac{1}{2}-\frac{\gamma }{2}$. Further we show that, the RSA keys are weak when $d<\frac{1}{2}{N}^{\delta }$ and $e$ is $O(N^{\frac{3}{2}-2\delta })$ for $\delta \le \frac{1}{2}$. Using similar techniques we also present new results over the work of Blömer and May (PKC 2004).

Note: Substantial Revision.