Does knowing that the exponent is in a certain range help solving discrete log?4b6p65naut U
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<i<k$
$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?
-
2$\\begingroup$ I think this allows an attack in time $\\sqrt{k-j}$ but I don't know for sure... $\\endgroup$ – SEJPM♦ 7 hours ago
1 Answer
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.
- Let $h:=c\\cdot g^{-j-1}$, which equals $g^{i-j-1}$.
- Pick some integer $m\\geq\\sqrt{k-j-1}$.
- Initialize an empty lookup table $T$.
- For all $0\\leq a<m$, compute $g^{ma}$ and store $T[g^{ma}]:=a$.
- For all $0\\leq b<m$, 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<m$ 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<m$ and satisfy $-b+i-j-1=ma$, hence will be found by the algorithm.
-
$\\begingroup$ 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. $\\endgroup$ – J. Doe 2 hours ago