b00tl3gRSA2 picoCTF 2019 Solution

Description

1. Step 1Understand why encrypting with d is reversible using e
   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
   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!
   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()).

Alternate Solution

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.