Cryptology ePrint Archive: Report 2017/092

Small CRT-Exponent RSA Revisited

Atsushi Takayasu and Yao Lu and Liqiang Peng

Abstract: Since May (Crypto'02) revealed the vulnerability of the small CRT-exponent RSA using Coppersmith's lattice-based method, several papers have studied the problem and two major improvements have been made. Bleichenbacher and May (PKC'06) proposed an attack for small $d_q$ when the prime factor $p$ is significantly smaller than the other prime factor $q$; the attack works for $p<N^{0.468}$. Jochemsz and May (Crypto'07) proposed an attack for small $d_p$ and $d_q$ where the prime factors $p$ and $q$ are balanced; the attack works for $d_p,d_q<N^{0.073}$. Even after a decade has passed since their proposals, the above two attacks are still considered to be the state-of-the-art, and no improvements have been made thus far. A novel technique seems to be required for further improvements since the attacks have been studied with all the applicable techniques for Coppersmith's methods proposed by Durfee-Nguyen (Asiacrypt'00), Jochemsz-May (Asiacrypt'06), and Herrmann-May (Asiacrypt'09, PKC'10). In this paper, we propose two improved attacks on the small CRT-exponent RSA: a small $d_q$ attack for $p<N^{0.5}$ (an improvement of Bleichenbacher-May's) and a small $d_p$ and $d_q$ attack for $d_p,d_q<N^{0.091}$ (an improvement of Jochemsz-May's). We use Coppersmith's lattice-based method to solve modular equations and obtain the improvements from a novel lattice construction by exploiting useful algebraic structures of the CRT-RSA key generation. We explicitly show proofs of our attacks and verify the validities by computer experiments. In addition to the two main attacks, we propose small $d_q$ attacks on several variants of RSA.

Category / Keywords: CRT-RSA, cryptanalysis, Coppersmith's method, lattices

Original Publication (in the same form): IACR-EUROCRYPT-2017