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 dq when the prime factor p is significantly smaller than the other prime factor q; the attack works for p<N0.468. (2) Jochemsz and May (Crypto'07) proposed an attack for small dp and dq when the prime factors p and q are balanced; the attack works for dp,dq<N0.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 attack for (an improvement of Bleichenbacher-May's) and a small and attack for (an improvement of Jochemsz-May's). The latter result is also an improvement of our result in the proceeding version (Eurocrypt '17); . 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 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},
      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.