ClusterRSA picoCTF 2026 Solution

Description

1. Step 1Identify multi-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 a 1024-bit n with 4 prime factors, each prime is roughly 256 bits. A 256-bit prime can be factored by Pollard's rho algorithm in seconds on a modern laptop. The name "cluster RSA" refers to this clustering of many small primes, which makes the modulus trivially factorable despite appearing large.

2. Step 2Factorise the modulus
   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!
   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 3Compute phi(n) and the private key
   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!
   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 = 24673
     Check: 7 * 24673 = 172711 = 5 * 34560 + 1   so 7d = 1 (mod phi)
   
   Encrypt m = 1234:
     c = 1234^7 mod 46189
       square-and-multiply: 1234^2 = 1522756 mod 46189 = 32079
                            1234^4 = 32079^2 mod 46189 = ...
     After three squarings and two multiplies, c works out to 39204.
   
   Decrypt:
     m = 39204^24673 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.

Alternate Solution

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.