Breaking Weak RSA Keys in Crypto CTF Challenges

Introduction

RSA is one of the most common public-key cryptosystems, and it's frequently featured in CTF challenges. This writeup covers various techniques to break weak RSA implementations.

RSA Basics

RSA relies on three key components:

Encryption: c = m^e mod n

Decryption: m = c^d mod n

• ▹n - modulus (product of two large primes p and q)
• ▹e - public exponent
• ▹d - private exponent (kept secret)

Attack 1: Small Exponent (e=3)

When e is small (commonly 3), and the message is small, we can attack directly. Challenge: Given n, e=3, and c

import gmpy2

# If m^3 < n, then c = m^3 (no modular reduction)
m = gmpy2.iroot(c, 3)[0]
print(bytes.fromhex(hex(m)[2:]))

Attack 2: Fermat's Factorization

When p and q are close together, Fermat's method can factor n quickly.

import gmpy2

def fermat_factor(n):
    a = gmpy2.isqrt(n) + 1
    b2 = a*a - n
    
    while not gmpy2.is_square(b2):
        a += 1
        b2 = a*a - n
    
    b = gmpy2.isqrt(b2)
    p = a - b
    q = a + b
    return int(p), int(q)

# Once we have p and q:
phi = (p-1) * (q-1)
d = pow(e, -1, phi)
m = pow(c, d, n)

Real CTF Example

Challenge: CryptoCTF 2023 - Weak RSA

n = 98765432109876543210987654321098765432109876543210
e = 3
c = 12345678901234567890123456789012345678901234567890

Solution

import gmpy2

n = 98765432109876543210987654321098765432109876543210
e = 3
c = 12345678901234567890123456789012345678901234567890

# Try cube root attack
m, exact = gmpy2.iroot(c, 3)

if exact:
    flag = bytes.fromhex(hex(m)[2:])
    print(f"Flag: {flag.decode()}")

Defense Recommendations

• ▹Use large random primes with sufficient bit length (2048+ bits)
• ▹Choose e > 65537
• ▹Ensure p and q are sufficiently far apart
• ▹Implement proper padding (OAEP)
• ▹Never reuse the same modulus with different exponents