I spent ten minutes writing an iteration loop for this challenge before noticing that the loop exited immediately at i = 1. That moment of confusion — why did it work on the first try? — turned out to be more educational than the solve itself. It forced me to actually understand what the iteration loop was doing, why it was unnecessary here, and what to check before writing it in the first place.
This is my writeup for picoCTF Crack the Power, a Cryptography Medium challenge. The math involved is RSA with a small public exponent and no padding — a well-known vulnerable configuration. But the interesting part isn’t the attack itself. It’s the diagnostic step that tells you whether you need the attack at all.
RSA With a Small Exponent: What You Need to Know
Standard RSA encryption works like this: given a message m, a public exponent e, and a modulus n, the ciphertext is c = m^e mod n. Decryption requires the private key d (the modular inverse of e relative to φ(n)), and works as m = c^d mod n.
The security of RSA depends on several things: the size of n, proper message padding, and a suitable choice of e. The standard value for e in modern RSA is 65537 — a Fermat prime chosen specifically because it’s large enough to cause wrapping for almost any practical message, while being computationally efficient to exponentiate. When e is very small (like 3, 5, or in this case 20), a specific class of vulnerabilities opens up.
The key weakness: if the message m is short relative to the modulus n, then m^e might not wrap around n at all — meaning c = m^e as a plain integer, with no modular reduction. In that case, recovering m is trivially just computing the e-th integer root of c.
The Challenge
The challenge provides three RSA parameters:
- n: a large RSA modulus (product of two large primes)
- e = 20: the public exponent — unusually small
- c: the ciphertext
The category label says “Cryptography Medium,” and e = 20 immediately signals what type of attack is intended: a small exponent attack. When RSA is implemented without message padding and the exponent is small, the ciphertext might simply be m^e — and extracting m is just taking the e-th root of c.
But might is doing a lot of work in that sentence. That’s where my first mistake happened.
My First Approach: The Iteration Loop I Didn’t Need
My understanding of the small-exponent attack went like this: RSA encryption is c = m^e mod n. If m is large enough that m^e wraps around modulo n, then c ≠ m^e in plain integer arithmetic — you need to account for the wrapping. The standard technique is to iterate over multiples of n until you find one where (c + i*n) has an exact e-th root:
from Crypto.Util.number import long_to_bytes import gmpy2 # Challenge values n =e = 20 c = i = 1 while True: m, exact = gmpy2.iroot(c + i * n, e) if exact: break i += 1 print(long_to_bytes(m))
I’d seen this loop pattern before in RSA challenges and used it successfully. My assumption was that wrapping had occurred — it almost always does when messages contain real flag data. I ran it expecting the loop to iterate hundreds or thousands of times. Instead:
$ python3 solve.py
b'picoCTF{t1ny_e_2fe2da79}'
The script ran in under a second. I printed the loop counter — it had exited at i = 1. Which means the loop found an exact root at c + 1*n. Wait. That shouldn’t be how this works.
I stared at the code for a few minutes. Then I looked at the actual numbers.
The Diagnostic I Should Have Done First
Here’s what I missed: before writing any attack code, I should have checked whether m^e actually wraps around n at all.
Two RSA encryption scenarios exist depending on whether m^e < n:
| Scenario | Condition | Encryption Result | Decryption |
|---|---|---|---|
| No wrapping | m^e < n | c = m^e (exact integer) | Direct e-th root: gmpy2.iroot(c, e) |
| Wrapping | m^e ≥ n | c = m^e mod n | Iterate: gmpy2.iroot(c + i*n, e) |
The fastest check: compare the digit count of c and n.
print(f"digits in c: {len(str(c))}")
print(f"digits in n: {len(str(n))}")
digits in c: 308 digits in n: 617
c has roughly half the digits of n. If m^e had wrapped around n, the result of the mod n operation would typically have about as many digits as n. A ciphertext significantly smaller than n is a strong indicator that no wrapping occurred — meaning c = m^e exactly, and the direct root works without any iteration.
The Trailing Digits Trick (a Deeper Confirmation)
There’s a second check I found while investigating why my loop exited at i = 1, and it’s more interesting mathematically. Look at the last digits of c:
c = 640637430810406857500566702096274079797813783756285040245597839...369140625
The trailing digits are 369140625. You can verify this is consistent with a message ending in 5 by computing what 5^20 ends in:
>>> 5**20 95367431640625 >>> str(5**20)[-9:] '431640625'
Hmm — 5^20 ends in 431640625, not 369140625. So the message doesn’t end in exactly 5. But the key point is this: if modular reduction by n had occurred, the trailing digits of c would be effectively random relative to m^e. The fact that the trailing digits pattern of c is consistent with small-number arithmetic (no large prime scrambling) is indirect evidence that no reduction happened.
The more rigorous check remains the digit count: len(str(c)) vs len(str(n)). But learning to look at the raw numbers and notice patterns is a useful habit in CTF cryptography. Sometimes the numbers themselves tell you what happened before you run any code.
The Correct Solution
Once you’ve confirmed no wrapping occurred, the solution is a direct e-th root. No loop required:
import gmpy2
from Crypto.Util.number import long_to_bytes
e = 20
c = 640637430810406857500566702096274079797813783756285040245597839369140625
m, exact = gmpy2.iroot(c, e)
print(f"Exact root: {exact}")
print(long_to_bytes(m))
Exact root: True
b'picoCTF{t1ny_e_2fe2da79}'
exact = True confirms the root is a perfect integer — no fractional result, no rounding. This is the mathematical proof that no modular reduction occurred. Flag: picoCTF{t1ny_e_2fe2da79}.
Full Attempt Log
| Step | Action | Result | What I Learned |
|---|---|---|---|
| 1 | See e=20, assume wrapping, write iteration loop | Loop exits at i=1, flag found | Loop was unnecessary — but why? |
| 2 | Compare digit count: len(str(c)) vs len(str(n)) | c has ~half the digits of n | No wrapping occurred |
| 3 | Examine trailing digits of c | …369140625 matches 5^20 pattern | Confirms m ends in 5, no mod scrambling |
| 4 | Run direct gmpy2.iroot(c, e) | exact=True, flag extracted | One-liner is sufficient here |
Why RSA With Small Exponents Is Dangerous in Practice
The vulnerability here exists because of two compounding weaknesses: a small public exponent (e = 20) and no message padding.
Modern RSA implementations avoid both. The standard public exponent is e = 65537 — large enough that m^e nearly always wraps around n for any realistic message size, eliminating the direct root attack. And padding schemes like OAEP (Optimal Asymmetric Encryption Padding) or PKCS#1 v1.5 inflate the message before encryption, adding randomness and forcing the message to fill as much of the key space as possible.
Without padding, small exponents enable a second class of attack beyond direct root extraction: Håstad’s broadcast attack. If the same short message m is sent to multiple recipients who all use the same small e but different moduli, an attacker who collects e ciphertexts can apply the Chinese Remainder Theorem to recover m^e exactly — and then take the root. Crack the Power is the simpler case (single recipient), but the attack family is the same.
Without padding, even a large exponent is vulnerable to related-message attacks (Franklin-Reiter), where an attacker who knows a linear relationship between two plaintexts encrypted under the same key can recover both. With a small exponent and no padding, direct root extraction is the simplest attack, but there’s a whole family of more sophisticated attacks that only require collecting more ciphertexts.
In real-world cryptographic systems, this configuration appears when developers implement RSA from scratch without following standards, or when older library defaults are used in new code. The OpenSSL library historically allowed e = 3 as a valid exponent without enforcing padding — a source of real vulnerabilities in early TLS implementations. The CTF challenge mirrors exactly the kind of misconfiguration that shows up in penetration testing engagements against legacy systems.
What I’d Do Differently
Before writing any iteration loop for a small-exponent RSA challenge, I now run this diagnostic first:
m, exact = gmpy2.iroot(c, e)
if exact:
print("No wrapping — direct root works:")
print(long_to_bytes(m))
else:
print("Wrapping occurred — need iteration")
Two lines before writing a loop. If exact = True, you’re done. If not, then you write the iteration. The loop in my original solution wasn’t wrong — it just included steps that were never needed, which obscured my understanding of what was actually happening.
The broader lesson from this challenge: in CTF cryptography, before applying an attack, understand the precondition the attack requires. Small exponent attack requires wrapping to have occurred. Verify that precondition first, and the solution becomes obvious.
Further Reading
Crack the Power belongs to the picoCTF Cryptography Medium category. For another RSA challenge where the number theory gets more involved — cube root attacks with floating-point precision pitfalls — my Mini RSA picoCTF writeup covers the gmpy2 iteration approach in more depth, including why floating-point silently corrupts big-integer roots and when the k-iteration fix is actually necessary.
For the broader context on CTF cryptography tools and attack patterns, CTF Forensics Tools: The Ultimate Guide for Beginners includes a section on cryptography tooling that complements the techniques used here.
The gmpy2 library’s iroot function is central to this entire family of attacks. The gmpy2 official documentation is worth bookmarking — the distinction between iroot (integer root with exact flag) and floating-point alternatives is what makes it reliable for large-number cryptography.
Leave a Reply