Mind your Ps and Qs picoCTF 2021 Solution

Description

1. Step 1

   Factor n

   Observation

   I noticed the challenge description explicitly warned about 'small primes' and provided n directly, which suggested the modulus was too short to be secure and could be factored instantly via a public database like factordb.com.

   Because n is small (only a few hundred bits), it can be factored instantly using factordb.com. Paste the value of n into the search box to retrieve the two prime factors p and q.

   Learn more

   RSA's security relies entirely on the integer factorization problem: given a large number n = p * q, it should be computationally infeasible to find p and q. For modern RSA, n is at least 2048 bits (~617 decimal digits), which makes factoring effectively impossible with current technology.

   However, when n is small - say, a few hundred bits or fewer - factoring is trivial. Tools like factordb.com maintain a database of pre-factored numbers and can factor small integers instantly. For larger numbers they use algorithms like the Quadratic Sieve or General Number Field Sieve (GNFS). The title "Mind Your Ps and Qs" refers to the prime factors p and q - small primes undermine the entire system.

   Historical context: In 2012, researchers found that millions of real-world RSA public keys shared prime factors because of weak random number generators used during key generation. By computing GCDs between pairs of public keys, they factored a significant percentage of real keys - a real-world demonstration of exactly this vulnerability.

2. Step 2

   Compute the private key and decrypt

   Observation

   I noticed that once p and q were recovered from factordb, the standard RSA private key formula (phi = (p-1)*(q-1), d = modular_inverse(e, phi)) could be applied directly, so decrypting with pow(c, d, n) and converting the integer to bytes would yield the flag.

   With p and q known, compute phi = (p-1)*(q-1), then the private exponent d = modular_inverse(e, phi). Raise c to the power d mod n to recover the plaintext integer m, then convert it to bytes.

   python

   python3 << 'EOF'
   from Crypto.Util.number import inverse, long_to_bytes
   
   # Fill in values from the challenge file and factordb
   c = <c>
   n = <n>
   e = <e>
   p = <p>  # from factordb.com
   q = <q>  # from factordb.com
   
   phi = (p - 1) * (q - 1)
   d = inverse(e, phi)
   m = pow(c, d, n)
   print(long_to_bytes(m).decode())
   EOF

   Copied!

   Expected output

   picoCTF{sma11_N_n0_g0od_...}

   What didn't work first

   Tried: Running sympy.factorint() or a local factoring script on n instead of using factordb.com

   For a number this size sympy.factorint() and similar trial-division or Pollard-rho implementations may still complete, but they can stall for tens of seconds to minutes on numbers with two large but not tiny primes. factordb.com has already stored the factorization, so a web lookup is instant and sidesteps any local compute bottleneck entirely.

   Tried: Passing c**d to long_to_bytes without the modular form pow(c, d, n)

   Computing c**d as a raw exponentiation produces an astronomically large integer before the mod is applied, causing Python to exhaust memory or run indefinitely. The three-argument pow(c, d, n) applies the modular reduction at each squaring step and returns the same result in milliseconds.

   Learn more

   The RSA decryption process follows directly from the mathematics. Euler's totient function φ(n) = (p-1)*(q-1) counts how many integers less than n are coprime with it. The private exponent d is defined as the modular inverse of e modulo φ(n), meaning e*d ≡ 1 (mod φ(n)). This relationship is what makes decryption the inverse of encryption.

   Modular exponentiation (pow(c, d, n)) uses Python's built-in three-argument form, which is highly efficient - it applies the square-and-multiply algorithm internally. Even with a 2048-bit exponent, this completes in milliseconds. Without the three-argument form (computing c**d and then taking mod), the intermediate number would have millions of digits and be completely impractical.

   The long_to_bytes() function from pycryptodome converts the recovered plaintext integer back to a byte string. RSA operates on integers, so text messages are first converted to integers (using big-endian byte encoding) before encryption. long_to_bytes reverses this step to give the human-readable flag.

Flag

When n is small enough to factor, RSA provides zero security - always use at least 2048-bit keys.