Very Smooth picoCTF 2022 Solution

Description

1. Step 1Understand the smooth p-1 weakness
   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
   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!
   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
   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!
   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.