📋 Challenge Info
The Mission: Decrypt the ciphertext when the public exponent e is dangerously small (e=3).
Platform: picoCTF
Challenge Name: Mini RSA
Category: Cryptography
✨ Introduction: The “Gift” of a Tiny Exponent
When I first opened the challenge file and saw e: 3, my heart skipped a beat. In the world of RSA, e=3 is like leaving the front door unlocked but thinking a “keep out” sign will save you.
Normally, RSA relies on the difficulty of factoring the giant modulus N. But when e is this small, we don’t even need to touch N. We can use pure integer mathematics to “brute-force” our way back to the plaintext. In this writeup, I’ll walk you through the Low Public-Exponent Attack—a classic technique that every CTF player should have in their arsenal.
🧩Challenge Overview: The Math Behind the Flaw
We are given a massive N, a ciphertext c, and e = 3
The core equation of RSA is:
The “Clock” Analogy:
Think of the modulo N operation as a clock. After the value m^3 goes past N, it “wraps around” and starts over. Our ciphertext c is where the hand of the clock stopped. To find the original m, we need to “rewind” the clock by adding N back until the total value is a perfect cube.
Mathematically, this means finding an integer k such that:
Once c + k ・ N is a perfect cube, the cube root is our message m.
🛠️ My Cryptography Toolbox
Before starting, ensure you have the necessary libraries. You can install them via pip: pip install gmpy2 pycryptodome
- pycryptodome: Used for
long_to_bytesto convert the final number into a readable flag. - gmpy2: Essential for high-precision math. Its
iroot()function is a lifesaver—it handles massive integers and tells you exactly if a root is an integer.
🧭 Step-by-Step Solution
🚀 Step 1: Identifying the Attack Vector
First, I tried a simple cube root of c. It wasn’t a perfect integer.
My Thought Process: “Okay, so the modulo N did happen, but probably only a few times.” Since k is likely small in this “Mini” challenge, we can iterate through it.
🛠️ Step 2: Crafting the Solver
I wrote a script to test values of k starting from 0.
from Crypto.Util.number import long_to_bytes
import gmpy2
# Values from the challenge
N = 1615765684...
e = 3
c = 1220012318...
k = 0
while True:
# Adding N back to 'c' to find the original m^3
target = c + k * N
m, is_exact = gmpy2.iroot(target, e)
if is_exact:
print(f"Found it! k = {k}")
print(long_to_bytes(m).decode(errors='ignore'))
break
k += 1
if k > 100000: # Safety break
print("Search limit reached.")
break
🏁 Step 3: Execution & The “Aha!” Moment
Running the script, it found the correct k almost instantly (it turned out to be quite small!).
Insight on k: In this challenge, k is small because the plaintext m is only a few times larger than N after being cubed. If m were truly massive, k would be too large to brute-force, requiring advanced lattice-based attacks like Coppersmith’s Method.
🚩 Capture The Flag
The output revealed the flag hidden within some padding:
picoCTF{e_sh0u1d_b3_lArg3r_6e2e6bda}
Reflecting on the Flag: The flag itself gives us the lesson: “e should be larger”. Modern systems typically use e = 65537 to prevent this exact type of attack while keeping encryption efficient.
💡 Takeaways for Cryptography Beginners
- Why e = 3 is Dangerous: Without proper padding (like OAEP), the relationship between m and c is too direct. RSA isn’t just about big numbers; it’s about how they interact.
- Floating Point Trap: Never use
target ** (1/3)for large numbers. Standard floating-point math will lose precision. Always usegmpy2.iroot. - The Importance of Padding: Real-world RSA adds random padding so that m^e is always much larger than N, making this “clock-rewinding” attack impossible.
📚 Summary
The “Mini RSA” challenge is a perfect example of how a secure algorithm fails with poor parameters. By adding N back to the ciphertext, we bypassed the RSA “trapdoor” without needing the private key.
Stay curious, and always check your exponents!
For more crypto writeups, click here
Category: picoCTF-Cryptography-Medium
📚 Further Reading
Here are related articles from alsavaudomila.com that complement this challenge:
Leave a Reply