Crack the Power

Description

Solution

1. Step 1Check if modular reduction occurred
   If the exponent e is small (e.g., 3) and the message m is short, then m^e may be less than n, meaning c = m^e exactly - no reduction mod n took place. You can take the e-th integer root directly.
   Learn more

   In RSA, encryption computes c = m^e mod n. The mod n operation is what makes RSA a one-way function - it mixes the exponentiated value with the large modulus in a way that is hard to reverse without knowing the private key. However, this reduction only activates when m^e >= n. If the message is small enough that m^e < n, then c = m^e as a plain integer - the modular reduction never takes effect.

   When e = 3 and the message is a short ASCII string (say, 20 bytes), m is on the order of 2^160. Cubing that gives roughly 2^480. An RSA modulus is typically 2048 bits (2^2048), so the cube is far smaller than n and no reduction occurs. This makes the ciphertext a perfect cube whose integer cube root directly yields the plaintext.

   This is why cryptographic standards (PKCS#1 v1.5, OAEP) require random padding to be added before encryption. The padding inflates the message to be close to the size of n, ensuring modular reduction always occurs and making the plaintext statistically indistinguishable from random.

2. Step 2Compute the integer e-th root
   Use gmpy2.iroot() which returns (root, is_exact). If is_exact is True, you have the plaintext m. Convert to bytes.

   python3 -c "
   import gmpy2
   from Crypto.Util.number import long_to_bytes
   c = <ciphertext_integer>
   e = 3
   m, exact = gmpy2.iroot(c, e)
   if exact:
       print(long_to_bytes(m).decode())
   "

   Copied!
   Learn more

   gmpy2 is a Python wrapper around the GMP (GNU Multiple Precision Arithmetic Library), which handles arbitrarily large integers efficiently. Python's built-in integers support arbitrary precision, but GMP is orders of magnitude faster for cryptographic-scale numbers (hundreds to thousands of digits).

   gmpy2.iroot(c, e) computes the integer e-th root of c - it returns the largest integer r such that r^e <= c, along with a boolean indicating whether the root is exact (r^e == c). The exact flag is critical: if it is False, the cube root attack does not apply and you would need a different approach (such as Coppersmith's method for partial modular reduction).

   long_to_bytes(m) from PyCryptodome converts a large integer back into its big-endian byte representation. RSA plaintexts are conventionally encoded as integers using big-endian byte order, so this function is the standard way to recover the original string from the decrypted integer.

3. Step 3Use RsaCtfTool for automation
   Alternatively, RsaCtfTool.py handles this attack automatically with the --attack cube_root flag.

   python3 RsaCtfTool.py --publickey key.pem --uncipherfile cipher.bin --attack cube_root

   Copied!
   Learn more

   RsaCtfTool is an open-source collection of RSA attack implementations designed for CTF competitions. It automates dozens of known RSA weaknesses including: small exponent attacks (e=3 cube root, Hastad's broadcast attack), weak moduli (Fermat factorization when p and q are close, smooth numbers, Pollard's p-1), common modulus attacks, Wiener's attack for small private exponents, and more.

   The tool accepts public keys in standard PEM format, raw n/e values, or several other formats, and attempts multiple attacks automatically or a specific one via --attack. It is the standard first step when approaching an unknown RSA challenge - running all attacks takes seconds and quickly rules out the most common weaknesses.

   Understanding why each attack works is more valuable than just running the tool. The cube root attack specifically: --attack cube_root checks if iroot(c, e) is exact, handling e=3, e=5, and other small exponents. If the root is not exact, it falls back to Coppersmith-style approaches for partial information.

Flag

picoCTF{...}

Small exponent attacks work when m^e < n - always use PKCS#1 v1.5 or OAEP padding to prevent this by making messages indistinguishable from random.