A Unified Framework for Small Secret Exponent Attack on RSA

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 (\bmod\; 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ömer and May gave an alternative algorithm. Although their bound

d

 ≤ 

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

 ≤ 

N

0.292

. In this paper, we first give an elementary proof for achieving the bound of Blömer–May:

d

 ≤ 

N

0.290

. Our proof employs unravelled linearization technique introduced by Herrmann and May and is rather simpler than Blömer–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ömer–May methods as a special case. Furthermore, we prove that the bound of Boneh–Durfee:

d

 ≤ 

N

0.292

is still optimal in our unified framework.