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 (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$. Given $\rho$ $(1 \leq \rho \leq 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 \leq \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 BonehDurfee (IEEEIT 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 \leq \frac{1}{2}$. Using similar techniques we also present new results over the work of Blömer and May (PKC 2004).
Note: Substantial Revision.
Metadata
 Available format(s)
 Category
 Publickey cryptography
 Publication info
 Published elsewhere. ISC 2008, 11th Information Security Conference, September 1518, 2008, Taipei, Taiwan, to be published in Lecture Notes in Computer Science, Springer, 2008.
 Keywords
 CryptanalysisRSAFactorizationWeak Keys.
 Contact author(s)
 subho @ isical ac in
 History
 20090220: last of 2 revisions
 20080526: received
 See all versions
 Short URL
 https://ia.cr/2008/228
 License

CC BY
BibTeX
@misc{cryptoeprint:2008/228, author = {Subhamoy Maitra and Santanu Sarkar}, title = {Revisiting Wiener's Attack  New Weak Keys in {RSA}}, howpublished = {Cryptology ePrint Archive, Paper 2008/228}, year = {2008}, note = {\url{https://eprint.iacr.org/2008/228}}, url = {https://eprint.iacr.org/2008/228} }