Practical attacks on small private exponent RSA: new records and new insights

As a typical representative of the public key cryptosystem, RSA has attracted a great deal of cryptanalysis since its invention, among which a famous attack is the small private exponent attack. It is well-known that the best theoretical upper bound for the private exponent d that can be attacked is d <= N-0.292, where N is a RSA modulus. However, this bound may not be achieved in practical attacks since the lattice constructed by Coppersmith method may have a large enough dimension and the lattice-based reduction algorithms cannot work so well in both efficiency and quality. In this paper, we propose a new practical attack based on the binary search for the most significant bits (MSBs) of prime divisors of N and the Herrmann-May's attack in 2010. The idea of binary search is inspired by the discovery of phenomena called "multivalued-continuous phenomena", which can significantly accelerate our attack. Together with several carefully selected parameters according to our exact and effective numerical estimations, we can improve the upper bound of d that can be practically achieved. More specifically, without the binary search method, we successfully attack RSA with a 1024-bit-modulus N when d <= N-0.285. Moreover, by our new method, we can implement a successful attack for a 1024-bit-modulus RSA when d = N-0.292 and for a 2048-bit-modulus RSA when d <= N-0.287 in about a month. We believe our method can provide some inspiration to practical attacks on RSA with mainstream-size moduli.