# 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?

## 2 Answers

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.

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.

• The note is somewhat unnecessary as the fixed values would be easy to find through brute force, and the question states that brute force is not feasible. – Maarten Bodewes Apr 20 '19 at 16:33