Generalized cryptanalysis of small CRT-exponent RSA

摘要

There have been several works for studying the security of CRT-RSA with small CRT exponents d(p) and d(q) by using lattice-based Coppersmith's method. Thus far, two attack scenarios have been mainly studied: (1) d(q) is small with unbalanced prime factors p q. (2) Both d(p) and d(q) are small for balanced p approximate to q. The best attacks for the both scenarios were proposed by Takayasu-Lu-Peng (Eurocrypt'17. Journal of Cryptology'19) and the attack conditions are much better than the other known attacks. Although the attacks have been very useful for studying the security of CRT-RSA, the structures of their proposed lattices are not well understood. In this paper, to further study the security of CRT-RSA, we first define a generalized attack scenario to unify the previous ones. Specifically, all p, q, d(p), and d(q) can be of arbitrary sizes. Furthermore, we propose improved attacks in this paper when d(p) and/or p is sufficiently small. Technically, we construct a lattice whose basis vectors are chosen flexibly depending on the sizes of p, q, d(p), and d(q). Since the attack scenarios (1) and (2) are simpler than our general scenario, the previous Takayasu-Lu-Peng's lattices are simple special cases of ours. We are able to achieve the flexible lattice constructions by exploiting implicit but essential structures of Takayasu-Lu-Peng's lattices. We check the validity of our proposed attacks by computer experiments. We believe that the deeper understanding of the lattice structures will be useful for studying the security of CRT-RSA even in other scenarios. (C) 2019 Elsevier B.V. All rights reserved.