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?
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
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.
-
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, 2021 at 9:59