Mini RSA picoCTF 2021 Solution

Description

1. Step 1Recognize the small exponent weakness

   Observation

   The description warns about the danger of small exponents, and e is 3. That is the cube root attack: m^3 may only just exceed n, and iterating over small multiples of n recovers it.

   The challenge uses e=3. When the public exponent is very small and the message is not padded sufficiently, m^e may be only slightly larger than n. This means the ciphertext c = m^3 mod n is equivalent to m^3 - k*n for some small integer k. Try increasing values of k until the result is a perfect cube.

   Learn more

   The basic cube root attack. RSA encrypts as c = m^e mod n. With e = 3, if m^3 < n the reduction is a no-op and c = m^3. Take the integer cube root of c and you have m.

   This challenge twist: m^3 just barely exceeds n. By definition of mod, c = m^3 - k*n for some non-negative integer k = floor(m^3 / n). Therefore m^3 = c + k*n. If k is small (single digits to a few thousand), iterate:

   for k in 0, 1, 2, ...:
       candidate = c + k*n
       m, exact = iroot(candidate, 3)
       if exact:
           return m

   Worked toy example. Take n = 1000, e = 3, plaintext m = 11:

   m^3 = 1331
   c = 1331 mod 1000 = 331
   k = floor(1331 / 1000) = 1
   
   Recovery (do not know m):
     k = 0:  iroot(331, 3) = (6, False)         no
     k = 1:  iroot(331 + 1000, 3) = (11, True)  ✓
     recovered m = 11

   How big can k get? If m is the same bit-length as n, then k ≈ m^3 / n can be roughly n^2 in magnitude - completely infeasible to iterate. The attack only works when the plaintext is short enough that m^3 fits in "a few wraparounds" of n. For a flag plaintext padded with a few bytes, k is typically 1 to a few thousand. If iteration runs for millions of values without success, the message is too long and you need stronger techniques (Coppersmith, broadcast).

   Why iroot not ** (1/3). Floating-point cube roots lose precision past 2^53. gmpy2.iroot(c, 3) uses arbitrary-precision Newton iteration: start with an estimate x_0, refine via x_(i+1) = (2*x_i + c // x_i^2) / 3 until x_(i+1) == x_i, then check x^3 == c.

2. Step 2Iterate k until you find a perfect cube root

   Observation

   With e=3 confirmed, the relationship is c = m^3 - k*n for some small unknown k. So iterate c + k*n and test each for a perfect cube root with gmpy2.iroot.

   Use gmpy2.iroot to compute the integer cube root of c + k*n. The function returns (root, exact) - when exact is True, you have found m. Convert the resulting integer to bytes to read the flag.

   python

   python3 << 'EOF'
   from gmpy2 import iroot
   from Crypto.Util.number import long_to_bytes
   
   n = <n>
   c = <c>
   e = 3
   
   k = 0
   while True:
       candidate = c + k * n
       m, exact = iroot(candidate, e)
       if exact:
           print(long_to_bytes(m).decode())
           break
       k += 1
   EOF

   Copied!

   Expected output

   picoCTF{e_sh0u1d_b3_lArg3r_...}

   What didn't work first

   Tried: Use Python's built-in float cube root: m = round(c ** (1/3)) and check m**3 == c.

   Floating-point exponentiation silently loses precision above 2^53. On a 1024-bit ciphertext the result is off by thousands, so the equality check never passes. gmpy2.iroot runs arbitrary-precision Newton iteration and returns an exact flag, which makes it the only reliable choice at RSA sizes.

   Tried: Start the k-iteration but cap it at k=10 after reading that the attack requires m^3 to be only slightly larger than n.

   The gap depends on the plaintext size. Here k is small, but small can still mean hundreds or a few thousand iterations, and stopping early just means the loop exits empty-handed. Let it run until the exact flag comes back true; each iroot call is fast even on large numbers.

   Learn more

   gmpy2 is a Python wrapper around the GMP arbitrary-precision library. iroot(x, n) returns (root, exact) where root is the integer n-th root of x and exact is True only if root^n == x exactly. This is far more reliable than floating-point cube root functions, which lose precision on 300+ digit numbers.

   This attack is known as the small-exponent attack. The standard defense is to use OAEP padding (PKCS#1 v2), which randomizes messages before encryption so that even identical plaintexts encrypt to different ciphertexts. Modern RSA implementations always use padding - never raw textbook RSA.

3. Step 3Fallback: Hastad's broadcast attack

   Observation

   If the k-iteration runs out without a perfect cube root, the plaintext is too large for the single-ciphertext approach. The Chinese Remainder Theorem, applied across e ciphertexts of the same message under different moduli, recovers m^e exactly over the integers.

   Given the same plaintext m encrypted under e different public keys (n_1, n_2, ..., n_e) all with the same small exponent e, use the Chinese Remainder Theorem to compute c = m^e mod (n_1 * ... * n_e). Since m^e is below this product, c equals m^e exactly and an integer e-th root recovers m.

   python

   python3 - <<'EOF'
   from gmpy2 import iroot
   from sympy.ntheory.modular import crt
   from Crypto.Util.number import long_to_bytes
   
   # Three ciphertexts of the same m under e=3 with different moduli
   ns = [<n1>, <n2>, <n3>]
   cs = [<c1>, <c2>, <c3>]
   e = 3
   
   # CRT recombines the three ciphertexts into m^e mod (n1*n2*n3)
   combined, _ = crt(ns, cs)
   
   m, exact = iroot(combined, e)
   assert exact, "CRT result was not a perfect e-th power - check inputs"
   print(long_to_bytes(int(m)).decode())
   EOF

   Copied!

   What didn't work first

   Tried: Apply the single-ciphertext k-iteration to the Hastad step instead of CRT, iterating k on just one of the three ciphertexts.

   With one ciphertext and a full-sized plaintext, k can reach into the billions before hitting a perfect cube, so the loop never ends in practice. CRT fuses all three equations into a combined value equal to m^e over the integers, with no iteration at all. The single-ciphertext attack is a shortcut that only works when the message is short relative to the modulus.

   Tried: Pass the three moduli and ciphertexts to sympy crt but forget to take the integer cube root, treating the combined output as the plaintext directly.

   The CRT result is m^e taken mod the product of the moduli, which is m^3, a very large integer, not m. Convert that straight to bytes and you get hundreds of bytes of garbage. The final iroot call recovers m from its cube, and the exactness assertion confirms the inputs were consistent.

   Learn more

   When to reach for Hastad. The single-ciphertext cube-root iteration only works when k = floor(m^3 / n) is small. If iteration walks past tens of millions of k values without success, the plaintext is comparable in size to the modulus and the basic attack is not going to terminate. Hastad sidesteps this by exploiting the structure of multiple equations: m^e mod n_1, m^e mod n_2, ..., m^e mod n_e. CRT solves them simultaneously to give m^e mod (n_1 * ... * n_e), and since m^e < n_1 * ... * n_e by construction (the moduli are large enough), the modular result is m^e on the integers. One integer e-th root finishes the recovery.

   Same-padding caveat: Hastad in its raw form requires the plaintext to be literally identical across all e encryptions. If each encryption applies a different linear padding m_i = a_i * m + b_i, the generalised Hastad / Coppersmith attack still recovers m as long as the padding polynomials are known.

Flag

When e=3 and m is lightly padded, m^3 barely exceeds n - iterate k until you find a perfect integer cube root.