3
$\begingroup$

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?

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

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<m$, compute $g^{ma}$ and store $T[g^{ma}]:=a$.
  5. 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.

$\endgroup$
  • $\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 Aug 17 at 22:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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