ElGamal signature scheme

The ElGamal Signature scheme is a digital signature scheme which is based on the

Security

A third party can forge signatures either by finding the signer's secret key x or by finding collisions in the hash function H(m) equiv H(M) pmod{p-1}. Both problems are believed to be difficult.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The signer must be careful to choose a different k uniformly at random for each signature and make sure that k or even partial information about k is not leaked. Otherwise a third party may be able to deduce the secret key x with less difficulty.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In particular, if two messages are sent using the same value of k then a third party can compute x.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~