b00tl3gRSA2 picoCTF 2019 Solution

Description

1. Step 1Understand why encrypting with d is reversible using e

   Observation

   The server encrypts with d instead of e, and d is far larger than e. RSA is symmetric that way: because e*d is congruent to 1 mod phi(n), applying e to the ciphertext undoes an encryption done with d.

   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 2Connect and decrypt

   Observation

   The server hands over c, n, and e directly. Since pow(c, e, n) reverses the encryption, one modular exponentiation in Python is the only computation this needs.

   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.

   The server never gives you d, only c, n, and e. Factoring n to derive d is infeasible at these key sizes. But the server already encrypted with d, so applying the e you do have is enough 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.