PicoCTF 2025 Cryptography—EVEN RSA CAN BE BROKEN??? Writeup

Welcome back to another CTF writeup! In this post, I'll be walking you through a detailed, step-by-step breakdown of how I solved the challenge titled "EVEN RSA CAN BE BROKEN???" from picoCTF. This challenge dives into the world of cryptography, specifically exploiting weaknesses in RSA encryption. If you're curious about how supposedly secure encryption can be cracked under certain conditions, then keep reading—this one's going to be both educational and exciting!

Let's analyze the provided Python file

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()

This Python script demonstrates a basic RSA encryption scheme setup and usage. It starts by importing necessary modules, including bytes_to_long and inverse from PyCryptodome, and a custom function get_primes from a setup file to generate large primes. The gen_key function creates a 1024-bit RSA keypair by generating two large primes p and q, computing the modulus N = p * q, and calculating the private exponent d as the modular inverse of the public exponent e = 65537 with respect to Euler’s totient (p-1)*(q-1). The encrypt function takes a public key and a plaintext message, converts the message into a long integer, and performs modular exponentiation to return the ciphertext. In the main function, the flag is read from a file, stripped of whitespace, and encrypted using the generated keypair.

First, what is RSA?

RSA (Rivest-Shamir-Adleman) is one of the most widely used public-key cryptographic algorithms. It allows secure communication by enabling anyone to encrypt a message using a public key, while only the holder of the private key can decrypt it. The security of RSA is based on the mathematical difficulty of factoring large composite numbers.

How does RSA work?

1. Key Generation:

   • Choose two large prime numbers, p and q.

   • Compute the modulus N = p * q. This number N is part of both the public and private keys.

   • Calculate Euler’s totient function, φ(N) = (p-1)*(q-1).

   • Select a public exponent e (commonly 65537), which must be coprime with φ(N).

   • Compute the private exponent d, the modular inverse of e modulo φ(N), satisfying d * e ≡ 1 (mod φ(N)).

2. Encryption:

   • Convert the plaintext message into a number m such that 0 <= m < N.

   • Compute ciphertext c = m^e mod N.

3. Decryption:

   • Using the private key d, compute m = c^d mod N to recover the original message.

How can RSA be broken?

RSA’s security hinges on the fact that factoring N into its prime factors p and q is extremely hard for large enough primes. If an attacker can factor N, they can compute φ(N) and then find the private key d. Some common ways RSA can be broken include:

• Factoring the modulus N: Using algorithms like the General Number Field Sieve (GNFS), attackers try to find p and q. If the primes are too small or poorly chosen, factoring becomes feasible.

• Using small or weak primes: If p and q are too small, too close to each other, or share factors, the modulus can be factored easily.

• Low public exponent attacks: If e is very small (like 3) and the same message is sent to multiple recipients, certain attacks can recover the message.

• Poor padding or implementation flaws: RSA should be used with secure padding schemes (like OAEP). Without them, it’s vulnerable to chosen ciphertext attacks.

• Special cases like the "Even RSA" vulnerability: If the primes or key parameters have unusual properties (e.g., one prime is even or close to a multiple of something), special factorization tricks may apply.

In this challenge, we only have access to the public key components: the modulus N and the public exponent e. To break RSA and decrypt the message, we need to find the private key d, which depends on knowing the prime factors p and q of N since N = p * q. The problem is, factoring a large composite number N directly by checking divisibility for all possible factors is computationally infeasible when N is hundreds or thousands of bits long.

This is where Pollard’s Rho algorithm becomes extremely useful. Pollard’s Rho is a probabilistic integer factorization algorithm that works well when N has relatively small or medium-sized factors. It exploits the idea of detecting a non-trivial divisor by using a pseudo-random sequence and the concept of cycles in modular arithmetic.

Here’s the intuition behind why it works and why it’s suitable:

1. Cycle detection in modular sequences: Pollard’s Rho generates a sequence of values using a function like

   f(x) = x^2 + c mod N

   which behaves like a pseudo-random walk modulo N. Because modular arithmetic wraps around, eventually values in the sequence will repeat, forming a cycle.

2. Greatest common divisor (GCD) reveals factors: By calculating the greatest common divisor

   gcd(|x_i - x_j|, N)

   of the difference between two sequence values and N, Pollard’s Rho can reveal a factor of N if the gcd is greater than 1 but less than N.

3. Efficiency for moderate sized factors: Unlike trial division, which has a time complexity proportional to the square root of N, Pollard’s Rho runs much faster in practice — often in roughly the fourth root of N time — which is a significant improvement for numbers that aren’t astronomically large or structured in a way that makes Pollard’s Rho effective.

4. Probabilistic nature: Pollard’s Rho does not guarantee immediate success, but by repeating with different parameters or starting points, it usually finds a factor quickly, especially if one of the primes p or q is not too large or has specific properties.

Because the challenge likely uses primes that are not extremely large, Pollard’s Rho is an excellent fit. It balances efficiency and simplicity, making it a practical choice for factoring the RSA modulus N in this puzzle and allowing us to retrieve p and q, and ultimately, break the encryption.

Here's the script I've made to emphasize that and get the flag

import gmpy2
from gmpy2 import mpz, next_prime, isqrt, invert
import time

# Given RSA values
N = mpz(20168896484145221390047841611288807976705509197322764938228630702600225823584813329889518046583400590938438122656026715440660312769513954948311486149976602)
e = mpz(65537)
ciphertext = mpz(8887028313129773620535348275129893066919436155126858542627496914102643784217816380854009879986298507548835625233973609335407805389393105692390652590069491)

# ===== Step 1: Factor N (using Pollard's Rho for fast factorization) =====
def pollards_rho(n):
    if n % 2 == 0:
        return 2
    if n % 3 == 0:
        return 3
    if n % 5 == 0:
        return 5

    while True:
        c = gmpy2.random_state(int(time.time())).random_range(1, n-1)
        f = lambda x: (pow(x, 2, n) + c) % n
        x, y, d = 2, 2, 1
        while d == 1:
            x = f(x)
            y = f(f(y))
            d = gmpy2.gcd(abs(x - y), n)
        if d != n:
            return d

# Factor N into p and q
start_time = time.time()
p = pollards_rho(N)
q = N // p
print(f"p = {p}")
print(f"q = {q}")

# ===== Step 2: Compute private key d = e⁻¹ mod φ(N) =====
phi = (p - 1) * (q - 1)
d = invert(e, phi)

# ===== Step 3: Decrypt ciphertext =====
m = pow(ciphertext, d, N)

# ===== Step 4: Convert to bytes (flag) =====
flag_bytes = m.to_bytes((m.bit_length() + 7) // 8, 'big')
flag = flag_bytes.decode('utf-8', errors='replace')

print("\nDecrypted flag:", flag)

Run and we should get the p, q, and the flag!

FLAG