RSA Basics

The textbook

RSA encrypts a message m with public key (n, e):

c = m^e mod n

Decryption uses the private key d (the modular inverse of e mod (p-1)(q-1)):

m = c^d mod n

Security rests on the hardness of factoring n = p * q when p and q are large random primes.

Beginner CTF mistakes

1. Small n — just factor it

If n is a few hundred bits, paste it into FactorDB or run factor n on Linux. Once you have p and q:

from sympy import mod_inverse
p, q = <factors>
n, e, c = <given values>
phi = (p - 1) * (q - 1)
d = mod_inverse(e, phi)
m = pow(c, d, n)
print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))

2. Small e with no padding

When e = 3 and m is small, m^3 < n, so c is just m^3 in the integers — take the integer cube root:

import gmpy2
m, exact = gmpy2.iroot(c, e)
print(m.to_bytes(...))

3. Common factor across two public keys

Two different n values sharing a prime p leak p instantly:

import math
p = math.gcd(n1, n2)   # p > 1 → you've factored both

This happens when a weak random number generator reuses primes.

Using RsaCtfTool

RsaCtfTool automates most beginner RSA attacks:

# Try every known attack on a given public key + ciphertext
python3 RsaCtfTool.py --publickey pub.pem --uncipherfile ct.bin

# Pass n and e directly
python3 RsaCtfTool.py -n <n> -e <e> --uncipher <c>

It hits FactorDB, Wiener’s attack, small-e, common-factor, and dozens more.

Mental model

CTF RSA challenges always exploit a parameter choice mistake. Ask: is n factorable? Is e too small? Are multiple ciphertexts sharing n or e? The math is correct; the implementation is broken.