Finding exponent $e$ in RSA given modulus and a plaintext/ciphertext pair

Question

Assuming $$c = m ^ e \bmod n$$ and given the values of $c$, $m$ and $n$ (32 bit integers),

How would one find the exponent $e$ (also 32 bit integer) ?

Answer 1

In this question we are given $c$, $m$ and $n$ (32 bit integers with $0\le c<n$), and asked to find the exponent $e$ (also 32 bit integer, odd and at least $3$) matching the equation of textbook RSA encryption: $c=m^e\bmod n$.

That's impossible with certainty unless $n$ is prime (which would not be RSA) and exactly 32-bit, because then the solution is never unique; either there is no solution, or several values of $e$ are possible. For some parameters (like $m=c=0$, $m=c=1$, or $m=c=n-1$), all odd values of $e$ work. If there's a solution, there is one below $\lambda(n)$ with $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ when $n=p\;q$ with $p$ and $q$ distinct primes; that's the Carmichael function, and is less than $2^{31}$ in an RSA context when $n$ is an at-most-32-bit composite; and then $e+\lambda(n)$ will be at-most-32-bit and also be a solution.

What we can find is the lowest odd value of $e$ at least $3$ such that $c=m^e\bmod n$ holds. The simplest method is perfectly adequate in the context if we can use a computer:

• $a\gets m\cdot m\bmod n$
• $e\gets 1$
• $b\gets m$; it holds that $b=m^e\bmod n$
• repeat until $e=2^{32}-1$
  • $e\gets e+2$
  • $b\gets a\cdot b\bmod n$; again it holds that $b=m^e\bmod n$
  • if $c=b$
    • output "One solution is" $e$ and stop
• output "There is no solution" and stop.

This requires $(e+1)/2$ modular multiplications if a solution is found, and in any case no more than $2^{31}$.

---

There are at least two independent speedups which would allows to reduce the work, or/and tackle larger parameters:

• There are better algorithms than exhaustive search to solve a Discrete Logarithm Problem, including baby-step/giant-step which reduces the work to $O(\sqrt n)$ modular multiplications; and Pollard's rho which is simpler and tends to be faster on average (but won't necessarily give the lowest $e$).
• If we can factor $n$ (and it is square- free as customary in RSA), then we can solve the equation $c\equiv m^{e_p}\pmod p$ for each prime factor $p$ of $n$, then combine the results into $e$ using the Chinese Remainder Theorem, noting that if $e\equiv e_p\pmod{p-1}$ for each prime $p$ dividing $n$, this $e$ will be a solution (there might be cases where we miss the lowest $e$).