Determine RSA modulus from encryption oracle

Question

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.

Answer 1

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