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

Journal of Inforamtion Science and Engineering, Vol.12 No.2, pp.277-290 (June 1996)
Cryptanalysis of the Secret Exponent
of the RSA Scheme

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 JISE. 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.