# RSA: finding e given n, m and c

So I'm not sure if this is possible but assume I have

$$c \equiv m^e \pmod n$$

I have $c$, $m$ and $n$ but no $e$, which in my case I a value that can be up to 15 digits. Is there a way to do this?

• That looks like a standard discrete-logarithm problem with the twist of the modulus being composite and thus the ring being of unknown order. 15 (decimal) digits roughly corresponds to 50 bits which should be doable I think (especially if you can adapt one of the $\mathcal O(\sqrt q)$ methods). Jul 9, 2018 at 13:53
• OK and that despite that c, m and n are all 300 digits? Does the fact that they are all roughly the same length help? Jul 9, 2018 at 14:16
• I want to add that usually $e=65537$ is a fixed value in practice. People intentionally make $e$ to be such a value and change $d$ accordingly. Jul 10, 2018 at 4:25

In general, if you have an algorithm $A$ which with high probability has $$A(n, m, m^e \bmod n) = e$$ under uniform random $e$ and $m$ and some distribution on $n$, you can use this to compute $e^{\mathit{th}}$ roots modulo $n = pq$ for any $e$, and even factor $n$, as follows:

1. Pick $c$ uniformly at random.
2. Compute $d = A(n, c^e \bmod n, c)$.

With high probability, $(c^e \bmod n)^d \bmod n = c$, so that $c^{e d} \equiv c \pmod n$ and hence $e d \equiv 1 \bmod{\lambda(n)}$. Recovering $p$ and $q$ from $n = pq$ once you have $d$ is left as an exercise for the reader. (Hint: There are about eighty-six gajillion questions on this site about how to do it.)

This shows that solving the discrete logarithm problem in $\mathbb Z/n\mathbb Z$ for an arbitrary exponent $e$ can't be much easier than the solving RSA problem or even factoring $n$. Your best bet is to factor $n$, compute the discrete logarithms modulo the factors separately, and combine the results with the Chinese remainder theorem.

However, there is a better strategy if $e$ is known to lie in a small interval, say $\{2,3,\dots,e_{\mathrm{max}}\}$: Pollard's kangaroo algorithm. Normally it is applied in groups like the multiplicative group of a finite field or an elliptic curve group, but there's no reason it can't be applied to the multiplicative group of an RSA quasi-field.

Fix $n$, $m$, and $e_{\mathrm{max}}$. Pick a random function $f\colon (\mathbb Z/n\mathbb Z)^\times \to S$ where $S$ is some finite set of $|S| \ll \sqrt{e_{\mathrm{max}}}$ integers. Pre-compute \begin{align*} x_0 &= m^{e_{\mathrm{max}}}, \\ x_{i+1} &= x_i m^{f(x_i)} \bmod n, \quad 0 < i \leq N \end{align*} for some bound $N$ on the amount of precomputation. Note that $$x_N \equiv x_0 m^\delta \equiv m^{e_{\mathrm{max}} + \delta} \pmod n$$ where $$\delta = f(x_0) + f(x_1) + \cdots + f(x_{N-1}).$$ Store $x_N$ and $\delta$.

Next, given $c$, compute \begin{align*} x'_0 &= c, & \delta'_0 &= 0, \\ x'_{i+1} &= x'_i m^{f(x'_i)} \bmod n, & \delta'_{i+1} &= \delta'_i + f(x'_i). \end{align*} Note that $x'_i \equiv c m^{\delta'_i} \equiv m^{e + \delta'_i} \pmod n$. If we find $x'_i = x_N$ for some $i$, then we know $m^{e_{\mathrm{max}} + \delta} \equiv m^{e + \delta'_i} \pmod n$, so $e \equiv e_{\mathrm{max}} + \delta - \delta'_i \pmod{\phi(n)}$. However, if we find $\delta'_i > e_{\mathrm{max}} + \delta$, then the method has failed and must start over with, e.g., a larger $N$ or a different $f$.

To attain success probability $p$, one should choose $S$ to have mean about $\sqrt{e_{\mathrm{max}}/4\theta}$ and choose $N \approx \sqrt{e_{\mathrm{max}} \theta/2}$ where $\theta = -\log(1 - p)$. The expected cost for an attack with fixed $\theta$ is approximately $2 \sqrt{\theta e_{\mathrm{max}}}$. (Details of the analysis are in the paper.) For 300-digit $n$ and 15-digit $e$, i.e. ~630-bit $n$ and ~32-bit $e$, this is almost certainly cheaper than factoring $n$ and computing discrete logs modulo its factors with Pollard's $\rho$ or even index calculus.

• While this is true for uniform e, what about small values of e like the mentioned very short e in the question? Jul 10, 2018 at 12:16
• If $e$ is known to be very short in the question, then it seems to me that finding $e$ by brute force should be pretty easy, and it is a moot point to study reductions with other problems, no? Jul 10, 2018 at 16:05
• What I found interesting about this question was the fact that the exponent is large enough to not be linearly brute-forceable, but small enough to be in reach of $\mathcal O(\sqrt{|e|})$ methods which at least to me makes it different from the uniform choice of $e$ which is required for the reduction to work and interesting enough on its own. Jul 10, 2018 at 16:11

As SEJPM suggested, it's quite practical for the range of $e$ in question.

Here's an easier way than the Kangaroo method:

• Set $\lambda \approx. 10^{7.5}$; the exact value isn't important, but the below works most efficiently if the approximation is close.

• Compute $A_i = c m^i \bmod n$ for $i = 0 .. \lambda - 1$ using about $\lambda$ modular multiplies

• Store all the $A_i$ values in a fast lookup table (e.g. a hash table)

• Compute $z = m^\lambda \bmod n$

• For $j = 1 .. 10^{15} /\lambda$ compute $B_j = z^j \bmod n$, and check if the value $B_j$ appears anywhere in the $A_i$ list.

If we have $B_j = A_i$, then we know that $e = \lambda j - i$

Assuming $e$ is in the range $0 .. 10^{15}$, this will always find it, using about $2 \lambda$ modular multiplies; quite doable on a standard PC.

• That is actually great, thanks a lot! it's a nice algo and also easy to understand! Jul 12, 2018 at 7:24
• @S.L.: this is known as 'big-step/little-step' (or baby-step/giant-step), modified to avoid the need to compute inverses (computing multiplicative inverses modulo n is certainly possible, but is actually harder to explain than the above algorithm). This algorithm does use a large table; however given the possible range of $e$,, the table size is quite practical. Jul 12, 2018 at 14:17