miniRSA picoCTF 2019 Solution

Description

1. Step 1Understand why e=3 is dangerous without padding

   Observation

   The public exponent is e=3 and nothing mentions padding. If the message is short enough, m^3 may be smaller than N, so the modular reduction never fires and a plain integer cube root recovers it.

   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 2Take the integer cube root of the ciphertext

   Observation

   Confirming m^3 < N means the ciphertext is a perfect cube over the integers. gmpy2.iroot(c, 3) with its exact flag recovers m precisely, without the floating-point loss that standard Python math would introduce.

   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 cube roots lose precision on 300-digit integers: math.pow(c, 1/3) returns a float with only 53 bits of mantissa, so the answer is wrong, and int(c**(1/3)) comes out off by one or more. gmpy2.iroot uses arbitrary-precision integers, and its exact flag confirms whether the result is right.

   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, ordinary decryption means factoring N, which is infeasible for large primes. The cube root attack works because m^3 < N, so no modular reduction ever happened and d is irrelevant. Trying to recover d or factor N with yafu or factordb will fail on a well-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.