Skip to main content
picoCTF Solutions
picoMini by redpwnCryptographyHard

college-rowing-team picoMini by redpwn Solution

Break a custom encryption scheme by exploiting algebraic weaknesses in its design.

Published: April 2, 2026Updated: August 25, 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

Want to try it yourself first?

The guided walkthrough reveals hints one step at a time.

Walk me through it
  1. Step 1Examine the RSA parameters
    Observation
    The description mentions RSA group operations and ships several parameter files. Check the exponent size and the ciphertext count to see which structural weakness this is: small exponent, shared factor, or small message.
    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
    "
    What didn't work first

    Tried: Try to factor the modulus n directly using a tool like factordb or yafu to recover the private key.

    A 2048-bit modulus with properly chosen primes does not factor: the attempt times out or returns nothing. This attack never factors anything. It exploits a small exponent plus several ciphertexts of the same message, a different weakness entirely.

    Tried: Assume the attack is a small private exponent attack (Wiener's attack) and run a continued-fraction solver on e/n.

    Wiener's attack targets a small private exponent, not a small public one. The exponent here is 3, which is public, so the relevant attack is Hastad's broadcast. A continued-fraction solver on that ratio produces nothing useful.

    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's Broadcast Attack (e=3, 3 ciphertexts)
    Observation
    There are exactly three ciphertext and modulus pairs, all sharing an exponent of 3. That is the precondition for Hastad's broadcast attack: reconstruct the cube with the Chinese Remainder Theorem, then take its cube root.
    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(m.to_bytes((m.bit_length() + 7) // 8, 'big'))
    bash
    "
    What didn't work first

    Tried: Apply CRT to only two ciphertexts (n1, c1) and (n2, c2) instead of all three, then take the cube root.

    With two ciphertexts, the CRT result is the cube reduced modulo the product of two moduli, and the cube may still exceed that product, so what you have is not the cube as an integer and its root is not the message. Three ciphertexts push the combined modulus above the cube, which makes the CRT result exact.

    Tried: Use sympy's crt() with the ciphertexts as the moduli and the moduli as the residues (swapping the argument order).

    sympy's CRT takes the moduli first and the remainders second. Swap them and the ciphertexts become divisors while the moduli become residues, producing a result far outside the expected range and a cube root that is inexact or errors out.

    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 automatically, 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, n1, n2, n3 are each ~2048 bits, so
their product is ~6144 bits. Since m < n_i for every i, m^3 is
always below that product, so the message may be as large as a
full 2048-bit block and the CRT result is still exact. (The
~683-bit ceiling belongs to the single-modulus cube-root
attack, where m^3 must fit under one 2048-bit n.)
  3. Step 3Decode the recovered integer to ASCII
    Observation
    The cube root gives a large integer rather than text, because the plaintext is the flag's bytes read as a big-endian number. Convert it back.
    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.

Interactive tools
  • RSA CalculatorDecrypt RSA ciphertexts, factor n from the sum of primes, or generate key parameters. Handles arbitrarily large BigInt values.
  • Number Base ConverterConvert numbers between binary, octal, decimal, and hexadecimal instantly. Enter any value and see all four bases update in real time.

Flag

Reveal flag

picoCTF{1_gu3ss_p30pl3_p4d_m3ss4g3s_f0r_4_r34s0n}

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.

Key takeaway

A small public exponent turns dangerous the moment the same unpadded message goes to several recipients: the Chinese Remainder Theorem stitches their ciphertexts into the message raised to that exponent over the integers, and since the message is smaller than each modulus, an integer root recovers it without factoring anything. Hastad's broadcast attack is exactly why PKCS#1 and OAEP mandate randomized padding, which gives each recipient a different effective plaintext and makes the combination useless. The same CRT machinery reappears in fault-injection attacks against RSA-CRT implementations.

Related reading

Useful tools for Cryptography

Where to go next

Try these next