2006 | OriginalPaper | Buchkapitel
New Attacks on RSA with Small Secret CRT-Exponents
verfasst von : Daniel Bleichenbacher, Alexander May
Erschienen in: Public Key Cryptography - PKC 2006
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
It is well-known that there is an efficient method for decrypting/signing with RSA when the secret exponent
d
is small modulo
p
–1 and
q
–1. We call such an exponent
d
a small CRT-exponent. It is one of the major open problems in attacking RSA whether there exists a polynomial time attack for small CRT-exponents, i.e. a result that can be considered as an equivalent to the Wiener and Boneh-Durfee bound for small
d
. At Crypto 2002, May presented a partial solution in the case of an RSA modulus
N
=
pq
with unbalanced prime factors
p
and
q
. Based on Coppersmith’s method, he showed that there is a polynomial time attack provided that
q
<
N
0.382
. We will improve this bound to
q
<
N
0.468
. Thus, our result comes close to the desired normal RSA case with balanced prime factors. We also present a second result for balanced RSA primes in the case that the public exponent
e
is significantly smaller than
N
. More precisely, we show that there is a polynomial time attack if
$d_{p}, d_{q} \leq min\{(N/e)^{\frac{2}{5}},N^{\frac{1}{4}}\}$
. The method can be used to attack two fast RSA variants recently proposed by Galbraith, Heneghan, McKee, and by Sun, Wu.