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:
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.)
Let be a primitive root mod and let . Then .
Alice chooses a secret such that and calculates .
Alice publishes and keeps secret.
Alice signs a message by the following procedure:
Select a random, secret integer such that .
Compute .
Compute .
Alice’s signature for is , which she sends to Bob along with .
For Bob to verify, he must
Download Alice’s public information .
Compute , and .
Compute .
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.