b00tl3gRSA2 picoCTF 2019 Solution

Description

1. Step 1

   Understand why encrypting with d is reversible using e

   Observation

   I noticed the challenge description stated the server encrypted with d instead of e and that d is much larger than e, which suggested the RSA symmetry property (e*d ≡ 1 mod phi(n)) means applying e to the ciphertext would reverse the private-key encryption.

   The challenge says 'd is a lot bigger than e' and the server used d to encrypt instead of e. Because RSA keys are mathematical inverses of each other, decryption with d can be undone by applying e: m = pow(c, e, n). This is the same operation as normal RSA encryption but in reverse.

   Learn more

   Standard RSA: encrypt with public key e as c = pow(m, e, n), decrypt with private key d as m = pow(c, d, n). The relationship e * d ≡ 1 (mod phi(n)) means these operations cancel each other out.

   When the sender mistakenly uses d to encrypt: c = pow(m, d, n), the recipient can recover m by applying e: m = pow(c, e, n). This works because pow(pow(m, d, n), e, n) = m by Euler's theorem.

   The classic reason e is chosen small (3, 17, 65537) is encryption speed. The private exponent d must be large for security. Using d to encrypt defeats both purposes and exposes the message to anyone with the public key.

2. Step 2

   Connect and decrypt

   Observation

   I noticed the server provides c, n, and e directly, and since the conceptual step confirmed pow(c, e, n) reverses the encryption, connecting to retrieve those values and running that single modular exponentiation in Python was the only computation needed to recover the flag.

   Connect to the server to get c, n, and e. Then compute pow(c, e, n) in Python. Convert the integer result from hex to ASCII to read the flag.

   python

   python3 << 'EOF'
   c = <PASTE_C_HERE>
   n = <PASTE_N_HERE>
   e = <PASTE_E_HERE>  # likely 65537
   
   m = pow(c, e, n)
   flag = bytes.fromhex(hex(m)[2:]).decode()
   print(flag)
   EOF

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Try decrypting with pow(c, d, n) using a guessed or brute-forced private exponent d.

   d is not given by the server - only c, n, and e are provided. Factoring n to derive d is computationally infeasible for the key sizes used here. The trick is that the server already encrypted with d, so applying e (the public exponent you do have) is all that is needed to reverse it.

   Tried: Convert the integer m to ASCII by calling m.to_bytes(...).decode() without handling hex padding.

   hex(m)[2:] can produce an odd-length string when the leading nibble is zero, causing bytes.fromhex() to raise a ValueError. The fix is to left-pad to an even length with '0' + h before decoding, or use m.to_bytes((m.bit_length() + 7) // 8, 'big').decode().

   Learn more

   Python's built-in pow(base, exp, mod) computes modular exponentiation efficiently using square-and-multiply, so this works even for multi-hundred-digit n.

   If hex(m) has an odd number of characters, prepend a zero before decoding: h = hex(m)[2:]; h = h if len(h) % 2 == 0 else '0' + h; print(bytes.fromhex(h).decode()).

Flag

When d was used to encrypt instead of e, decrypting is just pow(c, e, n) - the public exponent reverses the private-key encryption.