rsa-pop-quiz picoCTF 2019 Solution

Description

1. Step 1Understand the quiz format

   Observation

   The name and description both say RSA pop quiz, so the server will run multiple rounds of RSA parameter computations. Knowing the five core identities (n, phi, d, encryption, decryption) up front is what makes opening the connection worthwhile.

   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 2Write a pwntools solver

   Observation

   The quiz is timed and runs many rounds. Solving each question by hand is far too slow, so automate the interaction with pwntools and dispatch to the right RSA formula per question type.

   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 has to be taken with respect to phi(n) = (p-1)*(q-1), not n. pow(e, -1, n) returns a different number entirely, one that does not satisfy the e*d relation mod phi, so decryption produces garbage. Use 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, -17 instead of 103 for phi=120, and the server rejects a negative integer. Reduce it: d = d % phi brings any negative result back 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 3Answer all questions and get the flag

   Observation

   Interactive quiz servers on picoCTF hand over the flag only after every round is answered correctly. So once the solver handles all the question types, the flag arrives 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.