Suppose we have an RSA encryption oracle $E(m)$ which basically just calculates $m^e \mod n$ for a given message $m$. Here $e=65537$ is known but $n$ is not. Can we determine the value of $n$ without trying all values below $n$, assuming $2^{1023}\leq n <2^{1024}$?

I thought of using $E(-1)$ but sadly only positive messages are allowed. Another idea that i had was to just use $E(2)$ and if $e$ was small it would wrap the modulus only a few times and we would be able to determine $n$. Sadly $2^{65537}$ is many times bigger than $n$ so it doesn't work either.

  • $\begingroup$ In the present question $e$ is known and $m$ can be chosen. It can only make finding $n$ easier than in said similar question. $\endgroup$ – fgrieu Dec 18 '18 at 18:52
  • $\begingroup$ Its for a private CTF challenge $\endgroup$ – Jannes Braet Dec 18 '18 at 19:09

We have $E(x) = x^{65537} - k \cdot n$, for some integer $k$ (which will be different for different values of $x$), and the unknown modulus $n$, and hence $x^{65537} - E(x)$ will always be a multiple of $n$.

So, compute:

$$\gcd( 2^{65537} - E(2), 3^{65537} - E(3) )$$

That will be $n$ multiplied by some integer which is likely to be small...

As similar method (that doesn't involve computing on such large integers, and even works even if you don't know $e$) is to compute:

$$\gcd( E(2)^2 - E(4), E(3)^2 - E(9) )$$

How this works should be fairly obvious...

| improve this answer | |

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.