IEICE TRANSACTIONS on Fundamentals
A Unified Framework for Small Secret Exponent Attack on RSA
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.
- 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
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 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.
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 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.},
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 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.
ER -
English
