Previous | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] |

Cryptanalysis of the Secret Exponent

of the RSA Scheme

**Chien-Yuan Chen, Chin-Chen Chang ^{*} and Wei-Pang Yang**

National Chiao Tung University

Hsinchu, Taiwan 300, R.O.C.

National Chung Cheng University

Chiayi, Taiwan 621, R.O.C.

In this paper, we present a cryptanalytic attack on large RSA secret exponents. Let e and N denote the public exponent and the modulus of the RSA scheme, respectively. This attack uses the continued fraction algorithm to find an estimate of a fraction which involves the secret exponent d from a known close enough estimate of a fraction e/N. According to our proposed attack, the large secret exponent d can be discovered if e < N and . Furthermore, if the secret exponent is close to £f(N)/2, or even if it is close to some other critical value, it will be discovered.

Keywords: the RSA scheme, the continued fraction algorithm

Received July 22, 1994; revised August 4, 1995.

Communicated by C. L. Liu.