Mini RSA picoCTF 2021 Solution

Description

1. Step 1Recognize the small exponent weakness
   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
   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!
   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
   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!
   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.

Alternate Solution

Flag

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