International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Subhamoy Maitra
Santanu Sarkar
Download:
URL: http://eprint.iacr.org/2008/228
Search ePrint
Search Google
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 \leq \delta \leq 0.5$. We use both the upper and lower bounds on $\phi(N)$ and then try to find out what are the cases when $\frac{t}{d}$ is a convergent in the CF expression of $\frac{e}{N - \frac{3}{\sqrt{2}} \sqrt{N} + 1}$. First we show that the RSA keys are weak when $d = N^\delta$ and $\delta < \frac{3}{4} - \gamma - \tau$, where $2q - p = N^\gamma$ and $\tau$ is a small value based on certain parameters. This presents additional results over the work of de Weger (AAECC 2002). We also discuss how the idea of Boneh-Durfee (Eurocrypt 1999) works better to find weak keys beyond the bound $\delta < \frac{3}{4} - \gamma - \tau$. 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 \leq \frac{1}{2}$. Using similar idea we also present new results over the work of Bl{\"o}mer and May (PKC 2004).
BibTeX
@misc{eprint-2008-17905,
  title={Revisiting Wiener's Attack -- New Weak Keys in RSA},
  booktitle={IACR Eprint archive},
  keywords={public-key cryptography / Cryptanalysis, RSA, Factorization, Weak Keys.},
  url={http://eprint.iacr.org/2008/228},
  note={ISC 2008, 11th Information Security Conference, September 15-18, 2008, Taipei, Taiwan, to be published in Lecture Notes in Computer Science, Springer, 2008. subho@isical.ac.in 14071 received 19 May 2008, last revised 10 Jul 2008},
  author={Subhamoy Maitra and Santanu Sarkar},
  year=2008
}