# Determine RSA modulus from encryption oracle

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.

• In the present question $e$ is known and $m$ can be chosen. It can only make finding $n$ easier than in said similar question. – fgrieu Dec 18 '18 at 18:52
• Its for a private CTF challenge – 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...