Mini RSA picoCTF 2021 Solution

Description

1. Step 1

   Recognize the small exponent weakness

   Observation

   I noticed the challenge description explicitly warned about a 'small danger in using small exponents' and that the provided e equals 3, which suggested the cube root attack where m^3 may only slightly exceed n and can be recovered by iterating over small multiples of n.

   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 2

   Iterate k until you find a perfect cube root

   Observation

   I noticed that once e=3 was confirmed as the exponent, the relationship c = m^3 - k*n for a small unknown integer k meant that iterating c + k*n and checking for a perfect cube root with gmpy2.iroot was the direct recovery path.

   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 on numbers larger than 2^53. For a 1024-bit ciphertext the result is off by thousands, so the equality check always fails. gmpy2.iroot performs arbitrary-precision Newton iteration and returns an exact boolean flag, making it the only reliable option for RSA-sized integers.

   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 actual plaintext size. For this challenge k is small, but 'small' can still mean hundreds or low thousands of iterations. Stopping too early just means the loop exits without finding a result. Let the loop run until the exact flag is True - there is no performance issue since 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 3

   Fallback: Hastad's broadcast attack

   Observation

   I noticed that if the k-iteration runs without finding a perfect cube root, the plaintext is too large for the single-ciphertext approach, which suggested using the Chinese Remainder Theorem across e ciphertexts of the same message under different moduli to recover m^e exactly on 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 only one ciphertext and a full-sized plaintext, k can reach into the billions before hitting a perfect cube, making the loop practically infinite. CRT is necessary because it fuses all three equations to produce a combined value equal to m^e on the integers - no iteration needed. The single-ciphertext attack is a shortcut that only applies 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 mod (n1*n2*n3), which is m^3 - a very large integer, not m itself. Converting that directly to bytes produces hundreds of bytes of garbage. The final iroot(combined, e) call is mandatory to recover m from its cube, and the assert exact guard 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.