Cryptanalysis of ‘Less Short’ RSA Secret Exponents

 In some applications of RSA, it is desirable to have a short secret exponent d. Wiener [6], describes a technique to use continued fractions (CF) in a cryptanalytic attack on an RSA cryptosystem having a ‘short’ secret exponent. Let n=p ⋅ q be the modulus of the system. In the typical case that G=gcd(p−1, q−1) is small. Wiener’s method will give the secret exponent d when d does not exceed (approximately) n ^1/4.

Here, we describe a general method to compute the CF-convergents of the continued fraction expansion of the same number as in Wiener (which has denominator d ⋅ G) up to the point where the denominator of the CF-convergent exceeds approximately n ^1/4. When d<n ^1/4 this technique determines d, p, and q as does Wiener’s method. For larger values of d there is still information available on the secret key. An estimate is made of the remaining workload to determine d, p and q. Roughly speaking this workload corresponds to an exhaustive search for about 2r+8 bit, where r=ln₂ d/n ^1/4.

Authors and Affiliations

1. Department of the Interior, P.O. Box 20010, NL-2500 EA The Hague, The Netherlands (e-mail: eric.verheul@pobox.com), , , , , , NL

   Eric R. Verheul

2. Department of Mathematics and Computing Science, Eindhoven University of Technology, P.O. Box 513, NL-5600 MB Eindhoven, The Netherlands (e-mail: henkvt@win.tue.nl), , , , , , NL

   Henk C. A. van Tilborg

Received: September 30, 1996; revised version: March 7, 1997

Reprints and permissions