RSA: Recover e given factorization of N and plaintext/ciphertext pair Is there a way to recover the public exponent e (assume in this case it is in fact not public) used in an encryption if I know the following:


Factorization of N : p and q
one plaintext m and its encryption c = m^e mod N


Obviously I can just bruteforce if e is small, but is there a more elegant way? (or just assume e is too large to simply bruteforce)
If $e$ is a random number, then knowledge of the factorization allows us to reduce the recovery operation to:

$$(c \bmod p) = (m \bmod p)^{e \bmod p-1} \pmod p$$
$$(c \bmod q) = (m \bmod q)^{e \bmod q-1} \pmod q$$

Solving both these discrete log problems will give us enough information on $e$ to efficiently recover it.

Now, while solving these two subproblems is easier than factoring $N$, or recovering $e$ without knowing the factorization, it is still nontrivial.  If we assume that the RSA modulus was a 2048-bit key, then each of these subproblems is a 1024 bit discrete log problem; that's larger than any published result.

On the other hand, if we are allowed to assume that $e$ is small (but perhaps a bit larger than we can brute-force), there are more efficient methods than simply trying each possible $e$ value.  For example, using the Baby Step Giant Step algorithm, you can efficiently check all possible values $e &lt; 2^{61}$ with $2^{31}$ modular multiplications, and a few tens of Gigabytes of disk space.  You don't even need to know the factorization of $n$ (however, it would make it a bit more efficient, as that would allow you to compute everything modulo $p$)