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

Question

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?

Answer 1

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.