Welcome to the resource topic for 2023/367
Title:
Practical Attacks on Small Private Exponent RSA: New Records and New Insights
Authors: Qiang Li, Qun-xiong Zheng, Wen-feng Qi
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.
ePrint: https://eprint.iacr.org/2023/367
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .