EVEN RSA CAN BE BROKEN??? picoCTF 2025 Solution

Description

1. Step 1

   Capture the challenge output and confirm N is even

   Observation

   I noticed the challenge title explicitly states 'even RSA' and the description confirms one prime is 2, which suggested the very first step was verifying this by checking N % 2 before attempting any factoring.

   Each netcat connection emits a fresh set of RSA parameters. Grab N, e, and the ciphertext, then calculate N % 2 in Python. If the result is 0, N is even, so one prime factor is 2. That's the entire weakness: p = 2 and q = N // 2, and the rest of the attack is one line of math.

   bash

   nc verbal-sleep.picoctf.net <PORT_FROM_INSTANCE>

   Copied!

   python

   python3 -c 'N=...; print(N % 2)'  # expect 0

   Copied!

   Expected output

   0

   What didn't work first

   Tried: Try to factor N with a general-purpose tool like sympy.factorint() or yafu before checking parity

   General-purpose factoring tools work by trial division, Pollard rho, and quadratic sieve - all of which will eventually find p=2, but they add unnecessary complexity. Checking N % 2 first takes one operation and immediately reveals the trivial factor, making all other factoring approaches redundant for this challenge.

   Tried: Assume the service uses a fixed N and reuse the modulus printed in the challenge description without reconnecting

   Each netcat connection generates a fresh RSA keypair, so N, e, and c all change between sessions. Using a stale N with a freshly captured c will produce a nonsense plaintext or a ValueError when long_to_bytes fails to decode valid ASCII. Always copy all three values from a single connection.

   Learn more

   RSA relies on the computational difficulty of factoring the product of two large prime numbers. The modulus N = p × q is public, but recovering p and q individually from N alone should be computationally infeasible when both primes are large (typically 1024 bits or more each). The security breaks down completely when one of the primes is small or trivially guessable.

   In this challenge, one prime is literally 2 - the smallest prime. Checking divisibility by 2 is as simple as looking at the last digit or testing N % 2 == 0. This makes factoring N trivial: p = 2, q = N / 2. An even modulus is an immediate red flag in any RSA implementation because it means one prime was 2.

   Proper RSA key generation uses cryptographically secure random prime generation algorithms (like the Miller-Rabin primality test with high iteration counts) that always produce odd primes significantly larger than 3. Libraries like OpenSSL, Python's cryptography package, and pycryptodome handle this correctly. Rolling your own RSA key generation is strongly discouraged for exactly this reason.

2. Step 2

   Exploit the even modulus

   Observation

   I noticed that once p = 2 is confirmed, the totient formula phi(N) = (p-1)(q-1) collapses to q-1 because (2-1) = 1, which suggested the private key d could be derived immediately using a single modular inverse call.

   Because p = 2, Euler's totient is simply φ(N) = (2 − 1) × (q − 1) = q − 1. Invert e modulo φ(N) to obtain the private exponent d and run a modular exponentiation to recover the plaintext.

   bash

   d = pow(e, -1, q - 1)

   Copied!

   bash

   m = pow(ciphertext, d, N)

   Copied!

   What didn't work first

   Tried: Compute phi(N) as (p-1)*(q-1) using the full standard RSA formula with p=2 and q=N//2

   (2-1)*(q-1) does equal q-1, so the math is identical - but if a solver mistakenly writes phi = (N//2 - 1)*(N//2 - 1) by confusing p and q, or tries phi = N - 1 (Fermat's little theorem for prime N), the modular inverse will silently produce a wrong d and the decryption will return a large integer that long_to_bytes cannot decode as ASCII. Sticking to q-1 directly is both simpler and less error-prone.

   Tried: Use gmpy2.invert(e, phi) instead of Python's built-in pow(e, -1, phi) for the modular inverse

   gmpy2.invert raises ZeroDivisionError when the inverse does not exist, while pow(e, -1, phi) raises ValueError - both surface the same underlying problem (gcd(e, phi) != 1). However, gmpy2 is not in the standard library and requires a separate install; using the built-in pow avoids the dependency entirely. If gcd(e, q-1) happens to be greater than 1 on a given connection, reconnect to get a fresh keypair where e and phi are coprime.

   Learn more

   Euler's totient function φ(N) counts the integers from 1 to N that are coprime to N. For a product of two distinct primes, φ(N) = (p − 1)(q − 1). RSA private key generation requires computing φ(N) to find the modular inverse of the public exponent e. With p = 2, the totient simplifies to (2−1)(q−1) = q−1, a value that is directly computable from the public modulus.

   Python 3.8+ supports pow(e, -1, m) for modular inverse computation using the extended Euclidean algorithm. This is equivalent to finding d such that e × d ≡ 1 (mod φ(N)), which is the RSA private exponent. The modular inverse exists only when gcd(e, φ(N)) = 1; standard RSA public exponents like 65537 are chosen specifically because they are prime and likely coprime to φ(N).

   The decryption operation m = pow(c, d, N) performs modular exponentiation efficiently using Python's built-in three-argument pow, which uses the square-and-multiply algorithm. For large RSA numbers this is much faster than naive exponentiation, completing in milliseconds even for 2048-bit moduli.

   Even-RSA worked example (small numbers):
     Suppose N = 26 (= 2 * 13).  Even, so p = 2, q = 13.
     phi(N) = (2-1)*(13-1) = 1 * 12 = 12 = q - 1.
   
     e = 5  (gcd(5, 12) = 1)
     d = 5^(-1) mod 12 = 5  (since 5*5 = 25 = 2*12 + 1)
   
   Encrypt m = 7:
     c = 7^5 mod 26
       = 16807 mod 26
       16807 = 26 * 646 + 11
       c = 11
   
   Decrypt:
     m = 11^5 mod 26
       = 161051 mod 26
       161051 = 26 * 6194 + 7
       m = 7   ✓
   
   Why "even modulus" is the giveaway:
     In real RSA the modulus N is the product of two large odd primes,
     so N is always odd. The instant you see N % 2 == 0, you know
     one factor is 2. Compute q = N // 2, then phi = q - 1, then
     d = pow(e, -1, phi). Total work: one division, one subtraction,
     one extended-Euclidean inversion. Done.
   
   Even with N being thousands of bits, this is microseconds of
   computation. The challenge generator literally rolled "2" as one
   of the primes, which would never happen in any correct RSA
   implementation that uses prime-generation routines like
   sympy.randprime() or OpenSSL's BN_generate_prime_ex().

3. Step 3

   Convert the integer to bytes

   Observation

   I noticed that RSA decryption produces a raw integer rather than a string, and the flag format requires ASCII text, which suggested using pycryptodome's long_to_bytes to convert the integer back into readable output.

   Install pycryptodome if you don't already have it, then call long_to_bytes to turn the decrypted integer into ASCII. The result is the picoCTF flag.

   bash

   pip install pycryptodome

   Copied!

   bash

   from Crypto.Util.number import long_to_bytes

   Copied!

   python

   print(long_to_bytes(m).decode())

   Copied!

   Expected output

   picoCTF{tw0_1$_pr!m38177...}

   Learn more

   RSA operates on integers modulo N. To encrypt a message, the plaintext is first converted to an integer (using a padding scheme and byte-to-integer conversion), then encrypted. Decryption produces the integer back; recovering the string requires reversing that conversion.

   long_to_bytes from pycryptodome interprets the integer as a big-endian sequence of bytes, which is the standard representation. This is the inverse of int.from_bytes(msg, 'big') in plain Python. In real RSA usage, the plaintext integer would be much smaller than N thanks to OAEP padding, which adds randomness and structure before encryption. Textbook RSA (unpadded) like this challenge is deterministic: the same plaintext always encrypts to the same ciphertext, so an attacker who sees a ciphertext repeat instantly knows the plaintexts match. OAEP randomizes per encryption, so identical plaintexts produce different ciphertexts every time.

   Pycryptodome (the successor to PyCrypto) provides a comprehensive set of cryptographic primitives for Python, including RSA, AES, hashing, and key derivation. It is a commonly used library in CTF crypto challenges. Install it with pip install pycryptodome.

Flag

If the script throws a ValueError, double-check you copied the current N/e/c set. The values change with every connection.