RSA Attacks for CTF Cryptography

Introduction

RSA is the most frequently attacked cryptosystem in CTF competitions. When correctly implemented with large primes and proper padding, RSA is secure. But CTF challenges deliberately introduce subtle weaknesses: a tiny public exponent, a modulus with small prime factors, two ciphertexts sharing the same modulus, or a private exponent so small it can be recovered by a continued-fraction attack.

This guide covers the attacks you will encounter most often in picoCTF, roughly in order from simplest to most involved. Each section links directly to the picoCTF writeup where that attack was the key to solving the challenge.

RSA basics

Before attacking RSA you need to be comfortable reading the parameters you are given. A standard RSA public key consists of:

n  = p * q          # modulus (product of two large primes)
e  = 65537          # public exponent (usually 65537, sometimes 3)
c  = m^e mod n      # ciphertext
# To decrypt you need the private exponent d:
d  = e^-1 mod phi(n)   where phi(n) = (p-1)*(q-1)
m  = c^d mod n

The security of RSA depends entirely on the difficulty of factoring n. If an attacker can recover p and q, they can compute phi(n), then d, and decrypt any ciphertext.

Small public exponent (e=3 cube root attack)

When e=3 and the plaintext message m is small enough that m^3 < n, the ciphertext c = m^3 (without the modular reduction). You can recover the message simply by taking the integer cube root of c.

from gmpy2 import iroot
# c = m^3 when m^3 < n
m, exact = iroot(c, 3)
if exact:
    print(bytes.fromhex(hex(m)[2:]))

More generally, if e is small but m^e > n, you need to combine the cube root attack with Hastad's broadcast attack (multiple ciphertexts of the same message under different moduli) or use a Coppersmith short-pad attack.

Weak modulus (factoring n)

If n is small (under ~512 bits) or was generated from weak primes, you can factor it directly. Three reliable approaches:

FactorDB

FactorDB is a public database of pre-computed factorizations. Paste n into the website or query it programmatically:

pip install factordb-python
from factordb.factordb import FactorDB
f = FactorDB(n)
f.connect()
factors = f.get_factor_list()   # [p, q]

SageMath / PARI

# SageMath
factor(n)
# Python with sympy
from sympy import factorint
factorint(n)   # works for small n (~20 digits)

Once you have p and q

from Crypto.Util.number import long_to_bytes
phi = (p - 1) * (q - 1)
d   = pow(e, -1, phi)       # Python 3.8+ modular inverse
m   = pow(c, d, n)
print(long_to_bytes(m))

Common modulus attack

If the same plaintext m is encrypted under the same modulus n but two different public exponents e1 and e2 that are coprime to each other, you can recover mwithout knowing either private key.

The attack uses the extended Euclidean algorithm to find integers a and b such that a*e1 + b*e2 = 1, then combines the two ciphertexts:

from math import gcd
def extended_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x, y = extended_gcd(b, a % b)
    return g, y, x - (a // b) * y
_, a, b = extended_gcd(e1, e2)
# Handle negative exponents with modular inverse
if a < 0:
    c1 = pow(pow(c1, -1, n), -a, n)
    a  = -a
else:
    c1 = pow(c1, a, n)
if b < 0:
    c2 = pow(pow(c2, -1, n), -b, n)
    b  = -b
else:
    c2 = pow(c2, b, n)
m = (c1 * c2) % n

Wiener's attack (small private exponent)

When the private exponent d is small relative to n(specifically, when d < n^0.25 / 3), Wiener's theorem lets you recover d from the public key alone using the continued-fraction expansion of e/n.

This happens in challenges where the problem author set an unusually small d for "efficiency", or where e is enormous (close to phi(n)) which implies d is small.

pip install owiener
import owiener
d = owiener.attack(e, n)
if d is None:
    print('Wiener attack failed')
else:
    from Crypto.Util.number import long_to_bytes
    m = pow(c, d, n)
    print(long_to_bytes(m))

RSA oracle attack

Some challenges give you a server that will decrypt any ciphertext you send it, except the target ciphertext c. An RSA oracle attack (also called multiplicative homomorphism exploitation) works around this restriction by transforming c into a different ciphertext that decrypts to a related plaintext, then unwrapping the transformation.

Since RSA satisfies Enc(m1) * Enc(m2) = Enc(m1 * m2) mod n, you can multiply the ciphertext by an encryped blinding factor:

# Choose a random blinding factor r
r = 2
blinded_c = (c * pow(r, e, n)) % n   # = Enc(r * m)
# Ask the oracle to decrypt blinded_c
blinded_m = oracle_decrypt(blinded_c)
# Divide out the blinding factor
r_inv = pow(r, -1, n)
m = (blinded_m * r_inv) % n
from Crypto.Util.number import long_to_bytes
print(long_to_bytes(m))

Tools

pip install rsactftool
RsaCtfTool --n N --e E --uncipher C --attack all

pip install factordb-python

pip install pycryptodome

sudo apt install sagemath

Quick reference