Mind your Ps and Qs picoCTF 2021 Solution

Description

1. Step 1Factor n

   Observation

   The description warns about small primes and hands over n directly. So the modulus is too short to be secure, and a public database like factordb.com will have it factored already.

   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 2Compute the private key and decrypt

   Observation

   With p and q recovered, the standard RSA private key formula applies directly: phi is (p-1)(q-1), and d is the modular inverse of e mod phi. Decrypt with pow(c, d, n) and convert the integer to bytes.

   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

   At this size sympy.factorint and similar trial-division or Pollard-rho implementations may finish, but they can stall for tens of seconds or minutes when the two primes are large without being tiny. factordb.com already stores the factorization, so a lookup is instant and skips the local compute entirely.

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

   Computing c**d as a raw exponentiation builds an astronomically large integer before the mod is ever applied, so Python exhausts memory or runs forever. Three-argument pow(c, d, n) reduces at each squaring step and returns the same answer 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.