Mind your Ps and Qs

Description

Solution

1. Step 1Factor n
   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
   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.
   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()) EOFCopied!
   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

picoCTF{...}

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