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 \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 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 \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)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. ISC 2008, 11th Information Security Conference, September 15-18, 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
2009-02-20: last of 2 revisions
2008-05-26: received
See all versions
Short URL
https://ia.cr/2008/228
License
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.