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?


1 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.

  • $\begingroup$ Thank you! but how do I calculate the number of valid signatures? or K is already the number of valid signatures? $\endgroup$
    – Andre
    Aug 6, 2021 at 21:24
  • 1
    $\begingroup$ 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. $\endgroup$
    – bk2204
    Aug 7, 2021 at 1:55
  • $\begingroup$ Thank you very much ! $\endgroup$
    – Andre
    Aug 7, 2021 at 12:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.