john_pollard picoCTF 2019 Solution

Description

1. Step 1

   Extract n and e from the certificate

   Observation

   I noticed the challenge provides a PEM-encoded X.509 certificate, which meant the RSA public key parameters were embedded inside it and needed to be extracted before any factoring could begin.

   Parse the PEM certificate with openssl to reveal the RSA modulus (n) and public exponent (e) in human-readable form. The modulus n is only 53 bits - small enough to factor by trial division or using factordb.com. There is no ciphertext in this challenge; the flag is the prime factors themselves.

   bash

   openssl x509 -in cert -text -noout

   Copied!

   What didn't work first

   Tried: Running 'openssl rsa -in cert -text -noout' to read the key from the certificate

   The 'openssl rsa' command expects a raw private key file, not a certificate. It will error with 'unable to load Private Key'. The correct command is 'openssl x509' which parses the full X.509 certificate structure and prints the embedded public key modulus under the 'Subject Public Key Info' section.

   Tried: Using 'openssl x509 -in cert -pubkey -noout' and expecting to see n and e directly

   This flag extracts the raw public key in PEM format, not the parsed modulus and exponent values. You would then need a second command ('openssl rsa -pubin -text -noout') to decode that PEM blob. The single-pass '-text -noout' flag prints n and e in hex directly from the certificate, which is simpler for the next factoring step.

   Learn more

   RSA security depends on the difficulty of factoring large numbers. For a 2048-bit RSA key, factoring is computationally infeasible. But for small moduli (a few digits to a few hundred digits), factoring is easy using trial division, Pollard's rho algorithm, or pre-computed databases.

   factordb.com maintains a database of pre-factored numbers. For CTF challenges, the modulus is usually small enough to be in the database already.

2. Step 2

   Factor n to get p and q

   Observation

   I noticed from the openssl output that the modulus n was only 53 bits, which is far too small for secure RSA and suggested that trial division or a factoring database would yield p and q in milliseconds.

   Factor the modulus n to get the two prime factors p and q. Use Python, factordb, or an online factoring service.

   python

   python3 << 'EOF'
   # Small n can be factored by trial division
   import math
   
   n = <PASTE_N_HERE>
   # Trial division
   for p in range(2, int(math.isqrt(n)) + 1):
       if n % p == 0:
           q = n // p
           print(f"p = {p}")
           print(f"q = {q}")
           break
   EOF

   Copied!

   Expected output

   p = 67867967
   q = 73176001

   What didn't work first

   Tried: Pasting n into a general-purpose integer factoring site like WolframAlpha instead of factordb.com

   WolframAlpha can factor small integers but times out or refuses computation for numbers even a few dozen bits larger than this modulus. factordb.com is purpose-built for this task and pre-stores results, so it returns factors instantly regardless of size within CTF range. If WolframAlpha shows 'integer factorization not computed', switch to factordb.

   Tried: Running the trial division loop without first replacing PASTE_N_HERE with the actual modulus value from the openssl output

   The script uses a placeholder token that Python will fail to parse as an integer, raising a SyntaxError. You must copy the modulus hex string from the openssl output, convert it to a Python integer (using int('hex_digits', 16)), and substitute that value in place of PASTE_N_HERE before running the script.

   Learn more

   Why "John Pollard". The challenge name names John M. Pollard, who designed two of the classic factoring algorithms: Pollard's rho (1975) and Pollard's p-1 (1974). Trial division costs O(sqrt(n)); Pollard's rho costs about O(n^(1/4)); both crush small CTF moduli in milliseconds.

   Pollard's rho intuition. Iterate x_(i+1) = x_i^2 + 1 (mod n). By the birthday paradox, after about sqrt(p) steps two values collide modulo the smallest prime factor p, even though they have not collided modulo n. Floyd's tortoise-and-hare detects this collision: at every step compute g = gcd(|x - y|, n) with y moving twice as fast. When 1 < g < n, g is a non-trivial factor.

   def pollard_rho(n):
       x = y = 2
       g = 1
       while g == 1:
           x = (x*x + 1) % n
           y = (y*y + 1) % n
           y = (y*y + 1) % n     # tortoise vs hare
           g = math.gcd(abs(x - y), n)
       return g if g != n else None  # retry with new f if g == n

   Worked toy example. Factor n = 8051:

   step  x         y         gcd(|x-y|, 8051)
   1     5         26        1
   2     26        7474      1
   3     677       871       1
   4     7474      1244      83          <- factor!
   
   8051 = 83 * 97  (both prime)

   Pollard's p-1. Different family of attack: works when p - 1 is "B-smooth" (only small prime factors). Compute a = 2^(B!) mod n for a chosen bound B; if p - 1 | B! then Fermat's little theorem gives 2^(B!) ≡ 1 (mod p), so gcd(a - 1, n) = p. This is why prime-generation libraries pick safe primes where p = 2q + 1 with q also prime - that makes p - 1 have a giant prime factor and defeats p-1.

   Database lookup. For competition speed, paste n into factordb.com. The database stores millions of pre-factored RSA challenge numbers, including most CTF moduli that have appeared online. If FactorDB returns FF (Fully Factored), you have p, q instantly.

3. Step 3

   Submit p and q as the flag

   Observation

   I noticed the challenge description stated the flag is just the two prime factors, so once p and q were recovered from factoring n, no decryption step was needed and the flag format picoCTF{p,q} followed directly.

   Once you have factored n into p and q, the flag is simply picoCTF{p,q}. No decryption step is needed - the challenge tests only whether you can break the key itself, not use it.

   Learn more

   Why the flag is just p and q. This challenge tests one specific RSA weakness: using a modulus that is too small to be secure. The attacker goal is to factor n into p and q. Recovering those factors proves the key is broken - there is no separate encrypted message to recover.

   Flag format. Enter picoCTF{p,q} where p and q are the two prime factors in either order. For this certificate the factors are 73176001 and 67867967, so the flag is picoCTF{73176001,67867967}.

Flag

The flag is the two prime factors of the certificate modulus. No decryption step is required.