# Solving a discrete log with BsGs

If we consider a group G with modulus p, order q with $$p=2*q+1$$, and generator $$g=2$$ ($$p$$, $$q$$ huge prime numbers), is there a way to solve the discrete log problem $$g^x = y$$ for a y given, using the baby steps giant step algorithm AND the fact that $$x$$ is of the form: $$x = \sum_{i=0}^{10} \alpha_i * 2^i$$ $$:\alpha_i \in \mathbb{N}$$ without requiring to store all small steps in a hashtable, which is impossible with the magnitude of the numbers $$p$$ and $$q$$.

edit: The $$\alpha_i$$ values are unknown to the attacker.

edit 2: $$\alpha_i \in [0,\infty]$$

• Does the attacker know the $\alpha_i$ values? Oct 25, 2021 at 15:10
• Does actually $\alpha_i \in \{0,1\}$? Does $\mathbb{N} = \mathbb{Z}^+$ or $\mathbb{N} = \mathbb{Z}^+ \cup \{0\}$, there is no common agreement on this. Oct 25, 2021 at 21:50

is there a way to solve the discrete log problem $$g^x=y$$ for a $$y$$ given, using the baby steps giant step algorithm

No practical way if $$p, q$$ are large.

Even if $$x$$ is known to be in the form $$x = \sum_{i=0}^{10} \alpha_i * 2^i$$ $$:\alpha_i \in \mathbb{N}$$ ?

Every potential $$x$$ can be expressed in that form; consider $$\alpha_1 = \alpha_2 = ... = \alpha_{10} = 0$$ and $$\alpha_{0} = x$$. Hence, knowing that $$x$$ is expressable in that form does not provide any additional information; BsGs is usable only if the modulus is small enough (and the question assumes it is not)

• No $x< 2048$. The problem is much easier, you can do Bruteforce attack (but without babystep/giant step). Oct 25, 2021 at 16:04
• @levgeni: if we're talking about values that can be expressed in that form, we have $x \ge 2047$ (and that's with the convention that $0 \not\in \mathbb{N}$; otherwise, all $x$ values can be expressed in that form). Oct 25, 2021 at 16:36
• @levgeni: and, if $x < 2048$ and $p$ is cryptographically sized (i.e. at least 2048 bits), the discrete log can be extracted directly from the value $2^x$; that has bit $x$ as 1, and all the other bits as 0... Oct 25, 2021 at 16:38
• @poncho I think levgeni argues that even if $x>2046$, it doesn't imply that $x$ is not trivially small. The large is clear, however the small need a metric. Oct 25, 2021 at 20:40
• @kelalaka: I don't understand your argument; if we interpret the question of "is DLog solvable if we assume the exponent is random, conditioned by being expressable in the given form?" With that understanding, my answer is correct - how do you interpret the question? Oct 25, 2021 at 21:33