Join Log in
Score:0
avatar Crypto

Security of ElGamal signature scheme with generator of small order

cn flag
amycandyit

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?

51
0 + 0
Score:1
Ievgeni avatar Crypto
cn flag
Ievgeni

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.

0 + 0
fgrieu avatar
ng flag
fgrieu
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\].
1
Reply
ธงชาติไทย
Elon Musk
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.