Description
RSA group operations.
Setup
Download the provided files (n, e values and ciphertext) from the challenge page.
wget <challenge_url>/params.txt # download RSA parametersSolution
Want to try it yourself first?
The guided walkthrough reveals hints one step at a time.
Step 1
Examine the RSA parametersObservationI noticed the challenge description mentions 'RSA group operations' and provides multiple parameter files, which suggested inspecting the exponent size and the number of ciphertexts to identify which structural weakness (small exponent, common factor, or small message) applies here.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.bashcat params.txtpythonpython3 -c "bash# Check exponent sizebashe = <e_value>pythonprint(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.
For a 2048-bit RSA modulus with properly chosen primes, factoring is computationally infeasible and will either time out or return no result. The attack here does not require factoring n at all - it exploits the small exponent e=3 combined with multiple ciphertexts of the same message, which is a completely different weakness.
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 cases where the private exponent d is unusually small relative to n, not where the public exponent e is small. Checking e.bit_length() shows e=3, which is a small public exponent - the relevant attack is Hastad's broadcast, not Wiener's. Running a continued-fraction solver on e/n with e=3 produces no useful factorization.
Learn more
RSA group operations refers to the multiplicative group
Z/nZunder multiplication modulon. The RSA encryption operationc = m^e mod nis 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
Step 2
Hastad's Broadcast Attack (e=3, 3 ciphertexts)ObservationI noticed that the params file contained exactly three ciphertext and modulus pairs all sharing the same small exponent e=3, which is the precise precondition for Hastad's broadcast attack using CRT to reconstruct m^3 as an integer and then take the 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.pythonpython3 -c "bashfrom sympy.ntheory.modular import crtpythonfrom sympy import integer_nthrootbashn1, n2, n3 = <n1>, <n2>, <n3>bashc1, c2, c3 = <c1>, <c2>, <c3>bash# CRT: find x such that x = ci mod nibashresult, mod = crt([n1, n2, n3], [c1, c2, c3])bashm, exact = integer_nthroot(result, 3)pythonprint(bytes.fromhex(hex(m)[2:]))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 only two ciphertexts, CRT produces x = m^3 mod (n1*n2). Since m^3 may still be larger than n1*n2 for typical modulus sizes, x is not equal to m^3 as an integer - it is m^3 reduced modulo the product. The integer cube root of this reduced value is not m. All three ciphertexts are required so that the combined modulus n1*n2*n3 exceeds m^3, making the CRT result equal to m^3 exactly.
Tried: Use sympy's crt() with the ciphertexts as the moduli and the moduli as the residues (swapping the argument order).
sympy.ntheory.modular.crt expects (moduli_list, remainders_list) - the n values come first and the c values second. Swapping them feeds the ciphertext values as divisors and the huge moduli as the residues to reconstruct, which produces a nonsensical result far outside the expected range and causes integer_nthroot to return an inexact cube root or raise an error.
Learn more
Hastad's Broadcast Attack works when a message
mis encrypted with a small exponentetoeor more different recipients. Givenc_i = m^e mod n_ifori = 1..e, the Chinese Remainder Theorem combines these intox = m^e mod (n_1 * n_2 * ... * n_e). Sincem < n_ifor all i, we havem^e < n_1 * n_2 * ... * n_e(for small e and typical modulus sizes), sox = m^eexactly 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.crtor 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.Step 3
Decode the recovered integer to ASCIIObservationI noticed that the cube root recovered a large integer rather than a readable string, which suggested the plaintext was stored as a big-endian byte representation of the ASCII flag and needed to be converted back with to_bytes before decoding.Convert the recovered message integer m to bytes, then decode as ASCII or UTF-8 to read the flag string.pythonpython3 -c "bashm = <recovered_integer>bashflag = m.to_bytes((m.bit_length() + 7) // 8, 'big').decode()pythonprint(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) // 8to 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
- Cipher Identifier & Auto-DecoderPaste any ciphertext and the tool auto-runs every common decoder (base64, hex, Morse, ROT, Atbash, Bacon, binary, decimal, URL) and ranks the results by English-likeness.
- Frequency AnalysisAnalyze letter frequencies in a substitution cipher and interactively build the decryption mapping with auto-filled guesses.
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.