Suppose I have an encryption oracle which can encrypt $m^e \mod n$ for any $m$. I know $n$ and I know $\varphi(n)$. However the public exponent $e$ is secret. Is it possible to figure out it's value when $e$ is not bruteforce-able?
Is it possible to figure out it's value when $e$ is not bruteforce-able?
First note that knowing you can easily factor $n$ given that you also know $\varphi(n)$ (2-prime case). Next note that $\mathbb Z_n^*\cong\mathbb Z_p^*\times \mathbb Z_q^*$ (by the CRT), this means that doing component-wise operations on the pairs from the latter groups is a different way of writing an operation in the former group. Finally note that the bit-length of $p,q$ is about half of that of $n$ (usually).
Now that the preparation is through, the first thing to realize is that the given scenario is a standard discrete-logarithm problem with a composite modulus. Also note that the power of being able to choose the base shouldn't make the attacker stronger. Next thanks to the congruence and us knowing $p,q$ we can just map the problem to two smaller problems, finding $e$ given $x\mapsto x^e\bmod p$ and the same for $\bmod q$. Assuming the factors are reasonably small, a standard GNFS attack may work out, but with a standard RSA modulus of two primes of similar length resulting in a 2048-bit modulus this doesn't work.
Otherwise, this is a hard problem because it essentially constitutes a key-recovery attack on the Pohlig-Hellman cipher in a chosen-plaintext scenario.
Assuming you don’t know the private exponent as well; you have to treat $e$ as a random variable, as it can potentially be any number from a very large domain.
Please note that: If the implementation of RSA you’re using is a standard implementation; your encryption exponent is a fixed value, you can try the standard public exponents.