Abstract
At Eurocrypt'99, Boneh and Durfee presented a new short secret exponent attack which improves Wiener's bound (d<N <sup>0.25</sup> ) up to d<N <sup>0.292</sup> . In this paper we show that it is possible to use a short secret exponent which is below these bounds while not compromising with the security of RSA provided that p and q are differing in size and are large enough to combat factoring algorithms. As an example, the 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. Besides, in order to balance and minimize the overall computations between encryption and decryption, we propose a variant of RSA such that both e and d are of the same size, e.g., log <sub>2</sub> e ≈ log <sub>2</sub> d ≈ 568 for a 1024-bit RSA modulus. Moreover, a generalization of this variant is presented to design the RSA system with e log <sub>2</sub> + d log <sub>2</sub> ≈ N log <sub>2</sub> + l <sub>k</sub> where l <sub>k</sub> is a predetermined constant, e.g., 112. 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.