Chien-Yuan Chen, Chin-Chen Chang* and Wei-Pang Yang
Institute of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
*Institute of Computer Science and Information Engineering
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.