- ElGamal signature scheme
The ElGamal signature scheme is a
digital signaturescheme which is based on the difficulty of computing discrete logarithms. It was described by Taher ElGamalin 1984(see T. ElGamal, A public key cryptosystem and a signature scheme based on discrete logarithms, IEEE Trans inf Theo, 31:469–472, 1985).
The ElGamal signature algorithm described in this article is rarely used in practice. A variant developed at
NSAand known as the Digital Signature Algorithmis much more widely used. There are several other variants (see K. Nyberg and R. A. Rueppel, Message recovery for signature schemes based on the discrete logarithm problem, Designs, Codes and Cryptography, 7:61–81, 1996). The ElGamal signature scheme must not be confused with ElGamal encryptionwhich was also invented by Taher ElGamal.
The ElGamal signature scheme allows that a verifier can confirm the authenticity of a message "m" sent by the signer sent to him over an insecure channel.
* Let "H" be a collision-resistant hash function.
* Let "p" be a large prime such that computing
discrete logarithms modulo "p" is difficult.
* Let "g" be a randomly chosen generator of the multiplicative group of integers modulo "p" .
These system parameters may be shared between users.
* Choose randomly a secret key "x" with 1 < "x" < "p" − 1.
* Compute "y" = "g" "x" mod "p".
* The public key is ("p", "g", "y").
* The secret key is "x".These steps are performed once by the signer.
To sign a message "m" the signer performs the following steps.
* Choose a random "k" such that 0 < "k" < "p" − 1 and gcd("k", "p" − 1) = 1.
* Compute .
* Compute .
* If start over again.Then the pair ("r","s") is the digital signature of "m".The signer repeats these steps for every signature.
A signature ("r","s") of a message "m" is verified as follows.
Wikimedia Foundation. 2010.