Generalized cryptanalysis of small CRT-exponent RSA

Autor: Atsushi Takayasu, Liqiang Peng
Rok vydání: 2019
Předmět:
Zdroj: Theoretical Computer Science. 795:432-458
ISSN: 0304-3975
DOI: 10.1016/j.tcs.2019.07.031
Popis: 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 ≈ 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.
Databáze: OpenAIRE
Externí odkaz: