Breaking Weak RSA: A Classic CTF Walkthrough

If you spend any time grinding Capture The Flag (CTF) challenges like picoCTF, you will inevitably cross paths with RSA encryption. It’s the backbone of modern secure communication, but when implemented poorly, it leaves the front door wide open.

In this post, we’re going to walk through a classic crypto challenge: breaking RSA when the public key is just too small.

The Setup: Analyzing the Source

Usually, a challenge like this starts with a connection command (like nc to a server) and a provided Python script. Let’s look at the encryption script we’re up against:

from sys import exit
from Crypto.Util.number import bytes_to_long, inverse
from setup import get_primes

e = 65537

def gen_key(k):
    """
    Generates RSA key with k bits
    """
    p,q = get_primes(k//2)
    N = p*q
    d = inverse(e, (p-1)*(q-1))
    return ((N,e), d)

def encrypt(pubkey, m):
    N,e = pubkey
    return pow(bytes_to_long(m.encode('utf-8')), e, N)

def main(flag):
    pubkey, _privkey = gen_key(1024)
    encrypted = encrypt(pubkey, flag)
    return (pubkey[0], encrypted)

if __name__ == "__main__":
    flag = open('flag.txt', 'r').read()
    flag = flag.strip()
    N, cypher  = main(flag)
    print("N:", N)
    print("e:", e)
    print("cyphertext:", cypher)
    exit()

When we connect to the server, the script outputs three crucial pieces of information:

1. N: The modulus (part of the public key).
2. e: The public exponent (usually 65537).
3. cyphertext: Our encrypted flag.

The Vulnerability: Why Size Matters

To decrypt an RSA message, you need the private key, . To calculate , you need to know , which is derived from the prime factors of ( and ).

In modern RSA implementations, is exponentially large (e.g., 2048 or 4096 bits). Finding the prime factors of a number that large is practically impossible with current computing power.

However, in this specific challenge, the value of is relatively small. Because is small and simple, we don't need a supercomputer to find and . We can just ask the internet.

The Exploit: Step-by-Step

Step 1: Factoring N

Once you grab the value of from your terminal, head over to a database like FactorDB. Input your , and if it's small enough or has been factored before, the site will instantly hand you the prime factors, and .

Step 2: The Decryption Script

Now that we have and , we have everything we need to calculate our private key and decrypt the ciphertext.

In RSA, the private key is the modular inverse of modulo . Mathematically, this looks like:

Instead of doing the math by hand, we can write a quick Python script using the pycryptodome library to handle the heavy lifting:

from Crypto.Util.number import inverse, long_to_bytes

# Values retrieved from the netcat connection
N = int(input("N : "))
e = int(input("e : "))
c = int(input("cyperText : "))

# Paste the prime factors retrieved from FactorDB
p = int(input("p : "))
q = int(input("q : "))

# 1. Calculate phi
phi = (p - 1) * (q - 1)

# 2. Calculate private key d (The modular inverse)
d = inverse(e, phi)

# 3. Decrypt the ciphertext using C^d mod N
m_long = pow(c, d, N)

# 4. Convert the long integer back to readable bytes (the flag)
decrypted_bytes = long_to_bytes(m_long)

print(f"Raw Bytes: {decrypted_bytes}")

Step 3: Profit

Run the script, plug in the values from your terminal and FactorDB, and the script will calculate , find , decrypt the long integer, and convert it back into ASCII text.

Hureeeeee you got the flag!

Final Thoughts

This challenge is a great reminder of why cryptographic parameters must be strictly enforced. The algorithm itself isn't broken here; the implementation is. Without adequately large prime numbers, even the most mathematically sound encryption schemes fall apart in seconds.