Paper 2011/591

A Unified Framework for Small Secret Exponent Attack on RSA

Noboru Kunihiro, Naoyuki Shinohara, and Tetsuya Izu

Abstract

We address a lattice based method on small secret exponent attack on RSA scheme. Boneh and Durfee reduced the attack into finding small roots of a bivariate modular equation: $x(N+1+y)+1 ¥equiv 0 mod e)$, where $N$ is an RSA moduli and $e$ is the RSA public key. Boneh and Durfee proposed a lattice based algorithm for solving the problem. When the secret exponent $d$ is less than $N^{0.292}$, their method breaks RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Bl¥"omer and May gave an alternative algorithm. Although their bound $d ¥leq N^{0.290}$ is worse than Boneh--Durfee result, their method used a full rank lattice. However, the proof for their bound is still complicated. Herrmann and May gave an elementary proof for the Boneh--Durfee's bound: $d ¥leq N^{0.292}$. In this paper, we first give an elementary proof for achieving the bound of Bl¥"omer--May: $d ¥leq N^{0.290}$. Our proof employs unravelled linearization technique introduced by Herrmann and May and is rather simpler than Bl¥"omer--May's proof. Then, we provide a unified framework to construct a lattice that are used for solving the problem, which includes two previous method: Herrmann--May and Bl¥"omer--May methods as a special case. Furthermore, we prove that the bound of Boneh--Durfee: $d ¥leq N^{0.292}$ is still optimal in our unified framework.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. This is a full version of SAC2011 paper.
Keywords
lattice techniquesRSAcryptanalysis
Contact author(s)
kunihiro @ k u-tokyo ac jp
History
2011-11-03: received
Short URL
https://ia.cr/2011/591
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/591,
      author = {Noboru Kunihiro and Naoyuki Shinohara and Tetsuya Izu},
      title = {A Unified Framework for Small Secret Exponent Attack on RSA},
      howpublished = {Cryptology ePrint Archive, Paper 2011/591},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/591}},
      url = {https://eprint.iacr.org/2011/591}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.