
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

A Unified Framework for Small Secret Exponent Attack on RSA
Noboru KUNIHIRO Naoyuki SHINOHARA Tetsuya IZU
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E97A
No.6
pp.12851295 Publication Date: 2014/06/01
Online ISSN: 17451337
DOI: 10.1587/transfun.E97.A.1285
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: LLL algorithm, small inverse problem, RSA, latticebased cryptanalysis,
Full Text: PDF(521.9KB)>>
Summary:
In this paper, we present a lattice based method on small secret exponent attack on the RSA scheme. Boneh and Durfee reduced the attack to finding the small roots of the bivariate modular equation: x(N+1+y)+1 ≡ 0 (mod e), where N is an RSA modulus and e is the RSA public key and proposed a lattice based algorithm for solving the problem. When the secret exponent d is less than N^{0.292}, their method breaks the RSA scheme. Since the lattice used in the analysis is not fullrank, the analysis is not easy. Blömer and May proposed an alternative algorithm that uses a fullrank lattice, even though it gives a bound (d≤N^{0.290}) that is worse than BonehDurfee. However, the proof for their bound is still complicated. Herrmann and May, however, have given an elementary proof for the BonehDurfee's bound: d≤N^{0.292}. In this paper, we first give an elementary proof for achieving BlömerMay's bound: d≤N^{0.290}. Our proof employs the unravelled linearization technique introduced by Herrmann and May and is rather simpler than that of BlömerMay's proof. We then provide a unified framework — which subsumes the two previous methods, the HerrmannMay and the BlömerMay methods, as a special case — for constructing a lattice that can be are used to solve the problem. In addition, we prove that BonehDurfee's bound: d≤N^{0.292} is still optimal in our unified framework.

