New Partial Key Exposure Attacks on CRT-RSA with Large Public Exponents

In Crypto'03, Blomer and May provided several partial key exposure attacks on CRT-RSA. In their attacks, they suppose that an attacker can either succeed to obtain the most significant bits (MSBs) or the least significant bits (LSBs) of d(p) = d mod (p - 1) in consecutive order. For the case of known LSBs of dp, their algorithm is polynomial-time only for small public exponents e (i.e. e = poly(log N)). However, in some practical applications, we prefer to use large e (Like e approximate to d(p), to let the public and private operations with the same computational effort). In this paper, we propose some lattice-based attacks for this extended setting. For known LSBs case, we introduce two approaches that work up to e < N-3/8. Similar results (though not as strong) are obtained for MSBs case. We also provide detailed experimental results to justify our claims.