Mini RSA

Description

Solution

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

   In RSA, ciphertext is computed as c = m^e mod n. When e=3 and the message m is small enough that m^3 < n, the modular reduction never activates -- meaning c = m^3 exactly, and you simply take the cube root of c to recover m.

   Even when m^3 is slightly larger than n, the relationship c = m^3 - k*n holds for a small integer k. By iterating k = 0, 1, 2, ... and checking whether c + k*n is a perfect cube each time, you can recover m with minimal computation.

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.
   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 EOFCopied!
   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 broadcast attack variant or simply 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.

Flag

picoCTF{...}

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