# Digital Signature Standard (DSS)

from the Federal Information Processing Standards (FIPS) Publication Series of the National Institute of Standards and Technology (NIST)
FIPS PUB 186-2
(+Change Notice)
FEDERAL INFORMATION
PROCESSING STANDARDS PUBLICATION
2000 January 27
U.S. DEPARTMENT OF COMMERCE/National Institute of Standards and Technology
DIGITAL SIGNATURE STANDARD (DSS)
CATEGORY: COMPUTER SECURITY
U.S. DEPARTMENT OF COMMERCE, William M. Daley, Secretary
NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY,
Raymond G. Kammer, Director
Foreword
The Federal Information Processing Standards Publication Series of the National Institute of Standards and Technology (NIST) is the official series of publications relating to standards and guidelines adopted and promulgated under the provisions of Section 5131 of the Information Technology Management Reform Act of 1996 (Public Law 104-106), and the Computer Security Act of 1987 (Public Law 100-235). These mandates have given the Secretary of Commerce and NIST important responsibilities for improving the utilization and management of computer and related telecommunications systems in the Federal Government. The NIST, through its Information Technology Laboratory, provides leadership, technical guidance, and coordination of Government efforts in the development of standards and guidelines in these areas.
Comments concerning Federal Information Processing Standards Publications are welcomed and should be addressed to the Director, Information Technology Laboratory, National Institute of Standards and Technology, 100 Bureau Dr. Stop 8900, Gaithersburg, MD 20899-8900.
William Mehuron, Director
Information Technology Laboratory
Abstract
This standard specifies a suite of algorithms which can be used to generate a digital signature. Digital signatures are used to detect unauthorized modifications to data and to authenticate the identity of the signatory. In addition, the recipient of signed data can use a digital signature in proving to a third party that the signature was in fact generated by the signatory. This is known as nonrepudiation since the signatory cannot, at a later time, repudiate the signature.
Key words: ADP security, computer security, digital signatures, public-key cryptography, Federal Information Processing Standards.
FIPS PUB 186-2
Federal Information Processing Standards Publication 186-2
2000 January 27
Announcing the
DIGITAL SIGNATURE STANDARD (DSS)
Federal Information Processing Standards Publications (FIPS PUBS) are issued by the National Institute of Standards and Technology (NIST) after approval by the Secretary of Commerce pursuant to Section 5131 of the Information Technology Management Reform Act of 1996 (Public Law 104­-106), and 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 algorithms appropriate for applications requiring a digital, rather than written, signature. A digital signature is represented in a computer as a string of binary digits. A digital signature is computed using a set of rules and a set of parameters such that the identity of the signatory and integrity of the data can be verified. An algorithm 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 digital signature (ds) algorithm 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-1. FIPS approved ds algorithms must be implemented with the SHS. Similar procedures may be used to generate and verify signatures for stored as well as transmitted data.
Approving Authority: Secretary of Commerce.
Maintenance Agency: U.S. Department of Commerce, National Institute of Standards and Technology (NIST), Information Technology Laboratory (ITL).
Applicability: This standard is applicable to all Federal departments and agencies for the protection of sensitive unclassified information that is not subject to section 2315 of Title 10, United States Code, or section 3502(2) of Title 44, United States Code. This standard shall be used in designing and implementing public-key based signature systems that Federal departments and agencies operate or which are operated for them under contract. Adoption and use of this standard is available to private and commercial organizations.
Applications: A digital signature (ds) algorithm authenticates the integrity of the signed data and the identity of the signatory. A ds algorithm may also be used in proving to a third party that data was actually signed by the generator of the signature. A ds algorithm is intended for use in electronic mail, electronic funds transfer, electronic data interchange, software distribution, data storage, and ​other applications that require data integrity assurance and data origin authentication. The techniques specified in ANSI X9.31 and ANSI X9.62 may be used in addition to the Digital Signature Algorithm (DSA) specified herein. (NIST editorial note: either DSA, RSA [ANSI X9.31], or ECDSA [ANSI X9.62] may be used; all three do not have to be implemented.)
Implementations: A ds algorithm may be implemented in software firmware, hardware or any combination thereof. NIST has developed a validation program to test implementations for conformance to DSA. Currently, conformance tests for ANSI X9.31 and ANSI X9.62 have not been developed. These tests will be developed and made available in the future. Information about the planned validation program can be obtained from the National Institute of Standards and Technology, Information Technology Laboratory, Attn: DSS Validation, 100 Bureau Drive Stop 8930, Gaithersburg, MD 20899-8930.
Agencies are advised that separate keys should be used for signature and confidentiality purposes when using the X9.31 standard. This is because the RSA algorithm can be used for both data encryption and digital signature purposes.
Export Control: Certain cryptographic devices and technical data regarding them are subject to Federal export controls. Applicable Federal government export controls are specified in Title 15, Code of Federal Regulations (CFR) Part 740.17; Title 15, CFR Part 742; and Title 15, CFR Part 774, Category 5, Part 2.
Patents: The algorithms in this standard may be covered by U.S. or foreign patents.
Implementation Schedule: This standard becomes effective July 27, 2000. A transition period from July 27, 2000 until July 27, 2001 is provided to enable all agencies to develop plans for the acquisition of equipment which implements the digital signature techniques adopted by FIPS 186-2. During the transition period, agencies may continue to use their existing digital signature systems and to acquire additional equipment that may be needed to interoperate with these legacy digital signature systems. Agencies without legacy digital signature systems should plan for the acquisition and use of equipment implementing the digital signature techniques that are adopted by FIPS 186-2. After the transition period, only equipment that implements FIPS 186-2 endorsed techniques should be acquired.
Specifications: Federal Information Processing Standard (FIPS) 186-2 Digital Signature Standard (affixed). Also see an important change notice at the end of this document.
Cross Index:
a. FIPS PUB 46-3, Data Encryption Standard.
b. FIPS PUB 73, Guidelines for Security of Computer Applications.
​c. FIPS PUB 140-1, Security Requirements for Cryptographic Modules.
d. FIPS PUB 171, Key Management Using ANSI X9.17.
e. FIPS PUB 180-1, Secure Hash Standard.
f. ANSI X9.31-1998, Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA).
g. ANSI X9.62-1998, Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA).
Qualifications: The security of a digital signature system is dependent on maintaining the secrecy of users' private keys. Users must therefore guard against the unauthorized acquisition of their private keys. While it is the intent of this standard to specify general security requirements for generating digital signatures, conformance to this standard does not assure that a particular implementation is secure. The responsible authority in each agency or department shall assure that an overall implementation provides an acceptable level of security. This standard will be reviewed every five years in order to assess its adequacy.
Waiver Procedure: Under certain exceptional circumstances, the heads of Federal agencies, or their delegates, may approve waivers to Federal Information Processing Standards (FIPS). The head of such agency may redelegate such authority only to a senior official designated pursuant to section 3506(b) of Title 44, United States Code. Waiver shall be granted only when:
a. Compliance with a standard would adversely affect the accomplishment of the mission of an operator of a Federal computer system; or
b. Cause a major adverse financial impact on the operator which is not offset by Government wide savings.
Agency heads may act upon a written waiver request containing the information detailed above. Agency heads may also act without a written waiver request when they determine that conditions for meeting the standard cannot be met. Agency heads may approve waivers only by a written decision which explains the basis on which the agency head made the required finding(s). A copy of each such decision, with procurement sensitive or classified portions clearly identified, shall be sent to: National Institute of Standards and Technology; ATTN: FIPS Waiver Decisions, 100 Bureau Drive Stop 8970, Gaithersburg, MD 20899-8970.
In addition, notice of each waiver granted and each delegation of authority to approve waivers shall be sent promptly to the Committee on Government Operations of the House of Representatives and the Committee on Governmental Affairs of the Senate and shall be published promptly in the Federal Register.
​When the determination on a waiver applies to the procurement of equipment and/or services, a notice of the waiver determination must be published in the Commerce Business Daily as a part of the notice of solicitation for offers of an acquisition or, if the waiver determination is made after that notice is published, by amendment to such notice.
A copy of the waiver, any supporting documents, the document approving the waiver and any supporting and accompanying documents, with such deletions as the agency is authorized and decides to make under 5 U.S.C. Sec. 552(b), shall be part of the procurement documentation and retained by the agency.
Where to Obtain Copies of the Standard: Copies of this publication are for sale by the National Technical Information Service, U.S. Department of Commerce, Springfield, VA 22161. When ordering, refer to Federal Information Processing Standards Publication 186-2 (FIPSPUB186-2), and identify the title. When microfiche is desired, this should be specified. Prices are published by NTIS in current catalogs and other issuances. Payment may be made by check, money order, deposit account or charged to a credit card accepted by NTIS.
Federal Information Processing Standards Publication 186-2
2000 January 27
Specifications for the
DIGITAL SIGNATURE STANDARD (DSS)
1. INTRODUCTION
This publication prescribes three algorithms suitable for digital signature (ds) generation and verification. The first algorithm, the Digital Signature Algorithm (DSA), is described in sections 4 - 6 and appendices 1 - 5. The second algorithm, the RSA ds algorithm, is discussed in section 7 and the third algorithm, the ECDSA algorithm, is discussed in section 8 and recommended elliptic curves in appendix 6. An important change notice has been appended to this document.
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 a ds algorithm. 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 two algorithms suitable for digital signature generation and verification.
3. USE OF A DIGITAL SIGNATURE (ds) ALGORITHM
A ds algorithm 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-1) specified in FIPS 180-1. 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:
* p = a prime modulus, where 2$^{L-1}$ < p < 2$^L$ for 512 ≤ L ≤ 1024 and L a multiple of 64
* q = a prime divisor of p - 1, where 2$^{159}$ < q < 2$^{160}$
* 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)
* x = a randomly or pseudorandomly generated integer with 0 < x < q
* y = g$^x$ mod p
* k = a randomly or pseudorandomly generated integer with 0 < k < q
The integers p, q, and g can be public and can be common to a group of users. A user's private and public keys are x and y, respectively. They are normally fixed for a period of time. Parameters x and k are used for signature generation only, and must be kept secret. Parameter k must be regenerated for each signature.
Parameters p and q shall be generated as specified in Appendix 2, or using other FIPS approved security methods. Parameters x and k shall be generated as specified in Appendix 3, or using other FIPS approved security methods.
5. DSA SIGNATURE GENERATION
The signature of a message M is the pair of numbers r and's computed according to the equations below:
    r = (g$^k$ mod p) mod q and
    s = (k$^{-1}$(SHA-1(M) + xr)) mod q.
In the above, k$^{-1}$ is the multiplicative inverse of k, mod q; i.e., (k$^{-1}$ k) mod q = 1 and 0 < k$^{-1}$ < q. The value of SHA-1(M) is a 160-bit string output by the Secure Hash Algorithm specified in FIPS 180-1. For use in computing s, this string must be converted to an integer. The conversion rule is given in Appendix 2.2.
As an option, one may wish to check if r = 0 or s = 0. If either r = 0 or s = 0, a new value of k should be generated and the signature should be recalculated (it is extremely unlikely that r = 0 or s = 0 if signatures are generated properly).
The signature is transmitted along with the message to the verifier.
6. DSA SIGNATURE VERIFICATION
Prior to verifying the signature in a signed message, p, q and g plus the sender's public key and identity are made available to the verifier in an authenticated manner.
Let M, r′, and's′ be the received versions of M, r, and s, respectively, and let y be the public key of the signatory. To verify the signature, the verifier first checks to see that 0 < r′ < q and 0 < s′ < q; if either condition is violated the signature shall be rejected. If these two conditions are satisfied, the verifier computes
    w = (s′)$^{-1}$ mod q
    u1 = ((SHA-1(M′))w) mod q
    u2 = ((r′)w) mod q
    v = (((g)$^{u1}$ (y)$^{u2}$) mod p) mod q.
If v = r′, then the signature is verified and the verifier can have high confidence that the received message was sent by the party holding the secret key x corresponding to y. For a proof that v = r′ when M′ = M, r′ = r, and s′ = s, see Appendix 1.
If v does not equal r′, then the message may have been modified, the message may have been incorrectly signed by the signatory, or the message may have been signed by an impostor. The message should be considered invalid.
7. RSA DIGITAL SIGNATURE ALGORITHM
​The RSA ds algorithm is a FIPS approved cryptographic algorithm for digital signature generation and verification. This is described in ANSI X9.31.
8. ELLIPTIC CURVE DIGITAL SIGNATURE ALGORITHM (ECDSA)
The ECDSA ds algorithm is a FIPS approved cryptographic algorithm for digital signature generation and verification. ECDSA is the elliptic curve analogue of the DSA. ECDSA is described in ANSI X9.62. The recommended elliptic curves for Federal Government use are included in Appendix 6.
APPENDIX 1. A PROOF THAT v = r′ IN THE DSA
This appendix is for informational purposes only and is not required to meet the standard.
The purpose of this appendix is to show that in the DSA, 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$^n$ mod p.
Proof: We have
    g$^q$ mod p = (h$^{(p-1)/q}$ mod p)$^q$ mod p
          = h$^{(p-1)}$ mod p
          = 1
by Fermat's Little Theorem. Now let m mod q = n mod q, i.e., m = n + kq for some integer k. Then
    g$^m$ mod p = g$^{n+kq}$ mod p
          = (g$^n$ g$^{kq}$) mod p
          = ((g$^n$ mod p) (g$^q$ mod p)$^k$) mod p
          = g$^n$ mod p
since g$^q$ mod p = 1. ∎
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-1(M′))w) mod q = ((SHA-1(M))w) mod q
    u2 = ((r′)w) mod q = (rw) mod q.
​Now y = g$^x$ mod p, so that by the lemma,
    v = ((g$^{u1}$ y$^{u2}$) mod p) mod q
       = ((gSHA-1$^{(M)w}$ y$^{rw}$) mod p) mod q
       = ((gSHA-1$^{(M)w}$ g$^{xrw}$) mod p) mod q
       = ((g$^($SHA-1$^{(M)+xr)w}$) mod p) mod q.
Also
    s = (k$^{-1}$(SHA-1(M) + xr)) mod q.
Hence
    w = (k(SHA-1(M) + xr)$^{-1}$) mod q
    (SHA-1(M) + xr)w mod q = k mod q.
Thus by the lemma,
    v = (g$^k$ mod p) mod q
       = r
       = r′. ∎
APPENDIX 2. GENERATION OF PRIMES FOR THE DSA
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.
2.1. A PROBABILISTIC PRIMALITY TEST
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$^n$. Therefore, n ≥ 50 will give an acceptable probability of error. To test whether an integer is prime:
    Step 1. Set i = 1 and n ≥ 50.
    Step 2. Set w = the integer to be tested, w = 1 + 2$^a$m, 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$^2$ 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.
2.2. GENERATION OF PRIMES
The DSA requires two primes, p and q, satisfying the following three conditions:
* 2$^{159}$ < q < 2$^{160}$
* 2$^{L-1}$ < p < 2$^L$ for a specified L, where L = 512 + 64j for some 0 ≤ j ≤ 8
* ↑ The selection a = -3 for the coefficient of x was made for reasons of efficiency; see IEEE P1363.
* ↑ The attack was discovered by Dr. Daniel Bliechenbacher of Lucent Technologies, Bell Labs, Murray Hill, NJ. See a February 25, 2001 press article at http://www.lucent.com/press/0201/010205.bla.html.
_____________________
This work is in the public domain in the United States because it is a work of the United States federal government (see 17 U.S.C. 105).
Public domainPublic domainfalsefalse