Welcome to the resource topic for 2017/092
Title:
Small CRT-Exponent RSA Revisited
Authors: Atsushi Takayasu, Yao Lu, 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. (1) 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}. (2) Jochemsz and May (Crypto’07) proposed an attack for small d_p and d_q when the prime factors p and q are balanced; the attack works for d_p, d_q<N^{0.073}. Even a decade has passed since their proposals, the above two attacks are still considered as the state-of-the-art, and no improvements have been made thus far. A novel technique seems to be required for further improvements since it seems that 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.122} (an improvement of Jochemsz-May’s). The latter result is also an improvement of our result in the proceeding version (Eurocrypt '17); d_p, d_q < N^{0.091}. 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 equation. We explicitly show proofs of our attacks and verify the validities by computer experiments. In addition to the two main attacks, we also propose small d_q attacks on several variants of RSA.
ePrint: https://eprint.iacr.org/2017/092
Talk: https://www.youtube.com/watch?v=fFH3AUwew1M
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .