Crack the Power picoMini by CMU-Africa Solution

Description

1. Step 1Check if modular reduction occurred

   Observation

   The public exponent e is suspiciously small, and the challenge is called 'crack the power'. So the ciphertext may equal m^e as a plain integer, with no modular reduction, which opens the door to a direct integer root.

   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. Raising that to the 3rd power gives roughly 2^480. An RSA modulus is typically 2048 bits (2^2048), so the result 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

   Observation

   With no modular reduction confirmed, c equals m^e exactly. gmpy2.iroot takes the exact e-th integer root, which Python's float math cannot do at thousands of bits.

   Use gmpy2.iroot() which returns (root, is_exact). If is_exact is True, you have the plaintext m. Convert to bytes.

   python

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

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Use Python's built-in pow() or float() to compute the e-th root directly

   Python floats carry only 64 bits of precision, so c**(1/e) on a 3200-bit ciphertext silently rounds and gives a completely wrong integer, and long_to_bytes then returns garbage. gmpy2.iroot works on arbitrary-precision integers and returns an exact flag confirming the root is perfect.

   Tried: Run the script without verifying the 'exact' flag and decode whatever iroot returns

   If modular reduction did happen, meaning m^e is at least n, iroot still returns a value but exact comes back False and the integer is not the plaintext. Decode it anyway and you get random bytes or a UnicodeDecodeError. Check exact before trusting the root.

   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

   Observation

   A public key PEM ships alongside the ciphertext. RsaCtfTool can run the small-exponent attack straight against that key file, so there is no need to extract n and e by hand.

   Alternatively, RsaCtfTool.py handles this attack automatically with the --attack cube_root flag.

   python

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

   Copied!

   What didn't work first

   Tried: Run RsaCtfTool with --attack cube_root when the actual exponent is 20, not 3

   The --attack cube_root flag targets e=3 specifically and does not generalize to e=20, so the tool reports no plaintext: its implementation computes iroot(c, 3) rather than iroot(c, e). Run the manual gmpy2.iroot(c, 20) script instead, or look for a separate flag covering the general small-exponent case.

   Tried: Pass --attack wiener instead, assuming a small exponent means a small private key

   Wiener's attack targets a small private exponent d, not a small public exponent e. They are different weaknesses: small d leaks the private key through continued fractions on e/n, while small e opens the e-th root shortcut when m^e stays below n. Here d is a normal 2048-bit value, so Wiener's produces nothing.

   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

Per-instance flag. Prefix confirmed across 2 independent instances (hashes seen: ..., 837d7226). The hash suffix varies per team/instance.