0
$\begingroup$

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] $

Improve this question
$\endgroup$
2
  • $\begingroup$ Does the attacker know the $\alpha_i$ values? $\endgroup$
    – poncho
    Oct 25, 2021 at 15:10
  • 1
    $\begingroup$ 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. $\endgroup$
    – kelalaka
    Oct 25, 2021 at 21:50

1 Answer 1

Reset to default
0
$\begingroup$

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)

Improve this answer
$\endgroup$
11
  • $\begingroup$ No $x< 2048$. The problem is much easier, you can do Bruteforce attack (but without babystep/giant step). $\endgroup$
    – Ievgeni
    Oct 25, 2021 at 16:04
  • $\begingroup$ @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). $\endgroup$
    – poncho
    Oct 25, 2021 at 16:36
  • $\begingroup$ @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... $\endgroup$
    – poncho
    Oct 25, 2021 at 16:38
  • $\begingroup$ @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. $\endgroup$
    – kelalaka
    Oct 25, 2021 at 20:40
  • $\begingroup$ @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? $\endgroup$
    – poncho
    Oct 25, 2021 at 21:33

Your Answer

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

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