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

$\endgroup$
6
  • 4
    $\begingroup$ If the private exponent $d$ is small, Wiener's attack will work. $\endgroup$ Apr 9, 2019 at 4:57
  • 2
    $\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$ Apr 9, 2019 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, 2019 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$ Apr 9, 2019 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, 2019 at 19:35

0

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.