Very Smooth picoCTF 2022 Solution

Description

1. Step 1Understand the smooth p-1 weakness

   Observation

   The challenge is called Very Smooth, and gen.py builds primes whose p-1 has only small factors. Pollard's p-1 exploits exactly that smoothness through Fermat's little theorem.

   If all prime factors of p-1 are small (say <= 10^6), then B! is divisible by p-1. By Fermat's little theorem, a^(p-1) ≡ 1 (mod p), so a^(B!) ≡ 1 (mod p), meaning p divides a^(B!)-1.

   Learn more

   Fermat's Little Theorem: For prime p and any a not divisible by p: a^(p-1) ≡ 1 (mod p).

   A number M is B-smooth if every prime factor of M is at most B. If p-1 is B-smooth, then p-1 divides B! (because B! contains every prime up to B raised to a high power). Therefore a^(B!) ≡ a^(k*(p-1)) ≡ (a^(p-1))^k ≡ 1 (mod p), so p | a^(B!) - 1. As long as q-1 is NOT B-smooth, q does not divide a^(B!) - 1, and gcd(a^(B!) - 1, N) = p exactly.

   Toy walkthrough with N = pq, p = 331, q = 271:
     p - 1 = 330 = 2 * 3 * 5 * 11    (all small -> 11-smooth)
     q - 1 = 270 = 2 * 3^3 * 5       (also smooth, but suppose only p-1 were)
   
     Use bound B = 11. Then 11! is a multiple of 330 = p-1.
     Compute a = 2^(11!) mod N incrementally:
         a = 2
         a = a^2 mod N   (now 2^2)
         a = a^3 mod N   (now 2^6)
         a = a^4 mod N   (now 2^24)
         ...
         a = a^11 mod N  (now 2^(11!) mod N)
   
     At each step, check g = gcd(a - 1, N).
     As soon as the running exponent becomes a multiple of p-1 = 330,
     we have a ≡ 1 (mod p) but a != 1 (mod q),
     so gcd(a - 1, N) returns p (a non-trivial factor of N).

   The crucial efficiency trick: a^(B!) mod N is built incrementally - one short modular exponentiation per j - so we never construct the astronomical number B! itself. Each step is a = pow(a, j, N), which uses square-and-multiply in O(log j * log^2 N) bit operations.

2. Step 2Implement Pollard's p-1

   Observation

   With the smoothness confirmed, the standard algorithm follows: accumulate 2 raised to successive factorials mod N, checking the gcd against N at each stage, until one prime factor falls out.

   Start with a=2 and repeatedly compute a = a^j mod N for j=2..B. After each step, check if gcd(a-1, N) is a non-trivial factor.

   python

   python3 -c "
   from math import gcd
   
   # Replace with actual values from the challenge files
   n = 0xYOUR_N_VALUE
   e = 65537
   c = 0xYOUR_CIPHERTEXT
   
   def pollard_p_minus_1(n, B):
       a = 2
       for j in range(2, B + 1):
           a = pow(a, j, n)            # accumulate: after iter j, a = 2^(j!) mod n
           if j % 10000 == 0 or j == B:
               g = gcd(a - 1, n)
               if 1 < g < n:
                   return g
       return None
   
   for B in (10**4, 10**5, 10**6, 10**7):
       print(f'Trying B = {B}')
       p = pollard_p_minus_1(n, B)
       if p is not None:
           q = n // p
           print(f'Found: p = {p}')
           print(f'       q = {q}')
           phi = (p-1)*(q-1)
           d = pow(e, -1, phi)
           flag_int = pow(c, d, n)
           print('Flag:', flag_int.to_bytes((flag_int.bit_length()+7)//8, 'big').decode())
           break
   else:
       print('no smooth factor found up to B = 10^7; switch attacks (Fermat, Wiener, ECM)')
   "

   Copied!

   What didn't work first

   Tried: Use sympy.factorint or factor() from a CAS tool to factor N directly.

   General-purpose factoring in sympy falls back to trial division and Pollard's rho, neither of which uses the smooth p-1 structure, so on a 1024-bit modulus they run indefinitely. Pollard's p-1 is fast precisely when p-1 is smooth, and general tools do not reach for that shortcut on their own.

   Tried: Set B = 10^7 from the start without checking intermediate gcds.

   Waiting until the bound before checking the gcd for the first time overshoots: once both p-1 and q-1 divide the accumulated exponent, the gcd collapses to N and no useful factor appears. Check frequently, every ten thousand steps or so, and the loop stops as soon as one prime is isolated, before the other divides in too.

   Learn more

   Why the loop is one accumulator, not pow each time. The standard Pollard p-1 loop computes a = 2^(B!) mod n incrementally: after iteration j, the running value of a equals 2^(j!) mod n, because a = pow(a, j, n) raises the previous 2^((j-1)!) to the j-th power. This matches the toy walkthrough above. Recomputing pow(a, j!, n) from scratch each step would multiply the work by another log(j) factor for nothing.

   Heuristic for choosing B. Start at B = 10^4. If the loop completes without finding a non-trivial factor, double an order of magnitude: 10^5, then 10^6, then 10^7. By B = 10^7 the prime is unlikely to be smooth at all, and you should switch attacks (Fermat for close primes, Wiener for small private exponent, ECM for medium-smooth factors). The script above iterates this ladder for you.

   Non-trivial-factor check. The 1 < g < n guard is essential: gcd(a - 1, n) = 1 means we have not yet hit a multiple of p-1, and gcd(a - 1, n) = n means both p-1 and q-1 are smooth and we wrapped past both factors. The script returns None in those cases instead of failing silently.

   The algorithm runs in O(B * log(B) * log^2(N)) time, which is very fast for small B. Checking gcd every 10,000 steps rather than every step is an optimization: the gcd check is cheap, but checking every iteration still adds visible overhead at large B.

   The pow(a, j, n) call uses Python's built-in three-argument modular exponentiation, which uses fast square-and-multiply and stays within modular bounds. This is far faster than computing the full exponentiation then taking mod.

3. Step 3Decrypt the ciphertext with the recovered factors

   Observation

   Once Pollard's p-1 returns one prime, the rest is standard RSA: divide for the other, derive phi from (p-1)(q-1), take the modular inverse for d, and exponentiate the ciphertext.

   With p and q known, compute phi(N) = (p-1)(q-1), then d = e^-1 mod phi(N), then flag = c^d mod N.

   python

   python3 -c "
   from Crypto.Util.number import long_to_bytes
   
   p = 0xYOUR_P
   q = 0xYOUR_Q
   e = 65537
   c = 0xYOUR_CIPHERTEXT
   n = p * q
   
   phi = (p-1) * (q-1)
   d = pow(e, -1, phi)
   m = pow(c, d, n)
   print(long_to_bytes(m).decode())
   "

   Copied!

   What didn't work first

   Tried: Compute phi(N) as N - 1 instead of (p-1)(q-1) because N looks prime.

   N is a semiprime, a product of two large primes, not a prime itself, and phi equals N minus 1 only for a prime. Use N minus 1 as the modulus for the inverse and d comes out entirely wrong, so the decryption returns garbage. The right totient is (p-1)(q-1), which needs both primes, exactly what Pollard's p-1 just recovered.

   Tried: Use long_to_bytes(m) without .decode() and pipe to a hex dump to look for the flag.

   The flag bytes are printable ASCII, so decoding is right and succeeds when the decryption is correct. Get d or N wrong and long_to_bytes returns non-ASCII, so the decode raises a UnicodeDecodeError. Treat that as a signal to recheck the factorization, not a reason to drop the decode.

   Learn more

   Standard RSA decryption: m = c^d mod N where d = e^-1 mod phi(N) and phi(N) = (p-1)(q-1). Python 3.8+ supports pow(e, -1, phi) for modular inverse directly.

   To prevent Pollard's p-1 attack, RSA key generation must ensure that p-1 (and q-1) have at least one large prime factor - ideally close to the size of p itself. Such primes are called safe primes: p is safe if p = 2q + 1 where q is also prime. OpenSSL's genrsa command generates safe primes by default for this reason.

Flag

gen.py constructs primes p, q where p-1 and q-1 are smooth (each factor is a product of 16-17 bit primes plus 1). Sieve primes up to ~200000, build the prime-power exponent ladder, and Pollard's p-1 finds p in seconds. Standard RSA decryption then yields the flag.