# Implementation of Coppersmith attack (RSA attack using lattice reductions)

## posted February 2015

I've implemented the work of **Coppersmith** (to be correct the reformulation of his attack by **Howgrave-Graham**) in Sage.

You can see the code here on github.

I won't go too much into the details because this is for a later post, but you can use such an attack on several **relaxed RSA models** (meaning you have partial information, you are not totally in the dark).

I've used it in two examples in the above code:

## Stereotyped messages

For example if **you know the most significant bits of the message**. You can **find the rest of the message** with this method.

The usual RSA model is this one: you have a ciphertext `c`

a modulus `N`

and a public exponent `e`

. Find `m`

such that `m^e = c mod N`

.

Now, this is the **relaxed model** we can solve: you have `c = (m + x)^e`

, you know a part of the message, `m`

, but you don't know `x`

.
For example the message is always something like "*the password today is: [password]*".
Coppersmith says that if you are looking for `N^1/e`

of the message it is then a `small root`

and you should be able to find it pretty quickly.

let our polynomial be `f(x) = (m + x)^e - c`

which has a root we want to find `modulo N`

. Here's how to do it with my implementation:

```
dd = f.degree()
beta = 1
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon))
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
```

You can play with the values until it finds the root. The default values should be a good start. If you want to tweak:

- beta is always 1 in this case.
`XX`

is your upper bound on the root.**The bigger is the unknown, the bigger XX should be**. And the bigger it is... the more time it takes.

## Factoring with high bits known

Another case is factoring `N`

knowing high bits of `q`

.

The Factorization problem normally is: give `N = pq`

, find `q`

. In our **relaxed** model we know an approximation `q'`

of `q`

.

Here's how to do it with my implementation:

let `f(x) = x - q'`

which has a root `modulo q`

.

This is because `x - q' = x - ( q + diff ) = x - diff mod q`

with the difference being `diff = | q - q' |`

.

```
beta = 0.5
dd = f.degree()
epsilon = beta / 7
mm = ceil(beta**2 / (dd * epsilon))
tt = floor(dd * mm * ((1/beta) - 1))
XX = ceil(N**((beta**2/dd) - epsilon)) + 1000000000000000000000000000000000
roots = coppersmith_howgrave_univariate(f, N, beta, mm, tt, XX)
```

What is important here if you want to find a solution:

- we should have
`q >= N^beta`

- as usual
`XX`

is the upper bound of the root, so the difference should be:`|diff| < XX`