Federal Information Processing Standards Publications (FIPS PUBS) are issued by the National Institute of Standards and Technology after approval by the Secretary of Commerce pursuant to Section 111(d) of the Federal Property and Administrative Services Act of 1949, as amended by the Computer Security Act of 1987, Public Law 100-235.

Name of Standard: Digital Signature Standard (DSS).

Category of Standard: Computer Security; Cryptography.

Explanation: This Standard specifies a Digital Signature Algorithm (DSA) appropriate for applications requiring a digital rather than written signature. The DSA digital signature is a pair of large numbers represented in a computer as strings of binary digits. The digital signature is computed using a set of rules (i.e., the DSA) and a set of parameters such that the identity of the signatory and integrity of the data can be verified. The DSA provides the capability to generate and verify signatures. Signature generation makes use of a private key to generate a digital signature. Signature verification makes use of a public key which corresponds to, but is not the same as, the private key. Each user possesses a private and public key pair. Public keys are assumed to be known to the public in general. Private keys are never shared. Anyone can verify the signature of a user by employing that user's public key. Signature generation can be performed only by the possessor of the user's private key.

A hash function is used in the signature generation process to obtain a condensed version of data, called a message digest (see Figure 1). The message digest is then input to the DSA to generate the digital signature. The digital signature is sent to the intended verifier along with the signed data (often called the message). The verifier of the message and signature verifies the signature by using the sender's public key. The same hash function must also be used in the verification process. The hash function is specified in a separate standard, the Secure Hash Standard (SHS), FIPS 180. Similar procedures may be used to generate and verify signatures for stored as well as transmitted data.

Figure 1: Using the SHA with the DSA

a. Federal Information Resources Management Regulations (FIRMR) subpart 201.20.303, Standards, and subpart 201.39.1002, Federal Standards.

b. FIPS PUB 46-2, Data Encryption Standard.

c. FIPS PUB 73, Guidelines for Security of Computer Applications.

d. FIPS PUB 140-1, Security Requirements for Cryptographic Modules.

e. FIPS PUB 171, Key Management Using ANSI X9.17.

f. FIPS PUB 180, Secure Hash Standard.

a. Compliance with a standard would adversely affect the accomplishment of the mission of an operator of a Federal computer system; or

b. Compliance with a standard would cause a major adverse financial impact on the operator which is not offset by Government-wide savings.

1. INTRODUCTION

This publication prescribes the Digital Signature Algorithm (DSA) for digital signature generation and verification. Additional information is provided in Appendices 1 through 5.

2. GENERAL

When a message is received, the recipient may desire to verify that the message has not been altered in transit. Furthermore, the recipient may wish to be certain of the originator's identity. Both of these services can be provided by the DSA. A digital signature is an electronic analogue of a written signature in that the digital signature can be used in proving to the recipient or a third party that the message was, in fact, signed by the originator. Digital signatures may also be generated for stored data and programs so that the integrity of the data and programs may be verified at any later time.

This publication prescribes the DSA for digital signature generation and verification. In addition, the criteria for the public and private keys required by the algorithm are provided.

3. USE OF THE DSA ALGORITHM

The DSA is used by a signatory to generate a digital signature on data and by a verifier to verify the authenticity of the signature. Each signatory has a public and private key. The private key is used in the signature generation process and the public key is used in the signature verification process. For both signature generation and verification, the data which is referred to as a message, M, is reduced by means of the Secure Hash Algorithm (SHA) specified in FIPS YY. An adversary, who does not know the private key of the signatory, cannot generate the correct signature of the signatory. In other words, signatures cannot be forged. However, by using the signatory's public key, anyone can verify a correctly signed message.

A means of associating public and private key pairs to the corresponding users is required. That is, there must be a binding of a user's identity and the user's public key. This binding may be certified by a mutually trusted party. For example, a certifying authority could sign credentials containing a user's public key and identity to form a certificate. Systems for certifying credentials and distributing certificates are beyond the scope of this standard. NIST intends to publish separate document(s) on certifying credentials and distributing certificates.

4. DSA PARAMETERS

The DSA makes use of the following parameters:

1. p = a prime modulus, where 2^L-1 < p < 2^L for 512 = < L = <1024 and L a multiple of 64

2. q = a prime divisor of p - 1, where 2¹⁵⁹ < q < 2¹⁶⁰

3. g = h^(p-1)/q mod p, where h is any integer with 1 < h < p - 1 such that h^(p-1)/q mod p > 1
(g has order q mod p)

4. x = a randomly or pseudorandomly generated integer with 0 < x < q

5. y = g^x mod p

6. k = a randomly or pseudorandomly generated integer with 0 < k < q

r = (g^k mod p) mod q and

s = (k^-1(SHA(M) + xr)) mod q.

w = (s')^-1 mod q

u1 = ((SHA(M')w) mod q

u2 = ((r')w) mod q

v = (((g)^ul (y)^u2) mod p) mod q.

This appendix is for informational purposes only and is not required to meet the standard.

The purpose of this appendix is to show that if M' = M, r' = r and s' = s in the signature verification then v = r'. We need the following easy result.

LEMMA. Let p and q be primes so that q divides p - 1, h a positive integer less than p, and g = h^(p-1)/q mod p. Then g^q mod p = 1, and if m mod q = n mod q, then g^m mod p = gⁿ mod p.

Proof: We have

g^q mod p = (h^{(p- 1)/q} mod p)q mod p

= h^(p-1) mod p

= 1

g^m mod p = g^n+kq mod p

= (gⁿ g^kq) mod p

= ((gⁿ mod p) (g^q mod p)^k) mod p

= gⁿ mod p

We are now ready to prove the main result.

THEOREM. If M' = M, r' = r, and s' = s in the signature verification, then v = r'.

Proof: We have

w = (s')-1 mod q = s^-1 mod q

u1 = ((SHA(M'))w) mod q = ((SHA(M))w) mod q

u2 = ((r')w) mod q = (rw) mod q.

v = ((g^u1 y^u2) mod p) mod q

= ((g^SHA(M)w y^rw) mod p) mod q

= ((g^SHA(M)w g^xrw) mod p) mod q

= ((g^(SHA(M)+xr)w) mod p) mod q.

s = (k^-1(SHA(M) + xr)) mod q.

w = (k(SHA(M) + xr)^-1) mod q

(SHA(M) + xr)w mod q = k mod q.

v = (g^k mod p) mod q

= r

= r'.

This appendix includes algorithms for generating the primes p and q used in the DSA. These algorithms require a random number generator (see Appendix 3), and an efficient modular exponentiation algorithm. Generation of p and q shall be performed as specified in this appendix, or using other FIPS approved security methods.

In order to generate the primes p and q, a primality test is required.

There are several fast probabilistic algorithms available. The following algorithm is a simplified version of a procedure due to M.O. Rabin, based in part on ideas of Gary L. Miller. [See Knuth, The Art of Computer Programming, Vol. 2, Addison-Wesley, 1981, Algorithm P, page 379.] If this algorithm is iterated n times, it will produce a false prime with probability no greater than 1/4ⁿ. Therefore, n > or = to 50 will give an acceptable probability of error. To test whether an integer is prime:

Step 1. Set i = 1 and n > or = to 50.

Step 2. Set w = the integer to be tested, w = 1 + 2^am, where m is odd and 2^a is the largest power of 2 dividing w - 1.

Step 3. Generate a random integer b in the range 1 < b < w.

Step 4. Set j = 0 and z = b^m mod w.

Step 5. If j = 0 and z = 1, or if z = w - 1, go to step 9.

Step 6. If j > 0 and z = 1, go to step 8.

Step 7. j = j + 1. If j < a, set z = z² mod w and go to step 5.

Step 8. w is not prime. Stop.

Step 9. If i < n, set i = i + 1 and go to step 3. Otherwise, w is probably prime.

The DSS requires two primes, p and q, satisfying the following three conditions:

a. 2¹⁵⁹ < q < 2¹⁶⁰

b. 2^L-1 < p < 2^L for a specified L, where L = 512 + 64j for some 0 < or = to j < or = to 8

c. q divides p - 1.

An integer x in the range 0 < or = to x < 2^g may be converted to a g-long sequence of bits by using its binary expansion as shown below:

x = x₁*2^g-1 + x₂*2^g-2 + ... + x_g-1*2 + x_g -> { x₁,...,x_g }.

{ x₁,...,x_g } -> x₁*2^g-1 + x₂*2^g-2 + ... + x_g-1*2 + x_g.

Let L - 1 = n*160 + b, where both b and n are integers and 0 < or = to b < 160.

Step 1. Choose an arbitrary sequence of at least 160 bits and call it SEED. Let g be the length of SEED in bits.

Step 2. Compute

Step 3. Form q from U by setting the most significant bit (the 2¹⁵⁹ bit) and the least significant bit to 1. In terms of boolean operations, q = U OR 2¹⁵⁹ OR 1. Note that 2¹⁵⁹ < q < 2¹⁶⁰.

Step 4. Use a robust primality testing algorithm to test whether q is prime¹²(1).

Step 5. If q is not prime, go to step 1.

Step 6. Let counter = 0 and offset = 2.

Step 7. For k = 0,...,n let

Step 8. Let W be the integer