A Unified Framework for Small Secret Exponent Attack on RSA

Noboru KUNIHIRO; Naoyuki SHINOHARA; Tetsuya IZU

doi:10.1587/transfun.E97.A.1285

A Unified Framework for Small Secret Exponent Attack on RSA

Noboru KUNIHIRO, Naoyuki SHINOHARA, Tetsuya IZU

Full Text Views

0

Cite this

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 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≤N^0.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≤N^0.292. In this paper, we first give an elementary proof for achieving Blömer-May'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ö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≤N^0.292 is still optimal in our unified framework.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E97-A No.6 pp.1285-1295

Publication Date: 2014/06/01

Publicized

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

Authors

Noboru KUNIHIRO
  The University of Tokyo
Naoyuki SHINOHARA
  NICT
Tetsuya IZU
  Fujitsu Laboratories

Keyword

LLL algorithm, small inverse problem, RSA, lattice-based cryptanalysis

Cite this

Copy

Noboru KUNIHIRO, Naoyuki SHINOHARA, Tetsuya IZU, "A Unified Framework for Small Secret Exponent Attack on RSA" in IEICE TRANSACTIONS on Fundamentals, vol. E97-A, no. 6, pp. 1285-1295, June 2014, doi: 10.1587/transfun.E97.A.1285.
Abstract: 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 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≤N^0.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≤N^0.292. In this paper, we first give an elementary proof for achieving Blömer-May'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ö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≤N^0.292 is still optimal in our unified framework.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E97.A.1285/_p

Copy

@ARTICLE{e97-a_6_1285,
author={Noboru KUNIHIRO, Naoyuki SHINOHARA, Tetsuya IZU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={A Unified Framework for Small Secret Exponent Attack on RSA},
year={2014},
volume={E97-A},
number={6},
pages={1285-1295},
abstract={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 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≤N^0.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≤N^0.292. In this paper, we first give an elementary proof for achieving Blömer-May'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ö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≤N^0.292 is still optimal in our unified framework.},
keywords={},
doi={10.1587/transfun.E97.A.1285},
ISSN={1745-1337},
month={June},}

Copy

TY - JOUR
TI - A Unified Framework for Small Secret Exponent Attack on RSA
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1285
EP - 1295
AU - Noboru KUNIHIRO
AU - Naoyuki SHINOHARA
AU - Tetsuya IZU
PY - 2014
DO - 10.1587/transfun.E97.A.1285
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E97-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2014
AB - 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 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≤N^0.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≤N^0.292. In this paper, we first give an elementary proof for achieving Blömer-May'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ö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≤N^0.292 is still optimal in our unified framework.
ER -