RSA Attacks

# Small public exponent (e=3) with small message
# If m^3 < n, then c = m^3 and m = cube_root(c)
from gmpy2 import iroot
m = iroot(c, 3)[0]

# Wiener's Attack - Small private exponent
# If d < n^0.25 / 3, can recover d
# Use: https://github.com/pablocelayes/rsa-wiener-attack

# Common modulus attack
# If same message encrypted with same n, different e
# Can recover message using extended GCD

# Fermat factorization - When p and q are close
def fermat_factor(n):
    a = isqrt(n) + 1
    b2 = a*a - n
    while not is_square(b2):
        a += 1
        b2 = a*a - n
    b = isqrt(b2)
    return a - b, a + b

# Check for known factored moduli
# https://factordb.com/

# Install RsaCtfTool
git clone https://github.com/RsaCtfTool/RsaCtfTool
cd RsaCtfTool
pip install -r requirements.txt

# Attack with public key
python RsaCtfTool.py --publickey pubkey.pem --uncipherfile ciphertext.bin

# Attack with n and e
python RsaCtfTool.py -n <modulus> -e <exponent> --uncipher <ciphertext>

# Try all attacks
python RsaCtfTool.py --publickey pubkey.pem --uncipherfile cipher.bin --attack all