EVEN RSA CAN BE BROKEN???

Description

Solution

1. Step 1Capture the challenge output
   Each netcat connection emits a fresh set of RSA parameters. Grab N, e, and the ciphertext before disconnecting. N always divides evenly by 2, so you only need one large odd factor q = N / 2.
   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.

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

   Copied!

   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.

3. Step 3Convert the integer to bytes
   Use `Crypto.Util.number.long_to_bytes` (from pycryptodome) to transform the decrypted integer into ASCII, and the result is the picoCTF flag.

   from Crypto.Util.number import long_to_bytes

   Copied!

   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. Unpadded RSA (textbook RSA) like this challenge is deterministic and vulnerable to several attacks beyond just weak key generation.

   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

picoCTF{tw0_1$_pr!m38177...}

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