EVEN RSA CAN BE BROKEN??? picoCTF 2025 Solution

Description

1. Step 1Capture the challenge output and confirm N is even

   Observation

   The title says even RSA and the description confirms one prime is 2. Check N modulo 2 before reaching for any factoring tool.

   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 run trial division, Pollard rho, and the quadratic sieve, and all of them do eventually find the factor 2. But one modulo operation finds it first, which makes the rest redundant.

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

   Every connection generates a fresh keypair, so N, e, and c all change. Mixing a stale N with a new c gives nonsense, or a decode error when the bytes are not ASCII. Take all three from one session.

   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 2Exploit the even modulus

   Observation

   With p confirmed as 2, the totient collapses: (p-1)(q-1) becomes just q-1. One modular inverse gives the private key.

   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

   Writing it as (2-1)*(q-1) is mathematically identical. The risk is nearby mistakes: squaring the wrong term after confusing p and q, or reaching for N-1 as if N were prime. Either produces a wrong d silently, and the decryption returns an integer that will not decode as ASCII. Write q-1 directly.

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

   gmpy2.invert raises one error and the built-in pow raises another, but both mean the same thing: e and phi are not coprime. gmpy2 also needs a separate install, so the built-in is simpler. If a connection hands you a non-coprime pair, reconnect for a fresh keypair.

   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 3Convert the integer to bytes

   Observation

   RSA decryption yields an integer, not text. long_to_bytes from pycryptodome converts it back to readable ASCII.

   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.