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.

It helps to know where the real security line sits. NIST SP 800-57 Part 1 Rev. 5 puts a 2048-bit RSA modulus at roughly 112 bits of security and a 3072-bit modulus at 128 bits, and SP 800-131A Rev. 2 disallows anything below 2048 bits. The public factoring record is well under that: the team that factored RSA-250 in February 2020 broke an 829-bit modulus and spent about 2,700 core-years doing it. A CTF modulus you can factor in ten seconds is therefore not a small version of the real problem, it is a different problem: the challenge author left a structural flaw for you to find.

Broken RSA in the wild almost always comes from the same place. Lenstra and co-authors scanned millions of live public keys for "Ron was wrong, Whit is right" and found roughly 12,720 RSA moduli, about 0.2% of the set, that shared a prime factor with another key and so could be factored by taking a GCD. Four years earlier, CVE-2008-0166 had reduced Debian's OpenSSL key space to 32,767 possible keys per architecture. Bad randomness, not bad math.

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. For the symmetric half of CTF crypto (AES modes, ECB pattern leakage, CBC bit-flipping, CTR nonce reuse), see the companion AES for CTF post. For the other asymmetric family, where the hard problem is the discrete log instead of factoring, see the Diffie-Hellman for CTF post and the Elliptic Curves for CTF post. If the notation below is unfamiliar, the modular arithmetic for CTF post covers congruence, inverses, the totient, and the Chinese Remainder Theorem in one page.

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.

The default exponent is not arbitrary. 65537 is 2¹⁶ + 1, the fifth and largest known Fermat prime, and in binary it has only two bits set. Square-and-multiply therefore encrypts in 17 operations while still being large enough that me wraps the modulus for any realistic message. e = 3 is faster still and is exactly why the cube-root attack below exists.

Everything in this section is textbook RSA, which is the primitive and not the cryptosystem. RFC 8017 (PKCS #1 v2.2) specifies the padding schemes that make RSA safe to deploy: RSAES-OAEP for encryption and RSASSA-PSS for signatures. Every attack on this page assumes the padding is missing or the legacy PKCS #1 v1.5 scheme is in use, which is precisely how challenge authors set the board.

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
from Crypto.Util.number import long_to_bytes
 
# c = m^3 when m^3 < n
m, exact = iroot(c, 3)
if exact:
    print(long_to_bytes(int(m)))

More generally, if e is small but m^e > n, you need to combine the cube root attack with Hastad's broadcast attack or use a Coppersmith short-pad attack. Both have a precise entry price. Hastad needs the same message encrypted under at least e distinct moduli, so three ciphertexts for e = 3, after which the Chinese Remainder Theorem reassembles m3 below the product of the moduli and an ordinary integer cube root finishes it. Coppersmith's 1996 lattice method recovers a root smaller than n^1/e, which is why it can repair a message where only a fraction of the bits are unknown. This is also the exact failure RFC 8017 prevents: OAEP makes every encryption of the same plaintext a different, full-width integer.

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:

Before reaching for a tool, spend ten seconds on the cheap structural checks, because challenge moduli usually fail one of them. Is n even (then p = 2)? Is it a perfect square or a perfect power? Are p and q close together, in which case Fermat factorization finds them in a handful of iterations? Do you have two moduli from the same challenge, in which case gcd(n1, n2) is a shared prime? That last check is the one that broke thousands of real internet keys in the Lenstra study, and it costs one line of Python.

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 m without 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.

The bound comes straight from Wiener's 1990 paper in IEEE Transactions on Information Theory: the attack succeeds whenever d < (1/3) n^1/4. For a 1024-bit modulus that is any private exponent under about 256 bits, and the whole recovery runs in polynomial time because the continued-fraction expansion of a rational number has only O(log n) convergents to test. Boneh and Durfee later pushed the reachable bound to d < n^0.292 using lattice reduction, so if owiener returns None on a challenge that clearly wants a small-d attack, Boneh-Durfee in SageMath is the next step rather than a dead end.

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 encrypted blinding factor. That multiplicative homomorphism is a property of the raw primitive, not a bug in the server, which is why RFC 8017 wraps every real deployment in OAEP: a blinded ciphertext decrypts to a value whose padding does not verify, and the operation fails before it can leak anything.

The industrial-strength version of this idea is Bleichenbacher's 1998 adaptive chosen-ciphertext attack on PKCS #1 v1.5, still known as the "million message attack" because the original required on the order of 2²⁰ queries to a server that leaked only whether padding was valid. Twenty years later the ROBOT researchers found the same oracle still live on 27 of the Alexa top 100 domains. One bit of feedback per query is enough; a CTF oracle that hands you the full plaintext is a gift by comparison.

# 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

git clone https://github.com/RsaCtfTool/RsaCtfTool
cd RsaCtfTool && pip3 install -r requirements.txt
./RsaCtfTool.py -n N -e E --uncipher C --attack all
# or from a public key file:
./RsaCtfTool.py --publickey key.pub --uncipher ct

pip install factordb-python

pip install pycryptodome

sudo apt install sagemath

Verifying your plaintext

Once you recover a candidate plaintext m, how do you know it is correct? Raw RSA gives you a big integer. The common patterns in CTF challenges:

from Crypto.Util.number import long_to_bytes
 
m = pow(c, d, n)       # raw integer plaintext
flag_bytes = long_to_bytes(m)
print(flag_bytes)
 
# If the result starts with b'picoCTF{' you are done.
# If it starts with b'\x00' try stripping leading null bytes:
print(flag_bytes.lstrip(b'\x00'))
 
# If it looks like garbage, you may have the wrong parameters.
# Double-check: did the problem give e relative to phi(n) or lambda(n)?
# For challenges with multiple primes: phi = (p-1)*(q-1)*(r-1)*...

If the bytes start with recognizable structure (picoCTF{, a PDF header %PDF, a PNG magic \x89PNG) the decryption is correct. If you get random-looking bytes, the most likely causes are: wrong d (check your modular inverse), wrong n (confirm factorization), or the message was padded (OAEP or PKCS#1) before encryption.

Quick reference

Sources and further reading

Every bound and record above is from one of these. RSA is unusual among CTF topics in that the attacks are all published, named, and dated, so the primary literature is genuinely usable as a lookup table.

• RFC 8017: PKCS #1 v2.2 defines RSAES-OAEP, RSAES-PKCS1-v1_5, and RSASSA-PSS. Read it to see what every attack here assumes is absent.
• Key sizing: NIST SP 800-57 Part 1 Rev. 5 (security-strength table) and SP 800-131A Rev. 2 (what is disallowed and when).
• Small private exponent: Wiener (1990) for the n^0.25 bound and Boneh and Durfee (1999) for the lattice extension to n^0.292.
• Factoring reality: the RSA-250 and RSA-240 record paper (829 bits, about 2,700 core-years) and "Ron was wrong, Whit is right" (shared factors in live keys).
• Oracles and entropy: ROBOT (Bleichenbacher's attack, still live in 2017) and CVE-2008-0166 (Debian OpenSSL, 32,767 possible keys).