Paper 2023/367

Practical Attacks on Small Private Exponent RSA: New Records and New Insights

Qiang Li, PLA Strategic Support Force Information Engineering University
Qun-xiong Zheng, PLA Strategic Support Force Information Engineering University
Wen-feng Qi, PLA Strategic Support Force Information Engineering University
Abstract

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. We believe our method can provide some inspiration to practical attacks on RSA with mainstream-size moduli.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Practical attackSmall private exponent attackMSBs guessMultivalued-continuous phenomenaBinary search
Contact author(s)
hnuliqiang @ 163 com
qunxiong_zheng @ 163 com
wenfeng qi @ 263 net
History
2023-03-16: approved
2023-03-14: received
See all versions
Short URL
https://ia.cr/2023/367
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/367,
      author = {Qiang Li and Qun-xiong Zheng and Wen-feng Qi},
      title = {Practical Attacks on Small Private Exponent RSA: New Records and New Insights},
      howpublished = {Cryptology ePrint Archive, Paper 2023/367},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/367}},
      url = {https://eprint.iacr.org/2023/367}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.