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.
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
= ax 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 = ak mod p
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 yr
rs mod p and determine that it is equivalent to am 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 =
ax and r = ak.
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 2511 < p < 2512 (so that p is
roughly 170 decimal digits long). Second, q, the
large prime factor of (p - 1) is chosen so that
2159 < q < 2160 . 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.