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:

GitHub - orisano/owiener: A Python3 implementation of the Wiener attack on RSAGitHub

owiener

#!/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:

RSA-and-LLL-attacks/boneh_durfee.sage at master · mimoo/RSA-and-LLL-attacksGitHub

Boneh-Durfee Attack (Sage implementation)