The El Gamal and Digital Signature Algorithms

The El Gamal and Digital Signature Algorithms

Another public key algorithm was devised in 1984 by El Gamal [ELG85, ELG86]. While this algorithm is not widely used directly, it is of considerable importance in the U.S. Digital Signature Standard (DSS) [NIS92b, NIS94] of the National Institute of Standards and Technology (NIST). This algorithm relies on the difficulty of computing discrete logarithms over finite fields. Because it is based on arithmetic in finite fields, as is RSA, it bears some similarity to RSA.

We investigated digital signatures in Chapter 2. Recall that a digital signature is, like a handwritten signature, a means of associating a mark unique to an individual with a body of text. The mark should be unforgeable, meaning that only the originator should be able to compute the signature value. But the mark should be verifiable, meaning that others should be able to check that the signature comes from the claimed originator. The general way of computing digital signatures is with public key encryption; the signer computes a signature value by using a private key, and others can use the public key to verify that the signature came from the corresponding private key.

El Gamal Algorithm

In the El Gamal algorithm, to generate a key pair, first choose a prime p and two integers, a and x, such that a < p and x < p and calculate y

= a^x mod p. The prime p should be chosen so that (p - 1) has a large prime factor, q. The private key is x and the public key is y, along with parameters p and a.

To sign a message m, choose a random integer k, 0 < k < p - 1, which has not been used before and which is relatively prime to (p - 1), and compute

r = a^k mod p

and

s = ^k-1 (m - xr) mod (p - 1)

where k^-1 is the multiplicative inverse of k mod (p - 1), so that k * k^-1 = 1 mod (p - 1). The message signature is then r and s. A recipient can use the public key y to compute y^r r^s mod p and determine that it is equivalent to a^m mod p. To defeat this encryption and infer the values of x and k given r, s, and m, the intruder could find a means of computing a discrete logarithm to solve y = a^x and r = a^k.

Digital Signature Algorithm

The U.S. Digital Signature Algorithm (DSA) (also called the Digital Signature Standard or DSS) [NIS94] is the El Gamal algorithm with a few restrictions. First, the size of p is specifically fixed at 2⁵¹¹ < p < 2⁵¹² (so that p is roughly 170 decimal digits long). Second, q, the

large prime factor of (p - 1) is chosen so that 2¹⁵⁹ < q < 2¹⁶⁰ . The algorithm explicitly uses H(m), a hash value, instead of the full message text m. Finally, the computations of r and s are taken mod q. Largely, one can argue that these changes make the algorithm easy to use for those who do not want or need to understand the underlying mathematics. However, they also weaken the potential strength of the encryption by reducing the uncertainty for the attacker.