1
$\begingroup$

I'm trying to do learn a bit about RSA by doing CTF's and now I am doing one problem probably more than 7 hours so I would really appreciate a hint here from an expert.

I have an encrypted message $c$, the modulus $n$ and the public exponent $e$ (variable names are by the definition of the wikipedia article). The exponent $e$ is of the same length (308 digits in base10) as the message $c$ and the modulus $n$.

The first thing I thought was that the exponent $e$ so large that no computer would be able to calculate $m^e$ if m is bigger than $1$. So I thought that the message $c$ must be the same as the non-encrypted message $m$. Converting $c$ to base16 and then to ASCII just gave me a bunch of non-sense.

After searching through the internet a lot I found a statement by a user that if the public exponent $e$ is very large it is likely that the private exponent is very small. So assuming the calculation of $m^e$ is possible I tried to decrypt the message with common small exponents $d (3,17)$ but this also did not work.

Since I am really stuck here, I would be very glad for a hint.

|improve this question
$\endgroup$
  • 3
    $\begingroup$ If the private exponent $d$ is small, Wiener's attack will work. $\endgroup$ – Squeamish Ossifrage Apr 9 '19 at 4:57
  • 1
    $\begingroup$ (Side note: A 308-digit exponent is a ~1024-bit exponent. It only takes 1024-2048 multiplications modulo $n$ to compute $m^e \bmod n$—this is entirely feasible.) $\endgroup$ – Squeamish Ossifrage Apr 9 '19 at 5:00
  • 1
    $\begingroup$ Read on Modular Exponentiation to learn how computing $m^e\bmod n$ with large $e$ is feasible (and routinely done). With what you state, it is hard to tell how the CTF can be solved. Ideas: Find a weakness in how $(n,e,d)$ was drawn, allowing to find $d$ (perhaps, by trying small odd values of $d$ as you attempted and checking a guess of $d$ by checking that ${(2^e)}^d\bmod n=2$; or Wiener's attack), or/and factor $n$. Or guess $m$ and verify the guess by checking $m^e\bmod n=c$. None of this would work for serious use of RSA. $\endgroup$ – fgrieu Apr 9 '19 at 10:58
  • 3
    $\begingroup$ Note that, while $d$ and $e$ cannot both be small (i.e. $< \sqrt{\lambda(n)}$), it's perfectly possible for both of them to be large. $\endgroup$ – Ilmari Karonen Apr 9 '19 at 12:10
  • 1
    $\begingroup$ I'd also test a few more small primes, especially the fifth prime of Fermat, 65537. It may be that the public and private exponent are switched (encryption with a private key instead of a public key). The fifth prime of Fermat (also called F4) is a default for many cryptographic libraries. $\endgroup$ – Maarten Bodewes♦ Apr 9 '19 at 19:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.