miniRSA

Description

Solution

1. Step 1Understand why e=3 is dangerous without padding
   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
   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.
   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!
   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

picoCTF{...}

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.