A Tool Kit for Partial Key Exposure Attacks on RSA

Thus far, partial key exposure attacks on RSA have been intensively studied using lattice based Coppersmith’s methods. In the context, attackers are given partial information of a secret exponent and prime factors of (Multi-Prime) RSA where the partial information is exposed in various ways. Although these attack scenarios are worth studying, there are several known attacks whose constructions have similar flavor. In this paper, we try to formulate general attack scenarios to capture several existing ones and propose attacks for the scenarios. Our attacks contain all the state-of-the-art partial key exposure attacks, e.g., due to Ernst et al. (Eurocrypt’05) and Takayasu-Kunihiro (SAC’14, ICISC’14), as special cases. As a result, our attacks offer better results than previous best attacks in some special cases, e.g., Sarkar-Maitra’s partial key exposure attacks on RSA with the most significant bits of a prime factor (ICISC’08) and Hinek’s partial key exposure attacks on Multi-Prime RSA (J. Math. Cryptology ’08). We claim that our contribution is not only generalizations or improvements of the existing results. Since our attacks capture general exposure scenarios, the results can be used as a tool kit; the security of some future variants of RSA can be examined without any knowledge of Coppersmith’s methods.