New Attacks on RSA with Small Secret CRT-Exponents

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.