b00tl3gRSA3 picoCTF 2019 Solution

Description

1. Step 1

   Recognize multi-prime RSA

   Observation

   I noticed the challenge description explicitly says the modulus n is a product of many primes instead of two, which suggested that each individual prime factor must be much smaller than in standard RSA and therefore factorable with ordinary tools rather than requiring Wiener's attack or a small-exponent shortcut.

   Standard RSA uses n = p*q with two large primes. b00tl3gRSA3 uses n = p1*p2*...*pk for many primes. To keep n a similar size, each prime is much smaller, which makes n factorable with ordinary tools. e is large/random here, so small-exponent and Wiener (small-d) attacks do not apply; the weakness is purely that n factors.

   bash

   # Grab n, e, c from the service banner.

   Copied!

   bash

   # Confirm n factors into many primes, not two.

   Copied!

   Expected output

   b'picoCTF{...}'

   What didn't work first

   Tried: Try Wiener's attack (small private exponent d) because the name sounds like an obfuscated RSA variant.

   Wiener's attack requires d to be smaller than n^(1/4). Here d is derived from a full-size e, so d is large and the continued-fraction attack returns nothing useful. The real weakness is that n has many small prime factors, not that d is small.

   Tried: Attempt a small-exponent attack (e = 3 cube-root of c) because e might be small.

   The service issues a random or large e, not e = 3, so the cube-root shortcut does not apply. Printing e from the banner confirms it is large. The vulnerability is purely factorability of n into many small primes, which is independent of the size of e.

   Learn more

   Why more primes is weaker. RSA security rests on the difficulty of factoring n. For a fixed modulus size, splitting n into k primes makes each prime roughly (size of n)/k bits. Small primes fall quickly to trial division, Pollard rho, or ECM, so a many-prime modulus is far easier to factor than a two-prime one of the same length.

2. Step 2

   Factor n and build phi from all the primes

   Observation

   I noticed that once n is confirmed to be a product of many small primes, sympy.factorint can decompose it quickly; and since the totient for a product of distinct primes is the product of all (p_i - 1) terms, I needed to collect every factor before computing d = inverse(e, phi) to correctly decrypt c.

   Factor n into its full list of primes (sympy.factorint or factordb). Then compute phi(n) as the product of (p_i - 1) over all prime factors, derive d = inverse(e, phi), and decrypt c.

   python

   python3 - <<'PY'
   from sympy import factorint
   from Crypto.Util.number import inverse, long_to_bytes
   
   n = <PASTE_N>
   e = <PASTE_E>
   c = <PASTE_C>
   
   factors = factorint(n)                 # {p1: 1, p2: 1, ...} for many small primes
   phi = 1
   for p, mult in factors.items():
       phi *= (p - 1) * p**(mult - 1)     # general form; mult is 1 for distinct primes
   
   d = inverse(e, phi)
   m = pow(c, d, n)
   print(long_to_bytes(m))
   PY

   Copied!

   If factorint is slow, paste n into factordb.com, which already has many of these moduli fully factored.

   What didn't work first

   Tried: Compute phi as (p - 1) * (q - 1) using only two of the factors returned by factorint.

   When n has k distinct prime factors, phi(n) is the product of ALL (p_i - 1) terms. Using only two primes leaves the remaining (p_i - 1) factors out, producing a wrong phi. The resulting d = inverse(e, wrong_phi) decrypts to garbage instead of the flag.

   Tried: Use sympy.totient(n) directly instead of multiplying (p_i - 1) manually.

   sympy.totient calls factorint internally and is correct, but on a multi-prime modulus with several primes in the hundreds of bits it can take many minutes or time out. Computing factorint once, caching the result, and multiplying (p - 1) terms yourself is faster and makes the logic explicit.

   Learn more

   Why the totient changes. For two-prime RSA, phi(n) = (p-1)(q-1). For a product of distinct primes the totient is multiplicative: phi(n) = product of (p_i - 1). Use that exact totient to invert e; using the two-prime formula would give a wrong d. See the RSA Attacks for CTF guide for the broader factoring-based attacks.

Flag

Multi-prime RSA, not Wiener. n is a product of many small primes, so factor it (sympy.factorint / factordb), compute phi as the product of (p_i - 1) over all factors, invert e to get d, and decrypt c.