On the Design of RSA with Short Secret Exponent

孫宏民(Hung-Min Sun) ； 楊吳泉(Wu-Chuan Yang) ； 賴溪松(Chi-Sung Laih)

《Journal of Information Science and Engineering》 18卷1期 (2002/01) Pp. 1-18

https://doi.org/10.6688/JISE.2002.18.1.1

並列摘要

Based on continued fractions Wiener showed that a typical RSA system can be totally broken if its secret exponent d＜N^0.25 where N is the RSA modulus. Recently, based on lattice basis reduction, Boneh and Durfee presented a new short secret exponent attack which improves Wiener's bound up to d＜N^0.292. 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 dare the same size, e.g., log2 e=log2 d=568 for a 1024-bit RSA modulus. Moreover, a generalization of this variant is presented for designing the RSA system with log2 e+log2 d=(log2 N)+l(subscript k) where l(subscript k) 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.

並列關鍵字

data encryption and cryptography ； RSA ； short secret exponent ； continued fraction ； lattice basis reduction