Paper 2016/1056

A Tool Kit for Partial Key Exposure Attacks on RSA

Atsushi Takayasu and Noboru Kunihiro

Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. CT-RSA 2017
Keywords
(Multi-Prime) RSApartial key exposurelatticesCoppersmith's methods
Contact author(s)
a-takayasu @ it k u-tokyo ac jp
History
2016-11-15: received
Short URL
https://ia.cr/2016/1056
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1056,
      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{https://eprint.iacr.org/2016/1056}},
      url = {https://eprint.iacr.org/2016/1056}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.