Elgamal signature process

The Elgamal signature method is a method for digital signatures that is based on the mathematical problem of the discrete logarithm . It is to be distinguished from the Elgamal encryption method , whereby both methods were published in 1984 by Taher Elgamal in the same article.

A variant of this process was later standardized as the Digital Signature Algorithm and was widely used. The original method, on the other hand, is rarely used due to the relatively high computational effort and the large signatures (especially compared to DSA). For example, the ElGamal signature procedure was never part of SSL or TLS and was not implemented by OpenSSL or GnuTLS (DSA, however, was).

preparation

As with all methods with a discrete logarithm, one works 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 remainder class field modulo a prime number . However, it is just as possible to implement the method on the basis of another finite group. In particular, an elliptic curve can be used for this purpose . ${\displaystyle q}$ ${\displaystyle \mathbb {Z} _{p}^{*}}$ ${\displaystyle p}$

In practice this means choosing a prime q such that p = 2q + 1 is also a prime (by randomly choosing q and testing p, repeat until one is found). Then all elements (except 1 and −1) of either the entire group (of order ), or the subgroup of order q , and one chooses one as g , which creates the subgroup (multiplicative), usually 2 or 3. ${\displaystyle \mathbb {Z} _{p}^{*}}$ ${\displaystyle 2q=p-1}$

This selection of p , q and g can be made jointly for all participants. The size of q determines the security of the procedure. In addition, a collision-resistant hash function H must be fixed.

Key generation

To generate a key pair, a participant dials in (uniformly distributed at random) and calculates from it using modular exponentiation . A (or the triple (p, g, A) ) can then be made known as the subscriber's public key, while a is kept secret as the private key. ${\displaystyle a\in \{2,\ldots ,p-2\}}$ ${\displaystyle A=g^{a}\,{\bmod {\,}}p}$

Such a key pair can also be used for encryption with the Elgamal encryption method.

Sign a message

To send a message m to sign, to be executed by the undersigned following steps:

• A random number k is determined so that and (so that exists and can be calculated using the extended Euclidean algorithm ). ${\displaystyle 0<k<p-1}$ ${\displaystyle \operatorname {ggT} (k,p-1)=1}$ ${\displaystyle k^{-1}{\bmod {(}}p-1)}$
• One calculates . ${\displaystyle r\,\equiv \,g^{k}{\pmod {p}}}$
• One calculates ${\displaystyle s\,\equiv \,(H(m)-a\cdot r)k^{-1}{\pmod {p-1}}}$
• If so, the steps are repeated. ${\displaystyle s=0}$

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 is verified by checking the following conditions:

• ${\displaystyle 0<r<p}$and . ${\displaystyle 0<s<p-1}$
• ${\displaystyle g^{H(m)}\,\equiv \,A^{r}r^{s}{\pmod {p}}.}$

The recipient of the message accepts the signature if these conditions are met. Otherwise he will reject her.

Individual evidence

1. ↑ T. ElGamal: A public key cryptosystem and a signature scheme based on discrete logarithms Archived from the original on March 5, 2012. In: IEEE Trans inf Theo . 31, No. 4, 1985, pp. 469-472. , previously published in Proceedings of CRYPTO '84 .
2. ^ Neal Koblitz : Elliptic curve cryptosystems , p. 205.