RSA find public exponent 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?


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