0
$\begingroup$

For $p$ a 1024-bit prime, we have a 1021-bit element $g \in \mathbb{Z}_p^*$, where the order of $g$ is much smaller than the order of $\mathbb{Z}_p^*$. How does this small-order $g$ affect the security of the signature?

$\endgroup$
1
$\begingroup$

The size of $p$ only affects the cost of the group operations (which is small even for 1024-bit number). Many known attacks against Dlog such as baby-step-giant-step are in $\mathcal{O}(\sqrt{o(g)})$ group operations, with $o(g)$, the order of $g$. That's why it's important that $g$ has the same order of $\mathbb{Z}^{*}_p$ (then it should be a generator). Else, if $o(g)$ is small, you easily break Dlog, and thus ElGamal.

$\endgroup$
1
  • 1
    $\begingroup$ Addition: It's not indispensible that $g$ has the same order as $\mathbb Z_p^*$ [that $g$ is a generator], or even half that [which is customary for prime order]; and that's not the practice in the original Schnorr signature, or in the later DSA. It's enough that the order of $g$ has at least twice as many bits as the targeted security level [this bound follows from the answer's $\mathcal{O}(\sqrt{\operatorname{ord}(g)}\,)$ ], and is prime. So 256-bit prime order of $g$ is ample for 1024-bit $p$ [which is quite on the low side, 2048-bit would be the modern baseline]. $\endgroup$
    – fgrieu
    Nov 24 at 9:59

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.