🔒 Mini RSA PicoCTF

• Files Given:

    N = <large 1024‑bit modulus>
    e = 3
    ciphertext c = <another large integer>
  

  Goal: Recover the plaintext flag.

---

🕵️‍♂️ What’s the vulnerability?

The exponent e = 3 is small. Normally, this term allows c^(1/3) to be computed easily if m^e < N. But here, the plaintext has been slightly padded so that m³ just exceeds N. This renders a direct root useless—but leads to a smart brute‑force trick

🚀 Step-by-Step Approach

1. Recall RSA basics

c = m^e mod N

With small e, if m^e < N, then mod N does nothing. But with padding, m^e > N, so it wraps around once. That means:

m^e = c + k*N
# we just need to find the k

2. Brute‑force possible k values

Since the padding is minimal, trying k = 0… few thousand is enough. Use gmpy2.iroot to get exact integer roots. Here’s a clean solution:

from Crypto.Util.number import long_to_bytes
from gmpy2 import iroot

# Paste your own N, c, e=3 below
N = ...  
c = ...  
e = 3

for k in range(5000):
    m, exact = iroot(c + k * N, e)
    if exact:
        plaintext = long_to_bytes(int(m))
        if b'pico' in plaintext:
            print(plaintext)
            break

3. Decode the flag

Converting the integer m back to bytes gives something like:

b'picoCTF{e_sh0u1d_b3_lArg3r_7adb35b1}'

---

🧠 Why it works

• Low exponent (e = 3) with slight padding means integer root + small brute forcing suffices.

• gmpy2.iroot ensures exact root detection—avoids float inaccuracies.

---

✅ Key Takeaways

• Low exponent RSA is weak if plaintext is small, but clever padding can foil direct attacks.

• Smart variation: try adding multiples of N, then take integer root.

• Tools like gmpy2.iroot are indispensable for precision.

• This is a classic “boneheaded padding scheme” vulnerability—valuable real-world learning.