A New Attack on RSA and CRT-RSA

In RSA, the public modulus

N

 = 

pq

is the product of two primes of the same bit-size, the public exponent

e

and the private exponent

d

satisfy

$ed\equiv 1 \pmod{(p - 1)(q - 1)}$

. In many applications of RSA,

d

is chosen to be small. This was cryptanalyzed by Wiener in 1990 who showed that RSA is insecure if

d

 < 

N

0.25

. As an alternative, Quisquater and Couvreur proposed the CRT-RSA scheme in the decryption phase, where

$d_p = d \pmod{(p - 1)}$

and

$d_q = d \pmod{(q - 1)}$

are chosen significantly smaller than

p

and

q

. In 2006, Bleichenbacher and May presented an attack on CRT-RSA when the CRT-exponents

d

p

and

d

q

are both suitably small. In this paper, we show that RSA is insecure if the public exponent

e

satisfies an equation

$ex+y\equiv 0\pmod p$

with

$|x||y|<N^{\frac{\sqrt{2}-1}{2}}$

and

$ex+y\not\equiv 0\pmod N$

. As an application of our new attack, we present the cryptanalysis of CRT-RSA if one of the private exponents,

d

p

say, satisfies

$d_p<\frac{N^\frac{\sqrt{2}}{4}}{\sqrt{e}}$

. This improves the result of Bleichenbacher and May on CRT-RSA where both

d

p

and

d

q

are required to be suitably small.