# Does knowing that the exponent is in a certain range help solving discrete log?

given:
$$c=g^i \bmod P$$
$$g$$ generator for group with group size $$\varphi(P)$$
$$g,P,\varphi(P)$$,c is known by the attacker
He wants to know $$i$$.

Now the attacker also knows $$j,k$$ with $$j
$$k-j$$ is too big to compute them all but it is much smaller than group size.

Does this knowledge about $$i$$ help the attacker?

• I think this allows an attack in time $\sqrt{k-j}$ but I don't know for sure... – SEJPM Aug 17 at 17:32

The basic baby-step-giant-step algorithm can be tweaked to make use of this information. The following algorithm takes $$\Theta(\!\sqrt{k-j})$$ group operations.

1. Let $$h:=c\cdot g^{-j-1}$$, which equals $$g^{i-j-1}$$.
2. Pick some integer $$m\geq\sqrt{k-j-1}$$.
3. Initialize an empty lookup table $$T$$.
4. For all $$0\leq a, compute $$g^{ma}$$ and store $$T[g^{ma}]:=a$$.
5. For all $$0\leq b, compute $$g^{-b}h$$ and check if $$g^{-b}h$$ is in $$T$$. When a match is found, return $$j+1+m\cdot T[g^{-b}h]+b$$.

Note that this is almost exactly the standard BSGS algorithm, except for replacing the unknown exponent $$i$$ by $$i-j-1$$ in step 1 and adjusting the output accordingly in step 5.

Correctness: If the algorithm returns something, it must be of the form $$r=j+1+m\alpha+\beta$$ with $$0\leq\alpha,\beta and $$T[g^{-\beta}h]=T[g^{m\alpha}]$$. This implies $$g^r = g^{j+1+m\alpha+\beta} = g^{j+1-\beta+(i-j-1)+\beta} = g^i \text,$$ hence $$r=i$$ (modulo the order of $$g$$).

Completeness: Let $$b:=(i-j-1)\bmod m$$ and $$a:=(i-j-1-b)/m$$. These values are in the range $$0\leq a,b and satisfy $$-b+i-j-1=ma$$, hence will be found by the algorithm.

• thanks for answer. I checked b-s-g-s before and thought it won't work for big numbers because you need a lot of storage in 4. However bigger number almost always work. With the knowledge about the index it will be much faster. – J. Doe Aug 17 at 22:52