Paper 2016/1056

A Tool Kit for Partial Key Exposure Attacks on RSA

Atsushi Takayasu and Noboru Kunihiro


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.CT-RSA 2017
(Multi-Prime) RSApartial key exposurelatticesCoppersmith's methods
Contact author(s)
a-takayasu @ it k u-tokyo ac jp
2016-11-15: received
Short URL
Creative Commons Attribution


      author = {Atsushi Takayasu and Noboru Kunihiro},
      title = {A Tool Kit for Partial Key Exposure Attacks on RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1056},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.