CryptoDB
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 (IEEEIT, 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 BonehDurfee (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{eprint200817905,
title={Revisiting Wiener's Attack  New Weak Keys in RSA},
booktitle={IACR Eprint archive},
keywords={publickey cryptography / Cryptanalysis, RSA, Factorization, Weak Keys.},
url={http://eprint.iacr.org/2008/228},
note={ISC 2008, 11th Information Security Conference, September 1518, 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
}