miniRSA picoCTF 2019 Solution

Description

1. Step 1

   Understand why e=3 is dangerous without padding

   Observation

   I noticed the challenge provided a very small public exponent (e=3) with no mention of padding, which suggested that if the plaintext message is short enough, m^3 might be less than N and the modular reduction never fires, making a direct integer root attack viable.

   In standard RSA, c = m^e mod N. When e is very small (e.g., 3) and the message m is short, m^e may be smaller than N - meaning the modular reduction never activates and c = m^3 as a plain integer. Taking the integer cube root of c directly recovers m.

   Learn more

   RSA (Rivest-Shamir-Adleman) is an asymmetric cryptosystem based on the mathematical difficulty of factoring the product of two large primes. Encryption is: c = m^e mod N. The public exponent e is chosen for efficiency - common values are 3, 17, and 65537 (F4). Smaller values of e make encryption faster, but introduce vulnerabilities when messages are not properly padded.

   The modular reduction step (mod N) is what makes RSA a one-way function - it wraps the exponentiated value around the modulus. However, if the plaintext m is so short that m^3 < N, the reduction never occurs: c = m^3 exactly. The flag as a byte string (e.g., "picoCTF{...}" is around 30 bytes = 240 bits) cubed gives roughly 720 bits. A typical RSA-1024 or RSA-2048 modulus is much larger, so the cube may indeed fit without wrapping.

   This is why padding schemes are mandatory in real-world RSA. PKCS#1 v1.5 padding and OAEP (Optimal Asymmetric Encryption Padding) both add random bytes before encryption, inflating the plaintext to nearly the size of N. This guarantees modular reduction occurs and makes the same plaintext encrypt to different ciphertexts each time (semantic security / IND-CPA).

2. Step 2

   Take the integer cube root of the ciphertext

   Observation

   I noticed that confirming m^3 < N meant the ciphertext was a perfect cube in the integers, which suggested using gmpy2.iroot(c, 3) with its exact flag to recover m precisely without the floating-point precision loss that would come from standard Python math functions.

   Use gmpy2.iroot(c, 3) which returns (root, exact). If exact is True, m^3 == c exactly and you have the correct plaintext integer. Convert it to bytes using the hex representation.

   python

   python3 -c "
   import gmpy2
   c = <paste ciphertext here>
   m, exact = gmpy2.iroot(c, 3)
   assert exact, 'Not a perfect cube - cube root attack may not apply'
   print(bytes.fromhex(hex(m)[2:]))
   "

   Copied!

   Expected output

   picoCTF{...}

   What didn't work first

   Tried: Using Python's built-in pow or math.pow to compute the cube root instead of gmpy2.iroot

   Float-based cube roots lose precision on 300+ digit integers - math.pow(c, 1/3) returns a float with only 53 bits of mantissa, so the result is wrong. int(c**(1/3)) will be off by one or more, and bytes.fromhex will produce garbled output. gmpy2.iroot uses arbitrary-precision integer arithmetic and the exact flag confirms whether the result is correct.

   Tried: Attempting RSA decryption with the private key formula (d = modular inverse of e mod phi(N)) instead of taking the cube root

   Without the private key d, standard decryption requires factoring N - which is computationally infeasible for large primes. The cube root attack works precisely because m^3 < N means modular reduction never occurred, so d is irrelevant. Trying to compute d or factor N with tools like yafu or factordb will fail on a properly chosen N.

   Learn more

   gmpy2.iroot(n, k) computes the integer k-th root of n using Newton's method adapted for arbitrary-precision integers. It returns a tuple (root, exact) where exact is True if root^k == n precisely. This is important because standard floating-point square/cube root functions lose precision for numbers with hundreds of digits - gmpy2 works exactly regardless of size.

   If exact is False, the cube root attack does not directly apply - m^e underwent modular reduction. In that case, more advanced techniques may be applicable: Coppersmith's method can recover m when part of the plaintext is known (e.g., the picoCTF{...} prefix) and the unknown portion is small relative to N^(1/e). This requires the lattice module or Sage.

   Converting the recovered integer to bytes: hex(m) produces '0x70696...', and [2:] strips the prefix. bytes.fromhex() converts the hex string to bytes. If the hex string has an odd length (possible if the leading byte is < 0x10), prepend a '0': bytes.fromhex(hex(m)[2:].zfill((m.bit_length()//8 + 1)*2)). pwntools' long_to_bytes(m) handles this edge case automatically.

Flag

Small exponent attacks work when e is tiny and the message is short enough that m^e < N - the modular reduction never activates, so the root can be taken directly.