Welcome to the resource topic for 2008/228
Title:
Revisiting Wiener’s Attack – New Weak Keys in RSA
Authors: Subhamoy Maitra, 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).
ePrint: https://eprint.iacr.org/2008/228
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .