For Full-Text 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 RSANoboru KUNIHIRO  Naoyuki SHINOHARA  Tetsuya IZU  Publication IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E97-A   No.6   pp.1285-1295Publication Date: 2014/06/01 Online ISSN: 1745-1337 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,  lattice-based cryptanalysis,  Full Text: PDF(521.9KB)>> Buy this Article 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 N0.292, their method breaks the RSA scheme. Since the lattice used in the analysis is not full-rank, the analysis is not easy. Blömer and May proposed an alternative algorithm that uses a full-rank lattice, even though it gives a bound (d≤N0.290) that is worse than Boneh-Durfee. However, the proof for their bound is still complicated. Herrmann and May, however, have given an elementary proof for the Boneh-Durfee's bound: d≤N0.292. In this paper, we first give an elementary proof for achieving Blömer-May's bound: d≤N0.290. Our proof employs the unravelled linearization technique introduced by Herrmann and May and is rather simpler than that of Blömer-May's proof. We then provide a unified framework — which subsumes the two previous methods, the Herrmann-May and the Blömer-May methods, as a special case — for constructing a lattice that can be are used to solve the problem. In addition, we prove that Boneh-Durfee's bound: d≤N0.292 is still optimal in our unified framework.