Computer Security and Cryptography

17.10 NIST'S DIGITAL SIGNATURE ALGORITHM [NIST, 1991, 1994]

Public Key

• p an L-bit prime: conditions 512 ≤ L ≤ 1024 and L a multiple of 64;
• q a 160-bit prime factor of p − 1.
• h (an integer), 1 < h < p − 1 such that (modulo p) > 1.
• y = g^x (modulo p), x (randomly chosen).

Private Key: x < q.

Signing the Message: SHA[m] is the result of the Secure Hash Algorithm applied to the message m.

S1. Choose randomly subject to 1 = gcd{k, q − 1}.

S2.	Generate r = (gk (modulo p)) (modulo q) and s = (k−1(SHA[m] + xr)) (modulo q).
S3.	SHA[m] = (r, s).Verifying the Signature SIG[m] for m
V1.	Compute w = s−1 (modulo q), u1 = (wSHA[m]) (modulo q) and u2 = rw (modulo q)
V2.	Accept the transaction as properly signed if r = (gu1yu2 (modulo p)) (modulo q).

    Correctness of the DSS: Using (modulo p) → g^q (modulo p) = h^{p − 1}; (modulo p) = 1

C1.

Compute

A discussion of the validity of this signature protocol is contained in NIST [1991, 1994].

We describe two signature protocols whose strength ...