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

• Published in: Designs, codes, and cryptography codes, and cryptography, 2023-12, Vol.91 (12), p.4107-4142
• Main Authors: Li, Qiang, Zheng, Qun-xiong, Qi, Wen-feng
• Format: Article
• Language: English
• Subjects: Algorithms; Coding and Information Theory; Computer Science; Cryptography; Cryptology; Discrete Mathematics in Computer Science; Search methods; Upper bounds
• ISSN: 0925-1022; 1573-7586
• DOI: 10.1007/s10623-023-01295-5

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.