13.5 The Digital Signature Algorithm – Introduction to Cryptography with Coding Theory, 3rd Edition

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 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|p1 (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 αg(p1)/q  (mod p). Then αq1  (mod p).

  3. Alice chooses a secret a such that 1a<q1 and calculates βαa  (mod p).

  4. Alice publishes (p, q, α, β) and keeps a secret.

Alice signs a message m by the following procedure:

  1. Select a random, secret integer k such that 0<k<q1.

  2. Compute r=(αk  (mod p))  (mod q).

  3. Compute sk1(m+ar)  (mod q).

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

For Bob to verify, he must

  1. Download Alice’s public information (p, q, α, β).

  2. Compute u1s1m  (mod q), and u2s1r  (mod q).

  3. Compute v=(αu1βu2  (mod p))  (mod q).

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

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

m(ar+ks)(mod q), 

which implies

s1m(ars1+k)(mod q).

Therefore,

ks1m+ars1(mod q)u1+au2(mod q).

So αk=αu1+au2=(αu1βu2  (mod p))  (mod 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 22048256=21792 numbers mod p that reduce to a given number mod q.

What is the advantage of having αq1  (mod 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 p1, but it was useless mod large prime factors such as q. In the ElGamal scheme, an attacker could determine a  (mod 2t), where 2t is the largest power of 2 dividing p1. 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.