picoCTF Solutions
picoCTF 2026CryptographyMedium

ClusterRSA

Published: March 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' -- it has more than 2 prime factors.

cat message.txt

Solution

  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.
  2. Step 2Factorise the modulus
    Submit n to factordb.com, or use Sage's factor() function, or run yafu/msieve. With 4 primes each roughly n^(1/4) in size, trial division or Pollard's rho will succeed quickly.
    # Online: factor n at factordb.com
    sage -c "print(factor(YOUR_N))"
    python3 -c " from sympy import factorint n = YOUR_N print(factorint(n)) "
  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). Compute d = e^(-1) mod phi(n).
    python3 << 'EOF' from math import prod 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) d = mod_inverse(e, phi) m = pow(c, d, n) print(bytes.fromhex(hex(m)[2:])) EOF

Flag

picoCTF{clust3r_rs4_f4ct0r3d_...}

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