RSA Attacks for CTFs

intermediate45 minWriteup

Attacking weak RSA implementations

Learning Objectives

  • Understand RSA basics
  • Attack small exponents
  • Factor weak keys
  • Use RsaCtfTool

RSA is the most common public-key cryptosystem in CTFs. Understanding how it works and its common weaknesses is essential for crypto challenges. You don't need to be a mathematician - just know the attacks!

RSA security relies on the difficulty of factoring large numbers. When implemented correctly, it's secure. CTF RSA challenges always have implementation flaws to exploit!

How RSA Works

1606070;"># RSA Key Generation:
2606070;"># 1. Choose two large primes: p and q
3606070;"># 2. Calculate n = p × q
4606070;"># 3. Calculate φ(n) = (p-1)(q-1)
5606070;"># 4. Choose e (commonly 65537)
6606070;"># 5. Calculate d such that: e × d ≡ 1 (mod φ(n))
7 
8606070;"># Public Key: (n, e)
9606070;"># Private Key: (n, d)
10 
11606070;"># Encryption: c = m^e mod n
12606070;"># Decryption: m = c^d mod n
13 
14606070;"># Common values you'll see in CTFs:
15606070;"># n - modulus (large number, product of p and q)
16606070;"># e - public exponent (65537, 3, or other small values)
17606070;"># c - ciphertext (encrypted message)
18606070;"># p, q - prime factors of n
19606070;"># d - private exponent

Key Insight

If you can factor n into p and q, you can compute d and decrypt anything! All RSA attacks ultimately try to factor n or exploit implementation mistakes.

Attack 1: Known Factorization

bash
1606070;"># If n is already factored, game over!
2 
3606070;"># Check factordb.com first
4606070;"># Paste n, see if p and q are known
5 
6606070;"># Python script once you have p and q:
7from Crypto.Util.number import inverse, long_to_bytes
8 
9n = 606070;"># given
10e = 65537  606070;"># usually given or default
11c = 606070;"># given ciphertext
12p = 606070;"># from factordb
13q = 606070;"># from factordb
14 
15606070;"># Calculate private key
16phi = (p - 1) * (q - 1)
17d = inverse(e, phi)
18 
19606070;"># Decrypt
20m = pow(c, d, n)
21print(long_to_bytes(m))

Attack 2: Small n

python
1606070;"># If n is small enough to factor directly
2 
3606070;"># Using factordb Python library
4from factordb.factordb import FactorDB
5 
6n = 123456789...
7f = FactorDB(n)
8f.connect()
9factors = f.get_factor_list()
10print(factors)  606070;"># [p, q]
11 
12606070;"># Or use SageMath
13606070;"># sage: factor(n)
14 
15606070;"># Or use yafu (command line)
16606070;"># yafu "factor(n)"

Attack 3: Small e (e=3)

python
1606070;"># When e is very small (like 3) and message is short
2606070;"># c = m^3 mod n, but if m^3 < n, then c = m^3 exactly!
3 
4606070;"># Just take the cube root:
5import gmpy2
6from Crypto.Util.number import long_to_bytes
7 
8c = 606070;"># ciphertext
9e = 3
10 
11606070;"># If m^e < n:
12m = gmpy2.iroot(c, e)[0]
13print(long_to_bytes(m))
14 
15606070;"># If m^e slightly > n (requires trying multiples of n):
16for k in range(10000):
17    m, is_exact = gmpy2.iroot(c + k * n, e)
18    if is_exact:
19        print(f606070;">#a5d6ff;">"k={k}: {long_to_bytes(m)}")
20        break
Håstad's broadcast attack: If the same message is encrypted to multiple recipients with e=3 and different n values, use Chinese Remainder Theorem to recover m.

Attack 4: Common Factors

python
1606070;"># If two public keys share a prime factor
2606070;"># gcd(n1, n2) = shared_p
3 
4import math
5 
6n1 = 606070;"># first modulus
7n2 = 606070;"># second modulus
8 
9p = math.gcd(n1, n2)
10if p > 1 and p < n1:
11    print(f606070;">#a5d6ff;">"Found common factor: {p}")
12    q1 = n1 606070;">// p
13    q2 = n2 606070;">// p
14    606070;"># Now decrypt both messages!

Attack 5: Wiener's Attack (Small d)

python
1606070;"># When d is small (less than n^0.25), continued fractions can find it
2 
3606070;"># Using owiener library
4606070;"># pip install owiener
5import owiener
6 
7e = 606070;"># public exponent (very large)
8n = 606070;"># modulus
9 
10d = owiener.attack(e, n)
11if d:
12    print(f606070;">#a5d6ff;">"Found d: {d}")
13    606070;"># Decrypt as normal
14 
15606070;"># RsaCtfTool also implements this automatically

RsaCtfTool

bash
1606070;"># The ultimate RSA attack tool
2606070;"># https://github.com/RsaCtfTool/RsaCtfTool
3 
4git clone https:606070;">//github.com/RsaCtfTool/RsaCtfTool
5cd RsaCtfTool
6pip install -r requirements.txt
7 
8606070;"># Attack with public key file
9python3 RsaCtfTool.py --publickey key.pub --uncipherfile flag.enc
10 
11606070;"># Attack with values
12python3 RsaCtfTool.py -n 12345... -e 65537 --uncipher 98765...
13 
14606070;"># Try all attacks
15python3 RsaCtfTool.py --publickey key.pub --attack all
16 
17606070;"># Attacks included:
18606070;"># - Factordb lookup
19606070;"># - Small e attack
20606070;"># - Wiener's attack
21606070;"># - Fermat factorization
22606070;"># - Pollard p-1
23606070;"># - And many more!
RsaCtfTool is your first stop for RSA challenges. It automatically tries dozens of attacks. Only go manual if it fails!

Standard Decryption Script

python
1606070;">#!/usr/bin/env python3
2606070;"># Standard RSA decryption when you have all values
3 
4from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long
5import gmpy2
6 
7606070;"># Known values (fill these in)
8n = None  606070;"># modulus
9e = 65537  606070;"># public exponent
10c = None  606070;"># ciphertext
11p = None  606070;"># first prime (if known)
12q = None  606070;"># second prime (if known)
13d = None  606070;"># private exponent (if known)
14 
15606070;"># If you have p and q but not d:
16if p and q and not d:
17    phi = (p - 1) * (q - 1)
18    d = inverse(e, phi)
19 
20606070;"># Decrypt
21if d:
22    m = pow(c, d, n)
23    plaintext = long_to_bytes(m)
24    print(f606070;">#a5d6ff;">"Decrypted: {plaintext}")
25else:
26    print(606070;">#a5d6ff;">"Need d or (p,q) to decrypt!")
27 
28606070;"># Small e attack (if e=3)
29if e == 3:
30    m, exact = gmpy2.iroot(c, 3)
31    if exact:
32        print(f606070;">#a5d6ff;">"Small e attack: {long_to_bytes(m)}")

Knowledge Check

Quick Quiz
Question 1 of 2

What's the first thing to try with an RSA challenge?

Key Takeaways

  • Always check factordb.com first - it's instant if n is factored
  • Small e (especially e=3) enables cube root attack
  • RsaCtfTool automates dozens of RSA attacks
  • Common factors between two public keys = easy win
  • Know the standard decrypt script by heart
  • RSA math is simple: c=m^e mod n, m=c^d mod n