When you see an RSA problem, the first instinct is usually “factor it!” But this time, that was the trap. In fact, NOT attempting factorization was the key to solving this challenge—kind of interesting, right?
This writeup focuses not just on the solution, but on the thought process of “how did I come up with this attack method?” To be honest, I initially suspected a different approach and had to course-correct from there.
First Impressions
Here’s what we were given:
n(a massive integer)e = 20c(ciphertext)- Problem statement: “composed of large primes”
- “Factorization is not recommended”
When you hear “RSA problem,” the reflexive thought is “factor n to recover the private key,” right? I initially went down that path too.
But the problem statement explicitly says “factorization is not recommended.” That’s a clear hint. The challenge author is basically saying “that’s not the way.”
So if not factorization, then what? That’s where my thinking started.
Noticing the Anomaly: e=20
In typical RSA implementations, the public exponent e is usually 65537. It’s prime and computationally efficient.
But this time: e = 20.
Isn’t 20 way too small?
That’s when I remembered “Low Public Exponent Attack”—a pattern that occasionally shows up in CTF RSA challenges.
When e is small and there’s no padding, under certain conditions, the encryption can be easily broken. That condition is:
m^e < N
In other words, if the plaintext raised to the power of e is smaller than N, the modular arithmetic effectively doesn’t apply. The ciphertext c becomes simply m^e, and you can recover the plaintext just by taking the e-th root.
“Could this be it?”
The Decisive Observation: c’s Trailing Digits
Taking a closer look at the ciphertext c, the trailing digits were:
...369140625
This number felt familiar somehow.
I tried calculating:
python
>>> 5**20 95367431640625
The trailing digits match.
This isn’t a coincidence. If the plaintext m ends in 5, then m^20 will have a specific pattern in its trailing digits. And if that pattern appears directly in the ciphertext, it means the modular operation likely didn’t apply.
In other words, the hypothesis m^e < N seems correct.
That’s when my suspicion turned into confidence.
Implementation: Why Use gmpy2?
There are several ways to take the 20th root in Python.
The naive approach would be:
python
m = int(c ** (1/20))
But this is absolutely wrong.
The reason is that **(1/20) uses floating-point arithmetic. With RSA’s massive integers, even tiny errors are fatal. The moment you use float calculations, precision drops and you won’t get the correct value.
So what do you do?
Use gmpy2’s iroot()
python
import gmpy2 m, exact = gmpy2.iroot(c, 20)
iroot() calculates the integer n-th root accurately. Plus, it returns two values:
m: the calculated resultexact: a flag indicating whether it’s an exact match
This exact flag is crucial. If it’s True, it proves that m^20 == c. If False, your hypothesis was wrong.
In CTF, a lot of people get stuck by forgetting to check “exact.” I’ve made that mistake before, so now I always verify it.
The Actual Code
python
import gmpy2
from Crypto.Util.number import long_to_bytes
c = 640637430810406857500566702096274079797813783756285040245597839685897046611863482434073400367798608463086424458834137988104018091833145597410029013437735462302715129548973846379763728729428545767513419520378522822862961577973735078241754682355638335100576848694531121638889150356844531759174115231988144627267338389040375532574022748207315699664652980129278047686788121223259640746266698735050764418312913569057160089772324818273930095642209153888400571542769472334391306638409682954837629787109594899226928032724293229279318438125271482014147631619933912795541895525817682537949198255519604986878675604134812174747460052794647066527672861187040693055089502026533333902803596105771212450282047884079943754879040438929469847018747270202652653188907972546482593848436813297836191387991224410008628627845585580485535692961198532793983330642612321178773048997595566931650396018204656055319088331906719387438674611011910596470064874064138222641687608331096715571458404780449785022976473943452348149453421697207737409921591061793227611249155670614172413219039946694424819656348116324129922819825662148815322903833525904768421326834506787338352203369140625
e = 20
# Take the 20th root
m, exact = gmpy2.iroot(c, e)
print(f"Exact: {exact}")
print(long_to_bytes(m))
```
Running this:
```
Exact: True
b'picoCTF{t1ny_e_2fe2da79}'
```
It worked on the first try.
The moment I saw `exact=True`, I thought "Yes!" That sense of accomplishment in these moments—it never gets old.
---
## What If It Had Failed?
This time I was lucky to get `exact=True`, but what if it had been `False`?
Here are the possible patterns:
### Pattern 1: m^e >= N
In this case, the modular operation actually applied, so a simple iroot attack won't work.
But there's still a possibility that:
```
c + k*N (k=1,2,3...)
One of these values might exactly equal m^e. You’d try this next:
python
for k in range(1, 10):
candidate = c + k * n
m, exact = gmpy2.iroot(candidate, e)
if exact:
print(long_to_bytes(m))
break
Pattern 2: Padding Was Present
If padding like PKCS#1 was applied, a simple root attack won’t work. In that case, you’d need to consider different attacks (like Coppersmith’s Attack).
But since there was no padding this time, this wasn’t a concern.
Common Pitfalls for Beginners
Reflecting on this challenge, there are several points where beginners would definitely get stuck.
Trap 1: Immediately Trying to Factor
Even though the problem says “not recommended,” you reflexively run a factorization tool.
Factoring a 1024+ bit n isn’t realistic. It’s a waste of time.
Trap 2: Calculating with Float
python
m = int(c ** (1/20)) ``` This looks like it might work, but it fails due to precision errors. Always use gmpy2. ### Trap 3: Underestimating e If you have the fixed idea that "RSA = factorization," you'll overlook the value of e. But e often provides the attack vector. Especially small values of e are red flags. ### Trap 4: Forgetting to Check exact `iroot()` returns two values. If you don't check the second one (`exact`), you might end up with the wrong plaintext. --- ## Why Does Low Exponent Attack Work? Let me organize the technical background a bit. RSA encryption is: ``` c ≡ m^e (mod N) ``` Normally, `m` is the plaintext and `N` is a large composite number, so `m^e` will always be larger than `N`, making the modular operation effective and determining `c`. But what if: ``` m^e < N ``` In this case, the modular operation does nothing. Meaning: ``` c = m^e
This holds true as-is.
When this happens, encryption essentially becomes “just exponentiation,” and you can recover the plaintext just by taking the inverse operation (root).
This is the principle behind low exponent attacks.
Why Padding Matters
In actual RSA implementations (e.g., PKCS#1), padding is added to the plaintext. This makes m larger, guaranteeing that m^e > N.
With padding, low exponent attacks don’t work.
Conversely, no padding + small e = vulnerable.
CTF challenges feature these “intentionally broken implementations,” so knowing the theory gives you an advantage.
What I Learned from This Challenge
Looking back, here’s what this challenge taught me:
- Trust the problem hints
“Factorization is not recommended” → Follow it honestly - Be sensitive to anomalies
e=20is clearly abnormal → Attack vector - Observe trailing digits
...369140625→ Pattern of5^20→ Evidence of no modular operation - Choose the right tools
Not float, but gmpy2 → Precision is everything - Think ahead about failure branches
What ifexact=False? → Prepare the next move
If I Encounter the Same Problem Again
If I face a low exponent RSA problem next time, I’d solve it in this order:
- Check
e→ If small, suspect low exponent attack - Review problem statement → Check for factorization hints
- Observe
c‘s trailing digits → Signs of no modular operation - Execute
gmpy2.iroot(c, e) - If
exact=True, success; ifFalse, tryc + k*N
With this procedure in mind, I should be able to solve similar problems in seconds.
Closing Thoughts
This challenge, when you just look at the solution, is “just take the root.” But the thought process leading to that point was interesting.
The decision to abandon factorization—the “orthodox approach” to RSA, the observational skill to notice e’s anomaly, the deductive reasoning to form hypotheses from trailing digits—these elements combined led to the correct answer.
CTF isn’t about knowing the right answer; it’s a game of choosing the right path.
I hope this writeup serves as a reference point for someone’s decision-making the next time they encounter an RSA challenge.
Further Reading
If you found this low exponent RSA challenge interesting, there are several related topics worth exploring that build on similar cryptographic concepts and forensics techniques.
For another perspective on RSA vulnerabilities in CTF contexts, check out the Mini RSA picoCTF Writeup. This writeup explores a different variant of RSA attacks where the modulus N itself becomes the weak point, demonstrating how even slight implementation flaws can completely compromise cryptographic security.
File corruption and recovery is another common CTF theme that requires similar analytical thinking. The Corrupted file picoCTF Writeup walks through the process of identifying and repairing damaged file headers, which shares the same “observe anomalies and fix them” mindset we used when spotting the suspicious e=20 value in this challenge.
Finally, understanding when encryption is improperly applied extends beyond RSA. If you’re interested in learning about weak implementations in archive formats, Analyzing ZIP Encryption: When to Act covers common patterns in ZIP password attacks and explains how tools like zip2john can expose vulnerabilities in password-protected archives—another case where “proper implementation matters” becomes crucial.
These articles collectively reinforce the principle that CTF success often comes from recognizing implementation weaknesses rather than breaking theoretically sound cryptography.
Leave a Reply