Information Security - Digital Signature ElGamal and DSS - Algorithm and Examples

ElGamal Digital Signature Protocol

The El Gamal digital signature protocol was defined in 1985 ([4]). It is not a deterministic protocol, which means that for given message we can have more valid signatures. The verification function will accept as valid all these signatures. In the following, we utilize Alice, as the sender and Bob, as the receiver. Alice has the pair of keys (XA, YA) and Bob has the pair of keys (XB, YB).

Definition

We consider the public parameters are: p, g, YA. They are defined as follows.

We take p a big prime number for which the discrete logarithm problem is difficult in Zp.

We consider g ∈ Z∗p with order p-1 modulo p, being a prime factor for p-1.

Alice has the pair of keys (XA, YA). XA is the private key and YA is the public key.

XA ∈ Z∗p with XA does not divide p-1.

Alice’s public key is calculated function of Alice’s private key, YA = g^XA mod p

We provide here 4 examples for ElGamal digital signature.

Example 1

We consider p = 467; g = 2; XA = 127.

Now YA is calculated: YA = g^XA mod p = 2^127 mod 467 = 132.

So the Alice’s pair of keys is (127, 132).

We take message m= 100 and x = 213 for the signature of this message.

Here we notice that (213, 466)= 1

We calculate 213^−1 mod 466 = 431

Having these parameters, we can start to calculate the signature of Alice on the message m, which is represented by the pair (r, s).

r= g^x mod p = 2^213 mod 467 = 29

s= [m−(XA∗r)] / x mod p = (100-127*29) * 431 mod 466 = 51

Verification step:

g^m = Ya^r * r^s mod p

132^29 * 29^51 ≡ 189 (mod 467)

2^100 ≡ 189 (mod 467)

The verification confirms that the signature is valid.

Example 4

DSS - Digital Signature Standard

The Digital Signature Algorithm (DSA) is a Federal Information Processing Standard (FIPS) for digital signatures. It was proposed by the National Institute of Standards and Technology (NIST) in August 1991 for use in their Digital Signature Standard (DSS). DSA has been accepted and included in DSS in December 1994, supporting one modification: the message m has been replaced by the mark SHA1(m). Digital Signature Standard - DSS - is a variant of ElGamal digital signature protocol having the property that the length of the signature is reduced. The main difference between DSA and ElGamal digital signature is that DSA provides a digital signature of 320 bits on a message of 160 bits, using Zp where p has 512 bits, offering operations in a field with 2^160 elements.