Skip to main content
picoCTF Solutions
picoCTF 2026CryptographyMedium

ClusterRSA picoCTF 2026 Solution

The modulus is multi-prime, so factor out every prime, build phi from all of them, and decrypt as usual.

Published: March 20, 2026Updated: September 20, 2026

Description

A message has been encrypted using RSA, but this time something feels... more crowded than usual. Can you decrypt it? Download the message.txt.

Setup

Download message.txt
Download message.txt and inspect the RSA parameters (n, e, c).
Notice that n is 'more crowded than usual'.
bash
cat message.txt

Solution

Want to try it yourself first?

The guided walkthrough reveals hints one step at a time.

Walk me through it
  1. Step 1Identify multi-prime RSA
    Observation
    The name is clusterRSA and the setup calls the modulus more crowded than usual. That means more than two prime factors, not standard 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 1018 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 333 bits composed of 4 primes of 84 bits each. An 84-bit factor is 25 decimal digits, comfortably inside the range where ECM (the elliptic-curve method, what Sage, yafu and factordb all reach for) finds it in seconds. Pollard's rho would need on the order of 242 iterations per prime, so it is the wrong tool here despite being the one people reach for first. 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 2Factorise the modulus
    Observation
    With more primes packed into the same modulus, each one is proportionally smaller and easier to find. Factoring is the whole job, and factordb or sympy's factorint handles 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
    bash
    sage -c "print(factor(8749002899132047699790752490331099938058737706735201354674975134719667510377522805717156720453193651))"
    python
    python3 -c "
from sympy import factorint
n = 8749002899132047699790752490331099938058737706735201354674975134719667510377522805717156720453193651
print(factorint(n))
"

    Expected output

    {9671406556917033397931773: 1, 9671406556917033398314601: 1, 9671406556917033398439721: 1, 9671406556917033398454847: 1}
    What didn't work first

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

    yafu and msieve are capable, but on even a 256-bit modulus they can run for minutes or hours if they choose the number field sieve over Pollard's rho. FactorDB already holds precomputed factors for nearly every CTF modulus, so ask it first. Fall back to local tools only when it reports the number as composite with unknown factors.

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

    A primality test tells you n is composite, which every RSA modulus is. It does not give you the factors. Factor it with sympy or Sage and feed the primes 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(p1/2) per prime, which for a 256-bit factor is roughly 2128 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
    Observation
    With all four primes recovered, ordinary RSA decryption still applies: phi is the product of each prime minus one. Compute it, invert e to get d, and decrypt.
    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 = [
    9671406556917033397931773,
    9671406556917033398314601,
    9671406556917033398439721,
    9671406556917033398454847,
]  # from factorisation
n = prod(primes)
e = 65537
c = 184663950095417089249407325967298806692456158102141374180762585653354636328370817189107315557630497

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

    Expected output

    b'picoCTF{mul71_rsa_...}'
    What didn't work first

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

    phi equals n minus one only when n itself is prime. For a composite modulus it is the product of each prime minus one. Use n minus one and phi is wrong, so the inverse gives 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.
Interactive tools
  • RSA CalculatorDecrypt RSA ciphertexts, factor n from the sum of primes, or generate key parameters. Handles arbitrarily large BigInt values.
Alternate Solution

Skip the scripting and use the RSA Calculator on this site. Paste in the four fields it asks for: n (the modulus), e (public exponent), d (private exponent - compute as pow(e, -1, phi) with phi = product of (p-1) over the prime factors), and the ciphertext. It handles BigInt values natively, so no Python or SageMath required.

Flag

Reveal flag

picoCTF{mul71_rsa_...}

Multi-prime RSA with 4 prime factors is weak because each factor is only n^(1/4), here 84 bits, which factordb already knows and ECM recovers in seconds. The four primes are also nearly identical in value, which weakens the modulus further. The flag is shown abbreviated on this page; work the steps above to recover the full value.

Key takeaway

RSA rests entirely on how hard it is to factor n. With two primes of roughly equal size, each is about the square root of n and finding one takes enormous effort. Pack four primes into the same bit length and each shrinks to the fourth root, which speeds factoring by orders of magnitude. The mistake is splitting key material across more primes without growing n to match: multi-prime RSA is safe only when each individual prime is still large enough on its own.

Related reading

Useful tools for Cryptography

Where to go next

Try these next