# RSA encryption extremely large public exponent

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.

• If the private exponent $d$ is small, Wiener's attack will work. – Squeamish Ossifrage Apr 9 '19 at 4:57
• (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.) – Squeamish Ossifrage Apr 9 '19 at 5:00
• 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. – fgrieu Apr 9 '19 at 10:58
• 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. – Ilmari Karonen Apr 9 '19 at 12:10
• 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. – Maarten Bodewes Apr 9 '19 at 19:35