Skip to main content
picoCTF Solutions
picoCTF 2019CryptographyHard

b00tl3gRSA3 picoCTF 2019 Solution

Exploit a flaw in RSA key generation to decrypt a ciphertext and recover the flag.

Published: April 2, 2026Updated: August 13, 2026

Description

Why use p and q when I can use more? This is multi-prime RSA: the modulus n is a product of many primes instead of two. That is not more secure, it is less: more primes means each one is smaller, and a modulus built from small primes factors easily. This is not Wiener's small-d attack.

Setup

Remote

Connect to the service. It prints the modulus n, the public exponent e, and the encrypted flag c.

Install sympy for factoring (or use factordb.com).

bash
nc 2019shell1.picoctf.com <PORT_FROM_INSTANCE>
bash
pip3 install sympy pycryptodome

Solution

Want to try it yourself first?

The guided walkthrough reveals hints one step at a time.

Walk me through it
  1. Step 1Recognize multi-prime RSA
    Observation
    The description says n is a product of many primes rather than two. That forces each individual prime to be much smaller than in standard RSA, which puts it within reach of ordinary factoring tools. No Wiener's attack or small-exponent trick needed.
    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.
    bash
    # Confirm n factors into many primes, not two.

    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 needs d smaller than n^(1/4). Here d comes from a full-size e, so it is large and the continued-fraction attack returns nothing. The 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 large or random e, not e = 3, so the cube-root shortcut does not apply; printing e from the banner confirms it. The vulnerability is purely that n factors into many small primes, whatever e happens to be.

    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 2Factor n and build phi from all the primes
    Observation
    Once n is known to be many small primes, sympy.factorint decomposes it quickly. For a product of distinct primes the totient is the product of every (p_i - 1), so collect all the factors before computing d = inverse(e, phi).
    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

    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 k of the (p_i - 1) terms. Use only two and the rest are left out, giving a wrong phi, and d = inverse(e, wrong_phi) decrypts to garbage.

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

    sympy.totient is correct but calls factorint internally, and on a multi-prime modulus with several hundred-bit primes it can run for many minutes or time out. Call factorint once, keep the result, and multiply the (p - 1) terms yourself: faster, and the logic stays visible.

    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.

Interactive tools
  • RSA CalculatorDecrypt RSA ciphertexts, factor n from the sum of primes, or generate key parameters. Handles arbitrarily large BigInt values.

Flag

Reveal flag

picoCTF{...}

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.

Key takeaway

RSA's strength rests on how hard it is to factor a product of two large primes. Split the modulus into more than two and each prime shrinks for the same modulus size, which puts the whole thing within reach of Pollard rho or ECM. Once the primes are known, phi(n) is just the product of (p_i - 1) and the private key falls out. The same trap applies to any scheme resting on a hard factoring or discrete-log problem: shrinking the factors or the subgroup by design collapses the security margin.

Related reading

Useful tools for Cryptography

Where to go next

Try these next