rsa-pop-quiz picoCTF 2019 Solution

Description

1. Step 1Understand the quiz format
   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 = 95
   Decrypt c = 95:    m = 95^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
   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!
   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
   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.

Alternate Solution

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.