Score:0

How many valid signatures can the same message have using ElGamal?

pt flag

I know that messages in ElGamal are not deterministic, so a message can have more than one valid signature. But is the number of valid subscriptions infinite?

Score:1
fr flag

It is not infinite. There are two factors that control the potential number of signatures.

First, when using ElGamal signatures, you practically need some sort of padding scheme. Because it is a discrete logarithm algorithm, the key size needs to be at least 3072 bits for appropriate security, and unless you're using an XOF like SHAKE256, you'll need to securely pad the hash to an appropriate size. If your padding scheme is deterministic, such as PKCS #1 1.5, then this doesn't introduce any additional possible signatures. However, if you were using a probabilistic signature scheme, then the salt used in the signature scheme would add additional possibilities.

Second, when signing, you will also have to pick $ k $, which is supposed to be picked randomly from $ \{ 2 … p-2 \} $ and be relatively prime to $ p - 1 $. The size of that set determines the number of valid signatures for a given message. There are several different secure methods for generating $ p $, and the ease of computing the size of this set depends on which is used.

However, as a practical matter, it is often prudent to use a secure deterministic method for picking $ k $ (such as RFC 6979, which is trivially extended to ElGamal) because that means that a failure of a CSPRNG does not result in leaking the private key (since no CSPRNG is used when signing). In such a case, the signature can very well be deterministic, although this cannot be verified by the recipient.

Andre avatar
pt flag
Thank you! but how do I calculate the number of valid signatures? or K is already the number of valid signatures?
bk2204 avatar
fr flag
If you're using a deterministic padding scheme, the number of valid signatures is the number of valid values of $ k $. Otherwise, it would be that times the number of salt possibilities in the signature scheme.
Andre avatar
pt flag
Thank you very much !
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.