ElGamal signature scheme

The ElGamal signature scheme is a digital signature scheme whose security rests on the difficulty of computing discrete logarithms. Taher Elgamal described it in 1985. A signer holds a private key and a public key derived from it by modular exponentiation. To sign a message, the signer hashes it, picks a fresh random number relatively prime to the group order minus one, and computes two values that together form the signature. A verifier checks the signature with the public key using one modular exponentiation identity. The scheme gives message authentication, integrity and non-repudiation. The same random number must never be reused, because two signatures made with one value reveal the private key. The original paper omitted the hash function, which allowed existential forgery. The scheme is rarely used directly, and the Digital Signature Algorithm, a variant developed at the NSA, is far more widely used. It must not be confused with ElGamal encryption.