Paper 2017/092

Small CRT-Exponent RSA Revisited

Atsushi Takayasu, 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. (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.

Note: The result of Section 4 was improved.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in EUROCRYPT 2017
Keywords
CRT-RSAcryptanalysisCoppersmith's methodlattices
Contact author(s)
takayasu @ mist i u-tokyo ac jp
History
2017-07-26: last of 3 revisions
2017-02-10: received
See all versions
Short URL
https://ia.cr/2017/092
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/092,
      author = {Atsushi Takayasu and Yao Lu and Liqiang Peng},
      title = {Small CRT-Exponent RSA Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2017/092},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/092}},
      url = {https://eprint.iacr.org/2017/092}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.