Description
What happens if you have a small exponent? There is a twist though, we padded the plaintext so that (M ** e) is just barely larger than N. Let’s decrypt this: ciphertext
🧩 Challenge Overview
📝 In this challenge we recover a plaintext from an RSA ciphertext where the public exponent e is very small (e = 3). That makes the classic Low Public-Exponent Attack applicable: if the plaintext mmm is small enough that me<Nm^e < Nme<N, then the ciphertext c=me mod Nc = m^e \bmod Nc=memodN is actually equal to mem^eme as an integer (not wrapped by modulo NNN). Taking the integer eee-th root of c recovers m.
✅ Here we use a small loop that tests c + k*N for being a perfect cube — when it is, the cube root is the plaintext.
🚀 Step 1 — Inspecting the challenge
🔎 The provided values:
N— RSA modulus (very large)e = 3— public exponent (very small)c— ciphertext
🧠 Idea: because e is 3, try to see if m^3 < N. If so m = roundroot(c, 3). If not exactly, there exists an integer k with m^3 = c + k*N. So test c + k*N for being a perfect cube for small k.
Explanation: For any RSA ciphertext, me≡c(modN)m^e \equiv c \pmod Nme≡c(modN). If mem^eme as an integer equals c+kNc + kNc+kN for some integer kkk, and if c+kNc + kNc+kN is a perfect eee-th power, then its eee-th root is m. So we brute-force small k until c + k*N becomes an exact cube.
🛠️ Step 2 — The solver (solve.py)
🔧 Code used (shortened explanation inline):
from Crypto.Util.number import * # long_to_bytes, conversions
import gmpy2 # fast integer math, iroot
# given values
N = 1615765684321463054078226051959887884233678317734892901740763321135213636796075462401950274602405095138589898087428337758445013281488966866073355710771864671726991918706558071231266976427184673800225254531695928541272546385146495736420261815693810544589811104967829354461491178200126099661909654163542661541699404839644035177445092988952614918424317082380174383819025585076206641993479326576180793544321194357018916215113009742654408597083724508169216182008449693917227497813165444372201517541788989925461711067825681947947471001390843774746442699739386923285801022685451221261010798837646928092277556198145662924691803032880040492762442561497760689933601781401617086600593482127465655390841361154025890679757514060456103104199255917164678161972735858939464790960448345988941481499050248673128656508055285037090026439683847266536283160142071643015434813473463469733112182328678706702116054036618277506997666534567846763938692335069955755244438415377933440029498378955355877502743215305768814857864433151287
e = 3
c = 1220012318588871886132524757898884422174534558055593713309088304910273991073554732659977133980685370899257850121970812405700793710546674062154237544840177616746805668666317481140872605653768484867292138139949076102907399831998827567645230986345455915692863094364797526497302082734955903755050638155202890599808146956044568639690002921620304969196755223769438221859424275683828638207433071955615349052424040706261639770492033970498727183446507482899334169592311953247661557664109356372049286283480939368007035616954029177541731719684026988849403756133033533171081378815289443019437298879607294287249591634702823432448559878065453908423094452047188125358790554039587941488937855941604809869090304206028751113018999782990033393577325766685647733181521675994939066814158759362046052998582186178682593597175186539419118605277037256659707217066953121398700583644564201414551200278389319378027058801216150663695102005048597466358061508725332471930736629781191567057009302022382219283560795941554288119544255055962
i = 1
while True:
m, ok = gmpy2.iroot(c + i * N, e) # test if c + i*N is a perfect e-th power
if ok:
break
i += 1
print(long_to_bytes(m))
📌 What the loop does:
- For
i = 1,2,3,...computec + i*N. - Use
gmpy2.iroot(x, e)to test ifxis a perfecte-th power. IfokisTrue,mis the integere-th root. - Convert
mfrom integer to bytes and print the plaintext (the flag).
Explanation: This is a direct brute-force on the unknown integer k (named i in the script) until we find the k making c + k*N a perfect cube. gmpy2.iroot returns the integer root and a boolean indicating exactness — fast and reliable for big integers.
🏁 Step 3 — Run & Capture the Flag
▶️ Running the code produced:
b' picoCTF{e_sh0u1d_b3_lArg3r_6e2e6bda}'
🏳️🌈 Capture the Flag:
picoCTF{e_sh0u1d_b3_lArg3r_6e2e6bda}
Explanation: The printed bytes contain padding spaces and the flag string. Converting the bytes to text yields the flag above.
📊 Summary
| Step | Command / Action | Purpose | Key Result |
|---|---|---|---|
| 1 | Inspect N, e, c | Check if low-e attack is possible (e=3) | Suspected m is recoverable by cube root method |
| 2 | gmpy2.iroot(c + i*N, e) in loop | Find i such that c + i*N is perfect cube | Found m (integer cube root) |
| 3 | long_to_bytes(m) and print() | Convert integer plaintext to bytes and show flag | picoCTF{e_sh0u1d_b3_lArg3r_6e2e6bda} |
💡 Beginner Tips
- 🔢 If
eis small (like 3) and the message is small, first try the direct integer root ofc— i.e.,iroot(c, e). - 🔁 If direct root fails, try
c + k*Nfor smallkbecause me=c+kNm^e = c + kNme=c+kN. - 🧪 Use
gmpy2.iroot— it’s fast for huge integers and tells you if the root is exact. - 🛡️ In practice, always use a large exponent (commonly
e = 65537) and proper padding (e.g., OAEP) to avoid these attacks.
📚 What you learn (takeaways)
- Small public exponents (like
e = 3) with raw RSA (no padding) can leak plaintexts if the plaintext is small enough. - The attack exploits integer arithmetic properties, not a secret-key leak — it’s a mathematical vulnerability of the parameter choice/protocol usage.
- Always use modern padding and recommended parameter sizes: large
e(standard: 65537) and secure padding to prevent this class of attack.
🧾 Short explanations for commands / techniques used
gmpy2.iroot(x, e): computes the integer e-th root ofx. Returns(root, is_exact)whereis_exactisTrueifroot**e == x.Crypto.Util.number.long_to_bytes(n): converts a big integernto its byte-string representation.c + i * Nloop trick: tests whether the unknown exact powerm^ediffers fromcby a multiple ofN; if so,m^e = c + k*N, and checking if that is a perfect power revealsm.- Low Public-Exponent Attack: using small
e(like 3) without padding can allow recovery of plaintext by taking integer roots whenm^e < N, or by finding akto makec + kNa perfect power. - Brute-forcing small
k: practical because oftenkis small (or zero) whenmis small relative toN.