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?


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$.

  • $\begingroup$ I think you mean 16 Kib (kibibits)? 16K decimal digits would indeed be very large. $\endgroup$
    – Maarten Bodewes
    Commented Apr 27, 2020 at 16:34
  • 1
    $\begingroup$ Could (c+k*n) be a power of 7 for a small value of k? $\endgroup$ Commented Apr 27, 2020 at 16:36
  • $\begingroup$ Changed the question. It's a 4931 decimal digits $n$ $\endgroup$ Commented Apr 27, 2020 at 16:53
  • $\begingroup$ It doesn't seem like there is any small k that makes that true $\endgroup$ Commented Apr 27, 2020 at 17:02
  • $\begingroup$ 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. $\endgroup$
    – poncho
    Commented Apr 27, 2020 at 17:47


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.