2013 | OriginalPaper | Buchkapitel
An Attack on RSA Using LSBs of Multiples of the Prime Factors
verfasst von : Abderrahmane Nitaj
Erschienen in: Progress in Cryptology – AFRICACRYPT 2013
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Let
N
=
pq
be an RSA modulus with a public exponent
e
and a private exponent
d
. Wiener’s famous attack on RSA with
d
<
N
0.25
and its extension by Boneh and Durfee to
d
<
N
0.292
show that using a small
d
makes RSA completely insecure. However, for larger
d
, it is known that RSA can be broken in polynomial time under special conditions. For example, various partial key exposure attacks on RSA and some attacks using additional information encoded in the public exponent
e
are efficient to factor the RSA modulus. These attacks were later improved and extended in various ways. In this paper, we present a new attack on RSA with a public exponent
e
satisfying an equation
ed
−
k
(
N
+ 1 −
ap
−
bq
) = 1 where
$\frac{a}{b}$
is an unknown approximation of
$\frac{q}{p}$
. We show that RSA is insecure when certain amount of the Least Significant Bits (LSBs) of
ap
and
bq
are known. Further, we show that the existence of good approximations
$\frac{a}{b}$
of
$\frac{q}{p}$
with small
a
and
b
substantially reduces the requirement of LSBs of
ap
and
bq
.