On the Design of RSA with Short Secret Exponent

At Eurocrypt’99, Boneh and Durfee presented a new short secret exponent attack which improves Wiener’s bound (d < N0.25) up to d < N0.292. 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₂e ≈ log₂d ≈ 568 for a 1024-bit RSA modulus. Moreover, a generalization of this variant is presented to design the RSA system with log₂e + log₂d ≈ log₂N + l _k where l _k 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.