rsa-pop-quiz picoCTF 2019 Solution

Description

1. Step 1

   Understand the quiz format

   Observation

   I noticed the challenge name and description both say 'RSA pop quiz,' which suggested the server would present multiple rounds of RSA parameter computations and that knowing the five core RSA identities (n, phi, d, encryption, decryption) in advance was essential before attempting any connection.

   The server asks a series of RSA computation questions. Each question gives you some parameters and asks you to compute a missing value. Questions may include: compute n from p and q, compute d from p, q, e, decrypt c given all key parameters.

   Learn more

   The five RSA identities you must internalize.

   • n = p * q - the public modulus, product of two distinct large primes.
   • φ(n) = (p-1)*(q-1) - Euler's totient, counts integers in [1, n-1] coprime to n.
   • d = e^(-1) mod φ(n) - private exponent, exists because gcd(e, φ(n)) = 1; computed by extended Euclidean.
   • c = m^e mod n - encryption.
   • m = c^d mod n - decryption.

   Why decryption inverts encryption. By construction e*d = 1 + k*φ(n) for some integer k. Then c^d = m^(e*d) = m^(1 + k*φ(n)) = m * (m^φ(n))^k ≡ m * 1^k ≡ m (mod n) by Euler's theorem. The 1^k simplification is what makes it work - it is the entire reason RSA is a scheme rather than just a one-way function.

   Worked example with tiny numbers. Take p = 11, q = 13:

   n = 143,  φ = 10*12 = 120,  pick e = 7
   extgcd(7, 120):  1 = 120 - 17*7  =>  d = -17 mod 120 = 103
   
   Encrypt m = 42:    c = 42^7 mod 143 = 81
   Decrypt c = 81:    m = 81^103 mod 143 = 42   ✓

   Variant: Carmichael instead of Euler. Some implementations use λ(n) = lcm(p-1, q-1) instead of φ(n). Both work for choosing d, and λ gives a slightly smaller (sometimes faster) d. The quiz may accept either, but always test e*d ≡ 1 (mod φ(n)) first - that is the canonical relation.

2. Step 2

   Write a pwntools solver

   Observation

   I noticed the quiz has a time limit and presents many rounds of computation, which suggested that manually solving each question by hand would be too slow and that automating the interaction with pwntools and dispatching to the correct RSA formula per question type was the only practical approach.

   Automate the quiz with pwntools. Read each question, parse the parameters, compute the answer using sympy or gmpy2, and send it back.

   python

   python3 << 'EOF'
   from pwn import *
   from sympy import mod_inverse, isprime
   import re
   
   r = remote('<HOST>', <PORT_FROM_INSTANCE>)
   
   def solve_rsa(params):
       p = params.get('p')
       q = params.get('q')
       e = params.get('e')
       c = params.get('c')
       n = params.get('n')
   
       if p and q and not n:
           return ('n', p * q)
       if p and q and e and not c:
           phi = (p-1)*(q-1)
           d = mod_inverse(e, phi)
           return ('d', d)
       if n and e and c and p and q:
           phi = (p-1)*(q-1)
           d = mod_inverse(e, phi)
           m = pow(c, d, n)
           return ('plaintext', m)
       return None
   
   # Main loop: read question, parse params, compute answer, send
   r.interactive()
   EOF

   Copied!

   What didn't work first

   Tried: Computing d as pow(e, -1, n) instead of pow(e, -1, phi) and sending that as the private exponent.

   The modular inverse must be taken with respect to phi(n) = (p-1)*(q-1), not n itself. pow(e, -1, n) gives a completely different number that does not satisfy e*d ≡ 1 (mod phi), so decryption produces garbage. The correct call is pow(e, -1, (p-1)*(q-1)) or sympy.mod_inverse(e, phi).

   Tried: Using gmpy2.invert(e, phi) but forgetting to import gmpy2 and falling back to a hand-rolled extended-gcd that returns a negative value without reducing mod phi.

   A naive extended-gcd returns a Bezout coefficient that can be negative (e.g., -17 instead of 103 for phi=120). Sending a negative integer to the server causes it to reject the answer. The fix is to reduce: d = d % phi, which brings any negative result into the canonical [0, phi-1] range.

   Learn more

   Extended Euclidean walked by hand. To find d with e*d ≡ 1 (mod φ), run forward Euclid then back-substitute. Example with e = 7, φ = 40:

   Forward:
      40 = 5*7 + 5
       7 = 1*5 + 2
       5 = 2*2 + 1
       2 = 2*1 + 0   -> gcd = 1
   
   Back-substitute:
      1 = 5 - 2*2
        = 5 - 2*(7 - 5)
        = 3*5 - 2*7
        = 3*(40 - 5*7) - 2*7
        = 3*40 - 17*7
   
      So  -17*7 ≡ 1 (mod 40)
          d = -17 mod 40 = 23
   
   Verify: 7*23 = 161 = 4*40 + 1   ✓

   That is exactly what pow(e, -1, φ) (Python 3.8+) and sympy.mod_inverse(e, φ) compute internally. Both run in O(log min(e, φ)).

   Square-and-multiply for pow(c, d, n). Walk the bits of d from MSB to LSB:

   def modpow(base, exp, mod):
       result = 1
       base = base % mod
       while exp > 0:
           if exp & 1:                # if low bit of exp is 1
               result = (result * base) % mod
           base = (base * base) % mod # square
           exp >>= 1
       return result

   For 2048-bit d that is at most 4096 multiplies (one square plus optionally one multiply per bit), each on numbers reduced to under n. Without this, c**d would be a literal number with 10^600+ digits and could never fit in any computer's memory.

3. Step 3

   Answer all questions and get the flag

   Observation

   I noticed that interactive quiz servers on picoCTF typically reveal the flag only after all rounds are completed successfully, which suggested that once the automated solver handled every question type correctly the server would output the flag as the final response.

   After correctly answering all RSA questions, the server prints the flag.

   Learn more

   This challenge tests understanding of RSA's mathematical structure. Real-world RSA implementations also deal with padding (OAEP, PKCS#1), key serialization (PEM/DER), and constant-time implementation to prevent timing attacks.

Flag

Automate RSA computations (n=p*q, d=modinv(e,phi), m=pow(c,d,n)) to answer all quiz questions and receive the flag.