Small CRT-Exponent RSA Revisited

摘要

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.