# 13.5 The Digital Signature Algorithm

The National Institute of Standards and Technology proposed the Digital Signature Algorithm (DSA) in 1991 and adopted it as a standard in 1994. Later versions increased the sizes of the parameters. Just like the ElGamal method, DSA is a digital signature scheme with appendix. Also, like other schemes, it is usually a message digest that is signed. In this case, let’s say the hash function produces a 256-bit output. We will assume in the following that our data message  has already been hashed. Therefore, we are trying to sign a 256-bit message.

The generation of keys for DSA proceeds as follows. First, there is an initialization phase:

1. Alice finds a prime  that is 256 bits long and chooses a prime  that satisfies  (see Exercise 15). The discrete log problem should be hard for this choice of . (In the initial version,  had 512 bits. Later versions of the standard require longer primes, for example, 2048 bits.)

2. Let  be a primitive root mod  and let . Then .

3. Alice chooses a secret  such that  and calculates .

4. Alice publishes  and keeps  secret.

Alice signs a message  by the following procedure:

1. Select a random, secret integer  such that .

2. Compute .

3. Compute .

4. Alice’s signature for  is , which she sends to Bob along with .

For Bob to verify, he must

1. Download Alice’s public information .

2. Compute , and .

3. Compute .

4. Accept the signature if and only if .

We show that the verification works. By the definition of , we have



which implies



Therefore,



So . Thus .

As in the ElGamal scheme, the integer  must be kept secret. Anyone who has knowledge of  can sign any desired document. Also, if the same value of  is used twice, it is possible to find  by the same procedure as before.

In contrast to the ElGamal scheme, the integer  does not carry full information about . Knowing  allows us to find only the mod  value. There are approximately  numbers mod  that reduce to a given number mod .

What is the advantage of having  rather than using a primitive root? Recall the Pohlig-Hellman attack for solving the discrete log problem. It could find information mod small prime factors of , but it was useless mod large prime factors such as . In the ElGamal scheme, an attacker could determine , where  is the largest power of  dividing . This would not come close to finding , but the general philosophy is that many little pieces of information collectively can often be useful. The DSA avoids this problem by removing all but the mod  information for .

In the ElGamal scheme, three modular exponentiations are needed in the verification step. This step is modified for the DSA so that only two modular exponentiations are needed. Since modular exponentiation is one of the slower parts of the computation, this change speeds up the verification, which can be important if many signatures need to be verified in a short time.