# Implementation of Boneh and Durfee attack on RSA's low private exponents

## posted March 2015

I've Implemented a Coppersmith-type attack (using LLL reductions of lattice basis). It was done by **Boneh and Durfee** and later simplified by **Herrmann and May**. The program can be found on my github.

The attack allows us to break RSA and the private exponent `d`

.
Here's why RSA works (where `e`

is the public exponent, `phi`

is euler's totient function, `N`

is the public modulus):

\[ ed = 1 \pmod{\varphi(N)} \] \[ \implies ed = k \cdot \varphi(N) + 1 \text{ over } \mathbb{Z} \] \[ \implies k \cdot \varphi(N) + 1 = 0 \pmod{e} \] \[ \implies k \cdot (N + 1 - p - q) + 1 = 0 \pmod{e} \] \[ \implies 2k \cdot (\frac{N + 1}{2} + \frac{-p -q}{2}) + 1 = 0 \pmod{e} \]

The last equation gives us a bivariate polynomial \( f(x,y) = 1 + x \cdot (A + y) \). Finding the roots of this polynomial will allow us to easily compute the private exponent `d`

.

The attack works if the private exponent `d`

is too small compared to the modulus: \( d < N^{0.292} \).

To use it:

- look at the tests in boneh_durfee.sage and make your own with your own values for the public exponent
`e`

and the public modulus`N`

. - guess how small the private exponent
`d`

is and modify`delta`

so you have`d < N^delta`

- tweak
`m`

and`t`

until you find something. You can use Herrmann and May optimized`t = tau * m`

with`tau = 1-2*delta`

. Keep in mind that the bigger they are, the better it is, but the longer it will take. Also we must have`1 <= t <= m`

. - you can also decrease
`X`

as it might be too high compared to the root of`x`

you are trying to find. This is a last recourse tweak though.

Here is the tweakable part in the code:

```
# Tweak values here !
delta = 0.26 # so that d < N^delta
m = 3 # x-shifts
t = 1 # y-shifts # we must have 1 <= t <= m
```

## ralpo08

There's a mistake on the fourth line of the equations:

\varphi(N) = (p - 1).(q-1) = p.q - p - q + 1 = N - p - q + 1

## david

good catch! Thanks