john_pollard picoCTF 2019 Solution

Description

1. Step 1Extract n and e from the certificate

   Observation

   The challenge provides a PEM-encoded X.509 certificate, so the RSA public key parameters are embedded inside it. They have to come out before any factoring can start.

   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

   openssl rsa expects a raw private key file, not a certificate, so it errors with 'unable to load Private Key'. openssl x509 is the right command: it parses the full certificate and prints the embedded modulus under Subject Public Key Info.

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

   That flag extracts the raw public key in PEM form, not the parsed modulus and exponent, so you would need a second command to decode the blob. A single pass with -text -noout prints n and e in hex straight from the certificate, which is simpler for the 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 2Factor n to get p and q

   Observation

   The openssl output shows a modulus n of only 53 bits, which is nowhere near secure RSA. Trial division or a factoring database will produce 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 factors small integers but times out or refuses on numbers even a few dozen bits larger than this modulus. factordb.com is built for the job and stores results in advance, so it answers instantly at any CTF-range size. If WolframAlpha says the factorization was not computed, switch.

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

   The script has a placeholder token that Python cannot parse as an integer, so it raises a SyntaxError. Copy the modulus hex from the openssl output, convert it with int('hex_digits', 16), and put that value where PASTE_N_HERE sits before running.

   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 3Submit p and q as the flag

   Observation

   The description says the flag is just the two prime factors. So once p and q come out of factoring n there is no decryption step, and the format picoCTF{p,q} follows 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.