# Attack RSA with very big module ($n$) and very small $e$ (7)

As an exercise I'm given an RSA to attack. I have the module ($$n$$), the public exponent ($$e$$) and a single ciphertext ($$c$$).

For this particular case, $$n$$ is VERY big (5 thousand digits more or less), but the public exponent is small ($$e=7$$).

I know that, as $$m \ll n$$, this can cause no use of the module operation ($$m^7\bmod n = m^7$$). I tried reversing it doing $$c^{1/7}=m^{7\cdot1/7}=m$$ but this is not working. It might be that $$m^7 \bmod n \neq m^7$$. What can I do in this case?

What am I missing/misunderstanding?

EDIT

I was given an hint: "Big $$n$$ is useless with small $$e$$". I assume it has more to do with the exponent rather then $$n$$.

• I think you mean 16 Kib (kibibits)? 16K decimal digits would indeed be very large. Commented Apr 27, 2020 at 16:34
• Could (c+k*n) be a power of 7 for a small value of k? Commented Apr 27, 2020 at 16:36
• Changed the question. It's a 4931 decimal digits $n$ Commented Apr 27, 2020 at 16:53
• It doesn't seem like there is any small k that makes that true Commented Apr 27, 2020 at 17:02
• Is this problem supposed to be easy (e.g. a Capture-the-Flag challenge)? Unless the problem was designed with a specific weakness in mind, it's likely to be infeasible to solve. Commented Apr 27, 2020 at 17:47