john_pollard picoCTF 2019 Solution

Description

1. Step 1Extract n, e, and c from the certificate
   Open the certificate file. It contains the RSA public key (n and e) and the ciphertext c. The modulus n is small enough to factor by trial division or using factordb.com.
   bash

   cat certificate

   Copied!
   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
   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!
   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 3Compute d and decrypt
   With p and q known, compute phi(n) = (p-1)(q-1), then d = modular inverse of e mod phi(n). Finally decrypt: m = pow(c, d, n).
   python

   python3 << 'EOF'
   from sympy import mod_inverse
   
   n = <N>
   e = <E>
   c = <C>
   p = <P>
   q = <Q>
   
   phi = (p - 1) * (q - 1)
   d = mod_inverse(e, phi)
   m = pow(c, d, n)
   print(bytes.fromhex(hex(m)[2:]).decode())
   EOF

   Copied!
   Learn more

   Why this works. RSA encrypts as c = m^e mod n, decrypts as m = c^d mod n. The private exponent d satisfies e*d ≡ 1 (mod φ(n)), so e*d = 1 + k*φ(n) for some integer k. Then by Euler's theorem m^φ(n) ≡ 1 (mod n), giving c^d = m^(e*d) = m^(1 + k*φ(n)) = m * (m^φ(n))^k ≡ m (mod n).

   Worked toy example. Take p = 11, q = 13, n = 143, φ = 120, e = 7. Compute d = e^(-1) mod 120:

   Extended Euclidean on (7, 120):
     120 = 17*7 + 1
     =>  1 = 120 - 17*7
     =>  d = -17 mod 120 = 103
   Verify: 7*103 = 721 = 6*120 + 1   ✓
   
   Encrypt m = 42:
     c = 42^7 mod 143 = 230539333248856064 mod 143 = 95
   
   Decrypt c = 95:
     m = 95^103 mod 143 = 42   ✓

   Square-and-multiply. pow(c, d, n) never builds the literal integer c^d. It walks the bits of d from MSB to LSB, maintaining an accumulator: square at every step, multiply by c when the current bit is 1, reduce mod n after every operation. That is O(log d) multiplications - milliseconds for 2048-bit RSA.

   Why mod_inverse exists. The inverse of e modulo φ(n) exists if and only if gcd(e, φ(n)) = 1. RSA picks e coprime to φ(n) exactly so that this step succeeds. Common choices: e = 3, 17, 65537 - all primes, all small enough for fast encryption, all rarely sharing a factor with φ(n) for randomly chosen primes.

Alternate Solution

Flag

Factor the small RSA modulus to get p and q, compute d via modular inverse, and decrypt with pow(c, d, n).