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

Journal of Inforamtion Science and Engineering, Vol.18 No.1, pp.1-18 (January 2002)

On the Design of RSA With Short Secret Exponent

Hung-Min Sun, Wu-Chuan Yang* and Chi Sung Laih*
Department of Computer Science and Information Engineering
National Cheng Kung University
Tainan, 701 Taiwan
E-mail: hmsun@mail.ncku.edu
*Department of Electrical Engineering
National Cheng Kung University
Tainan, 701 Taiwan
E-mail: wcyang77@ms32.hinet.net
E-mail: laihc@eembox.ncku.edu.tw

Based on continued fractions Wiener showed that a typical RSA system can be totally broken if its secret exponent d < where N is the RSA modulus. Recently, based on lattice basis reduction, Boneh and Durfee presented a new short secret exponent attack which improves Wieners bound up to d < . In this paper we show that it is possible to use a short secret exponent which is lower than these bounds while not compromising the security of RSA, provided that p and q differ in size and are large enough to defend against factoring algorithms. As an example, an RSA system with d of 192 bits, p of 256 bits, and q of 768 bits is secure against all the existing short secret exponent attacks. On the other hand, in order to balance between and minimize the overall computation of encryption and decryption, we propose a secure variant of RSA such that both e and d are the same size, e.g., ? ? 568 for a 1024-bit RSA modulus. Moreover, a generalization of this variant is presented for designing the RSA system with + ? ( ) + where is a predetermined constant, e.g., 112. Compared with a typical RSA system in which e is the same order of magnitude as N if d is first selected, these variants of RSA have the advantage that the overall computation can be significantly reduced. As an example, we can construct a secure RSA system with p of 256 bits, q of 768 bits, d of 256 bits, and e of 880 bits.

Keywords: data encryption and cryptography, RSA, short secret exponent, continued fraction, lattice basis reduction

Full Text () Retrieve PDF document (200201_01.pdf)

Received October 12, 1999; accepted June 5, 2000.
Communicated by Hsu-Chun Yen.