ClusterRSA picoCTF 2026 Solution

Description

1. Step 1

   Identify multi-prime RSA

   Observation

   I noticed the challenge is named 'clusterRSA' and the setup description says the modulus feels 'more crowded than usual,' which suggested that n is composed of more than two prime factors rather than standard two-prime RSA.

   The modulus n is a product of 4 (or more) smaller primes rather than the standard 2. This makes n much easier to factor because each prime factor is proportionally smaller.

   Learn more

   Standard RSA uses a modulus n = p * q where p and q are two large primes of roughly equal size (~1024 bits each for a 2048-bit key). The security rests on the integer factorization problem: given n, it is computationally infeasible to find p and q. For a 2048-bit n, the best known algorithms (General Number Field Sieve) require roughly 10¹⁸ operations.

   Multi-prime RSA (defined in RFC 3447) uses three or more prime factors: n = p1 * p2 * p3 * ... * pk. This is sometimes used to speed up private-key operations using the Chinese Remainder Theorem. However, if the total bit length of n is fixed but shared among more primes, each individual prime is proportionally smaller - and smaller primes are much easier to find.

   For this challenge, the modulus is roughly 332 bits composed of 4 primes of about 83 bits each. An 83-bit prime can be factored by Pollard's rho in seconds (O(2⁴¹) operations). More generally, the smaller each factor, the faster factorisation becomes. The name "cluster RSA" refers to this clustering of many small primes into a single modulus that appears large but is trivially factorable.

2. Step 2

   Factorise the modulus

   Observation

   I noticed that multi-prime RSA means each individual factor of n is proportionally smaller and therefore weaker, which suggested that factoring the modulus is the key step and that tools like factordb.com or sympy's factorint() could handle it quickly.

   Paste n into factordb.com first - most CTF moduli are precomputed there. Otherwise run sympy's factorint() or Sage's factor().

   bash

   # Online: factor n at factordb.com

   Copied!

   bash

   sage -c "print(factor(YOUR_N))"

   Copied!

   python

   python3 -c "
   from sympy import factorint
   n = YOUR_N
   print(factorint(n))
   "

   Copied!

   What didn't work first

   Tried: Run yafu or msieve locally on the full modulus before checking factordb.com

   yafu and msieve are powerful tools but take minutes-to-hours on a modulus even 256 bits wide if they apply GNFS instead of Pollard's rho. FactorDB already has precomputed factors for virtually every CTF challenge modulus, so querying it first costs nothing and immediately returns the full factorisation. Only fall back to local tools when FactorDB reports the number as 'C' (composite, unknown factors).

   Tried: Use sympy.isprime() or a primality test to check whether n itself is prime

   A primality test on n only tells you whether n is composite - which is expected for any RSA modulus. It does not return the factors. The next step after confirming n is composite is factorisation via sympy.factorint(n) or Sage's factor(n), which actually splits n into its prime components that you can feed into the phi formula.

   Learn more

   FactorDB (factordb.com) is a collaborative database of known factorizations. CTF authors typically pick moduli that have been precomputed and submitted by previous solvers, so FactorDB returns the factors instantly. Always check FactorDB first.

   Don't expect Pollard's rho to chew through 256-bit primes on its own. Rho runs in O(p^1/2) per prime, which for a 256-bit factor is roughly 2¹²⁸ operations - infeasible. The toy example below uses 5-bit primes purely for illustration. The real reason these challenge moduli are easy is that the factors are precomputed (factordb) or the primes are intentionally weak (small, smooth, or close together).

   If FactorDB does not have it, try sympy.factorint() with default heuristics, then specialised tools like yafu, msieve, or cado-nfs for larger moduli. SageMath's factor(n) wraps PARI/GP and chooses the best algorithm automatically; this is the standard tool for CTF cryptography.

   See the RSA Attacks for CTF post for the full taxonomy: small e, common modulus, Wiener, Coppersmith, and shared-prime attacks.

3. Step 3

   Compute phi(n) and the private key

   Observation

   I noticed that once all four prime factors of n were recovered, the standard RSA decryption formula still applies with phi(n) extended to the product of (p_i - 1) for each prime, which suggested computing phi and the modular inverse of e to recover d and then decrypt the ciphertext.

   For n = p1*p2*p3*p4, phi(n) = (p1-1)*(p2-1)*(p3-1)*(p4-1). Verify gcd(e, phi) == 1 first, then compute d = e^(-1) mod phi(n).

   python

   python3 << 'EOF'
   from math import prod, gcd
   from sympy import mod_inverse
   
   primes = [p1, p2, p3, p4]  # from factorisation
   n = prod(primes)
   e = YOUR_E
   c = YOUR_C
   
   phi = prod(p - 1 for p in primes)
   assert gcd(e, phi) == 1, "e and phi(n) must be coprime to invert"
   
   d   = mod_inverse(e, phi)
   m   = pow(c, d, n)
   print(m.to_bytes((m.bit_length() + 7) // 8, 'big'))
   EOF

   Copied!

   What didn't work first

   Tried: Compute phi as (n - 1) the way you would for a prime modulus

   phi(n) = n - 1 only when n itself is prime (Fermat's little theorem). For a composite RSA modulus, phi(n) = product of (p_i - 1) over each prime factor. Using n - 1 produces a completely wrong phi, meaning mod_inverse(e, phi) will return a d that decrypts to garbage.

   Tried: Use pow(c, d, n) but convert the result with hex(m)[2:] and bytes.fromhex()

   hex(m)[2:] can produce an odd-length hex string (e.g. 'f' when the first byte is 0x0f), and bytes.fromhex() raises ValueError on odd-length input. The robust conversion is m.to_bytes((m.bit_length() + 7) // 8, 'big'), which always pads correctly and never throws on valid plaintexts.

   Learn more

   Euler's totient function phi(n) counts integers from 1 to n that are coprime to n. For a product of distinct primes, phi(p1*p2*...*pk) = (p1-1)*(p2-1)*...*(pk-1). This formula is the algebraic foundation of RSA decryption: the private exponent d satisfies e*d ≡ 1 (mod phi(n)), computed via the extended Euclidean algorithm.

   The decryption is m = c^d mod n using Python's built-in pow(c, d, n), which uses fast modular exponentiation (square-and-multiply) and is efficient even for thousand-bit numbers. The plaintext integer m is then converted to bytes: hex(m)[2:] strips the '0x' prefix, and bytes.fromhex() converts the hex string to bytes.

   An edge case: if m's hex representation has an odd number of digits (e.g., 'f' instead of '0f'), bytes.fromhex() will fail. Use m.to_bytes((m.bit_length() + 7) // 8, 'big') for a robust conversion that always produces correctly-padded bytes.

   Multi-prime RSA worked example (toy parameters):
     primes = [11, 13, 17, 19]
     n   = 11 * 13 * 17 * 19 = 46189        (~16 bits)
     phi = 10 * 12 * 16 * 18 = 34560
     e   = 7    (coprime to phi: gcd(7, 34560) = 1)
   
   Modular inverse via extended Euclidean (or Python pow(7,-1,34560)):
     d = 29623
     Check: 7 * 29623 = 207361 = 6 * 34560 + 1   so 7d = 1 (mod phi)
   
   Encrypt m = 1234:
     c = 1234^7 mod 46189
       square-and-multiply: 1234^2 = 1522756 mod 46189 = 44708
                            1234^4 = 44708^2 mod 46189 = 22478
     After three squarings and two multiplies, c works out to 44953.
   
   Decrypt:
     m = 44953^29623 mod 46189 = 1234.  Recovered.
   
   Why factoring is fast here:
     Each prime is ~5 bits in this toy, so trial division finishes in
     microseconds. For a real 1024-bit cluster-RSA n with k=4 primes,
     each factor is 256 bits and Pollard's rho is O(p^(1/2)) = O(2^128)
     per prime - infeasible from scratch. The CTF moduli are easy
     because factordb has them precomputed (or the primes are
     intentionally weak: small, smooth, or close together).
   
   Defense: stick to 2-prime RSA with primes ~n^(1/2). Multi-prime
   RSA is only safe when each individual prime is still 1024+ bits,
   i.e. for ridiculously large n.

Flag

Multi-prime RSA (4 prime factors) is weak because each factor is ~n^(1/4), making factorisation trivial with Pollard's rho or factordb.