picoCTF Solutions
picoMini by redpwnCryptographyHard

college-rowing-team picoMini by redpwn Solution

Published: April 2, 2026

Description

RSA group operations.

Setup

Download the provided files (n, e values and ciphertext) from the challenge page.

bash
wget <challenge_url>/params.txt  # download RSA parameters

Solution

Walk me through it
  1. Step 1Examine the RSA parameters
    Read the provided n, e, and ciphertext values. Check if multiple ciphertexts are provided for the same message under different public exponents, or if the same exponent is reused across multiple moduli. The attack depends on the structure.
    bash
    cat params.txt
    python
    python3 -c "
    bash
    # Check exponent size
    bash
    e = <e_value>
    python
    print(f'e = {e}, bits = {e.bit_length()}')
    bash
    "
    Learn more

    RSA group operations refers to the multiplicative group Z/nZ under multiplication modulo n. The RSA encryption operation c = m^e mod n is a group exponentiation. Many RSA attacks exploit weaknesses in how the group parameters (n, e) are chosen rather than breaking the underlying hard problem.

    Common attacks based on parameter weaknesses:

    • Small public exponent (e=3): if the same message is encrypted under e=3 different moduli, Hastad's broadcast attack uses CRT to recover m
    • Common factor: if two moduli share a prime factor, gcd(n1, n2) reveals it
    • Small message: if m^e < n, simply take the integer eth root of c
  2. Step 2Hastad&apos;s Broadcast Attack (e=3, 3 ciphertexts)
    If the same plaintext m was encrypted with e=3 under three different moduli n1, n2, n3, use the Chinese Remainder Theorem to find m^3, then take the integer cube root to recover m.
    python
    python3 -c "
    bash
    from sympy.ntheory.modular import crt
    python
    from sympy import integer_nthroot
    bash
    n1, n2, n3 = <n1>, <n2>, <n3>
    bash
    c1, c2, c3 = <c1>, <c2>, <c3>
    bash
    # CRT: find x such that x = ci mod ni
    bash
    result, mod = crt([n1, n2, n3], [c1, c2, c3])
    bash
    m, exact = integer_nthroot(result, 3)
    python
    print(bytes.fromhex(hex(m)[2:]))
    bash
    "
    Learn more

    Hastad's Broadcast Attack works when a message m is encrypted with a small exponent e to e or more different recipients. Given c_i = m^e mod n_i for i = 1..e, the Chinese Remainder Theorem combines these into x = m^e mod (n_1 * n_2 * ... * n_e). Since m < n_i for all i, we have m^e < n_1 * n_2 * ... * n_e (for small e and typical modulus sizes), so x = m^e exactly as an integer. Taking the eth root recovers m.

    Chinese Remainder Theorem (CRT) states that if n_i are pairwise coprime, there exists a unique solution modulo their product for any set of residues. In Python, sympy.ntheory.modular.crt or a manual implementation using modular inverses computes this efficiently.

    Hastad broadcast attack with e = 3 and 3 ciphertexts (toy moduli):
  m  = 5            (the secret message, < every n_i)
  n1 = 7 * 11 = 77
  n2 = 13 * 17 = 221
  n3 = 19 * 23 = 437
  e  = 3

Ciphertexts:
  c1 = 5^3 mod 77  = 125 mod 77 = 48
  c2 = 5^3 mod 221 = 125 mod 221 = 125
  c3 = 5^3 mod 437 = 125 mod 437 = 125

CRT: find x such that
  x = 48  mod 77
  x = 125 mod 221
  x = 125 mod 437

Compute N = 77 * 221 * 437 = 7,436,429.
Each partial: N_i = N / n_i, and y_i = N_i^(-1) mod n_i.
  N1 = 96577,  y1 = 96577^(-1) mod 77 = ...
  N2 = 33649,  y2 = 33649^(-1) mod 221 = ...
  N3 = 17017,  y3 = 17017^(-1) mod 437 = ...
  x = sum(c_i * N_i * y_i) mod N
    = 125          (since m^3 = 125 < N)

Integer cube root: iroot(125, 3) = 5.  Recovered.

The key insight: m^3 = 125 fits inside the combined modulus
n1*n2*n3 ~ 7M, so the CRT result is exactly m^3 as an integer
(no further reduction). Taking the integer cube root recovers m
without ever factoring any n_i.

For real CTF parameters, m can be up to ~683 bits while
n1, n2, n3 are each ~2048 bits, and the cube product is ~6144
bits - more than enough room for a real message.
  3. Step 3Decode the recovered integer to ASCII
    Convert the recovered message integer m to bytes, then decode as ASCII or UTF-8 to read the flag string.
    python
    python3 -c "
    bash
    m = <recovered_integer>
    bash
    flag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()
    python
    print(flag)
    bash
    "
    Learn more

    RSA operates on integers, but plaintexts are byte strings. The standard encoding converts the byte string to a big-endian integer: the first byte of the message becomes the most significant byte. int.to_bytes() reverses this. The length is (bit_length + 7) // 8 to round up to the nearest byte.

    If the decoding fails or produces garbage, verify that you are using the correct byte order and that the recovered integer does not have leading zero bytes lost in the conversion. A picoCTF{ prefix should be visible once correctly decoded.

Flag

picoCTF{...}

RSA broadcast attack - the same message encrypted with e=3 under three different moduli allows CRT combination followed by an integer cube root to recover the plaintext without ever factoring n.

Want more picoMini by redpwn writeups?

Browse picoMini by redpwnFull library

Useful tools for Cryptography

What to try next