 The DSA and related signature schemes

This section presents the Digital Signature Algorithm (DSA) and several related signature schemes. Most of these are presented over Z* for some large prime p, but all of these mechanisms can be generalized to any finite cyclic group; this is illustrated explicitly for the El-

1

Gamal signature scheme in §11.5.2. All of the methods discussed in this section are randomized digital signature schemes (see Definition 11.2). All give digital signatures with appendix and can be modified to provide digital signatures with message recovery (see Note 11.14). A necessary condition for the security of all of the signature schemes described in this section is that computing logarithms in Z* be computationally infeasible. This condition, however, is not necessarily sufficient for the security of these schemes; analogously, it remains unproven that RSA signatures are secure even if factoring integers is hard.

The Digital Signature Algorithm (DSA)

In August of 1991, the U.S. National Institute of Standards and Technology (NIST) proposed a digital signature algorithm (DSA). The DSA has become a U.S. Federal Information Processing Standard (FIPS 186) called the Digital Signature Standard (DSS), and is the first digital signature scheme recognized by any government. The algorithm is a variant of the ElGamal scheme (§11.5.2), and is a digital signature scheme with appendix.

The signature mechanism requires a hash function h: {0,1}* —> Zq for some integer q. The DSS explicitly requires use of the Secure Hash Algorithm (SHA-1), given by Algorithm 9.53.

11.54 Algorithm Key generation for the DSA

SUMMARY: each entity creates a public key and corresponding private key.

Each entity A should do the following:

• 1. Select a prime number q such that 2159 < q < 2160.
• 2. Choose t so that 0 < t < 8, and select a prime number p where 2511+64f < p < 25i2+C4t, with the property that q divides (p - 1).
• 3. (Select a generator a of the unique cyclic group of order q in Z*.)
• 3.1 Select an element д e Z* and compute a = mod p.
• 3.2 If a = 1 then go to step 3.1.
• 4. Select a random integer a such that 1 < a < q — 1.
• 5. Compute у = a° mod p.
• 6. A’s public key is (p, q, a, y) A’s private key is a.
• 11.55 Note (generation of DSA primes p and q) In Algorithm 11.54 one must select the prune q first and then try to find a prime p such that q divides (p - 1). The algorithm recommended by the DSS for accomplishing this is Algorithm 4.56.
• 11.56 Algorithm DSA signature generation and verification  
• 2. Verification. To verify A’s signature (r, s) on m, В should do the following:
• (a) Obtain A’s authentic public key (p, q, a, y).
• (b) Verify that 0 < r < q and 0 < s < q if not, then reject the signature.
• (c) Compute w = s 1 mod q and h(m).
• (d) Compute u = w li(m) mod q and и2 = rw mod q.
• (e) Compute v = (aUlyU2 mod p) mod q.
• (f) Accept the signature if and only if v = r.

witha 160-bit modulus, two 160-bit modular multiplications, and one addition. The 160-bit operations are relatively minor compared to the exponentiation. The DS A has the advantage that the exponentiation can be precomputed and need not be done at the tune of signature generation. By comparison, no precomputation is possible with the RSA signature scheme. The major portion of the work for signature verification is two exponentiations modulo p, each to 160-bit exponents. On average, these each require 240 modular multiplications or 480 in total. Some savings can be realized by doing the two exponentiations simultaneously (cf. Note 14.91); the cost, on average, is then 280 modular multiplications.

• 11.61 Note (system-wide parameters) It is not necessary for each entity to select its own prunes p and q. The DSS permits p, q, and a to be system-wide parameters. This does, however, present a more attractive target for an adversary.
• 11.62 Note (probability of failure) Verificationrequiresthecomputationofs-1 mod q. Ifs = 0, then .s-1 does not exist. To avoid this situation, the signer may check that ,s Ф 0; but if s is assumed to be a random element in Zq, then the probability that s = 0 is (i)1G0. In practice, this is extremely unlikely ever to occur. The signer may also check that г ф 0. If the signer detects that either r = 0 or s = 0, a new value of к should be generated.

•  SUMMARY: entity A signs a binary message m of arbitrary length. Any entity В can verifythis signature by using A’s public key.
•  Signature generation. Entity A should do the following: (a) Select a random secret integer k, 0 < к < q. (b) Compute r = (ak mod p) mod q (e.g., using Algorithm 2.143). (c) Compute/с-1 mod q (e.g., using Algorithm 2.142). (d) Compute s = k~1 {/;(m) + ar} mod q. (e) A’s signature for m is the pair (r, s).