EVEN RSA CAN BE BROKEN??? picoCTF 2025 Solution

Description

1. Step 1Capture the challenge output and confirm N is even
   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!
   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
   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!
   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
   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!
   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.

Alternate Solution

Flag

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