ElGamal signature scheme

The ElGamal signature scheme is a method for digital signatures, which is based on the mathematical problem of the discrete logarithm. It is distinguished from the ElGamal encryption method, both methods have been published by Taher Elgamal in the same article in 1984.

A variant of this method was later standardized as Digital Signature Algorithm.

Preparation

As with all processes with discrete logarithm working in an abelian group G with a generator g in the original version of the method, this group is a subgroup of large prime order of the multiplicative group of the residue class field modulo a prime number.

In practice, this means that one chooses a prime number q such that p = 2q 1 is also a prime number (using a random choice of q and testing of p, repeat until one is found ). Then produce all of the elements (except for 1 and -1 ) of the whole group, either ( order ), or the subgroup of order q, and g are selected as one which generates the sub-group ( multiplicative), usually 2 or 3

This choice of p, q and g can be taken together for all participants. The size of q determines the safety of the procedure. Furthermore, a collision- resistant hash function H has to be fixed.

Key generation

To generate a key pair selects a participant a ( uniformly distributed random), and calculates by means of modular exponentiation. A (or the triple ( p, g, A) can then be announced as the public key of the subscriber, while a is kept secret as a private key.

Such a pair of keys can also be used for the encryption using the ElGamal encryption scheme.

Signing a message

To sign a message m, the signer executes the following steps:

  • Determine a random number k such that and (so that exists and can be calculated using the extended Euclidean algorithm ).
  • Man charged.
  • We calculate
  • If so, the steps are repeated.

The pair ( r, s) is the digital signature of m. The steps must be repeated by the signer for each signature.

Verifying a signed message

A signature ( r, s ) of a message m, it is verified by the following conditions are verified:

  • And.

The message recipient accepts the signature if these conditions are met. Otherwise, it rejects it.

303186
de