# Security of ElGamal signature scheme with generator of small order

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?

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.
• 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].