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 $m$ 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 $q$ that is 256 bits long and chooses a prime $p$ that satisfies $q|p-1$ (see Exercise 15). The discrete log problem should be hard for this choice of $p$. (In the initial version, $p$ had 512 bits. Later versions of the standard require longer primes, for example, 2048 bits.)

2. Let $g$ be a primitive root mod $p$ and let $\alpha \equiv g^{(p-1)/q}(\mathrm{m}\mathrm{o}\mathrm{d}p)$. Then ${\alpha }^q\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

3. Alice chooses a secret $a$ such that $1\le a<q-1$ and calculates $\beta \equiv {\alpha }^a(\mathrm{m}\mathrm{o}\mathrm{d}p)$.

4. Alice publishes $(p\text{,}q\text{,}\alpha \text{,}\beta )$ and keeps $a$ secret.

Alice signs a message $m$ by the following procedure:

1. Select a random, secret integer $k$ such that $0<k<q-1$.

2. Compute $r=({\alpha }^k(\mathrm{m}\mathrm{o}\mathrm{d}p))(\mathrm{m}\mathrm{o}\mathrm{d}q)$.

3. Compute $s\equiv k^{-1}(m+ar)(\mathrm{m}\mathrm{o}\mathrm{d}q)$.

4. Alice’s signature for $m$ is $(r\text{,}s)$, which she sends to Bob along with $m$.

For Bob to verify, he must

1. Download Alice’s public information $(p\text{,}q\text{,}\alpha \text{,}\beta )$.

2. Compute $u_1\equiv s^{-1}m(\mathrm{m}\mathrm{o}\mathrm{d}q)$, and $u_2\equiv s^{-1}r(\mathrm{m}\mathrm{o}\mathrm{d}q)$.

3. Compute $v=({\alpha }^{u_1}{\beta }^{u_2}(\mathrm{m}\mathrm{o}\mathrm{d}p))(\mathrm{m}\mathrm{o}\mathrm{d}q)$.

4. Accept the signature if and only if $v=r$.

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

which implies

Therefore,

So ${\alpha }^k={\alpha }^{u_1+a{u}_2}=({\alpha }^{u_1}{\beta }^{u_2}(\mathrm{m}\mathrm{o}\mathrm{d}p))(\mathrm{m}\mathrm{o}\mathrm{d}q)$. Thus $v=r$.

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

In contrast to the ElGamal scheme, the integer $r$ does not carry full information about $k$. Knowing $r$ allows us to find only the mod $q$ value. There are approximately $2^{2048-256}=2^{1792}$ numbers mod $p$ that reduce to a given number mod $q$.

What is the advantage of having ${\alpha }^q\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}p)$ 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 $p-1$, but it was useless mod large prime factors such as $q$. In the ElGamal scheme, an attacker could determine $a(\mathrm{m}\mathrm{o}\mathrm{d}{2}^t)$, where $2^t$ is the largest power of $2$ dividing $p-1$. This would not come close to finding $a$, 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 $q$ information for $a$.

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.