0
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 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). $\endgroup$
    – SEJPM
    Jul 9, 2018 at 13:53
  • $\begingroup$ 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? $\endgroup$
    – S. L.
    Jul 9, 2018 at 14:16
  • $\begingroup$ 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. $\endgroup$ Jul 10, 2018 at 4:25

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ While this is true for uniform e, what about small values of e like the mentioned very short e in the question? $\endgroup$
    – SEJPM
    Jul 10, 2018 at 12:16
  • $\begingroup$ 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? $\endgroup$ Jul 10, 2018 at 16:05
  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Jul 10, 2018 at 16:11
2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ That is actually great, thanks a lot! it's a nice algo and also easy to understand! $\endgroup$
    – S. L.
    Jul 12, 2018 at 7:24
  • 1
    $\begingroup$ @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. $\endgroup$
    – poncho
    Jul 12, 2018 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.