# Low Private Exponent

## Wiener Attack

**Wiener Attack** works when the private exponent $$d$$ is small. How small? If the private component $$d$$ satisfies:

$$
d < \frac{1}{3}n^{\frac{1}{4}}
$$

then we can use Wiener's Attack to get the flag.

The idea behind Wiener's Attack is **continued fraction**. In the context of CTF, we don't need to worry about the underlying theory since this attack is already implemented in the package `oWiener`. Install it with `pip3 install owiener`. Read more about this implementation here:

{% embed url="<https://github.com/orisano/owiener>" %}
owiener
{% endembed %}

```python
#!/usr/bin/env python3
import owiener
from Crypto.Util.number import long_to_bytes

#--------Data--------#

N = <N>
e = <e>
c = <c>

#--------Wiener's attack--------#

d = owiener.attack(e, N)

if d:
    m = pow(c, d, N)
    flag = long_to_bytes(m).decode()
    print(flag)
else:
    print("Wiener's Attack failed.")
```

## Boneh-Durfee Attack

**Boneh-Durfee Attack** also works when the private component $$d$$ is small, but it relaxes the restriction to another level compared to Wiener's Attack. If the private component $$d$$ satisfies:

$$
d < N^{0.292}
$$

then we can use Boneh-Durfee Attack to get the flag.

This attack is implemented in Sage. The code can be found here:

{% embed url="<https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage>" %}
Boneh-Durfee Attack (Sage implementation)
{% endembed %}