ARCHIVED PUBLICATION
`
`The attached publication,
`
`FIPS Publication 186­2 (with Change Notice 1)
`(change notice dated October 5, 2001),
`
`was superseded on June 9, 2009 and is provided here only
`for historical purposes.
`
`For the most current revision of this publication, see:
`http://csrc.nist.gov/publications/PubsFIPS.html.
`
`1
`
`BLACKBERRY 2002
`FACEBOOK V. BLACKBERRY
`IPR2019-00923
`
`

`

`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
`
`2
`
`

`

`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.
`
`3
`
`

`

`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.
`
`1
`
`4
`
`

`

`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
`
`2
`
`5
`
`

`

`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.
`
`3
`
`6
`
`

`

`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.
`
`4
`
`7
`
`

`

`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.
`
`5
`
`8
`
`

`

`6
`
`9
`
`

`

`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,
`
`7
`
`10
`
`

`

`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:
` 1. p = a prime modulus, where 2L-1 < p < 2L for 512 ≤ L ≤ 1024 and L a multiple of 64
` 2. q = a prime divisor of p - 1, where 2159 < q < 2160
`
` 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 = gx mod p
`
` 6. 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:
`
`8
`
`11
`
`

`

`r = (gk 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
`
`9
`
`12
`
`

`

`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.
`
`10
`
`13
`
`

`

`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 gq mod p = 1, and if m mod q = n mod q, then gm mod p = gn mod p.
`
`Proof: We have
`
`gq 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
`
`gm mod p = gn+kq mod p
`
` = (gn gkq) mod p
`
` = ((gn mod p) (gq mod p)k) mod p
`
` = gn mod p
`
`since gq mod p = 1. (cid:132)
`
`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.
`
`11
`
`14
`
`

`

`Now y = gx mod p, so that by the lemma,
`
`v = ((gu1 yu2) mod p) mod q
`
` = ((gSHA-1(M)w yrw) mod p) mod q
`
` = ((gSHA-1(M)w gxrw) 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 = (gk mod p) mod q
`
` = r
` = r′. (cid:132)
`
`12
`
`15
`
`

`

`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/4n.
`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 + 2am, where m is odd and 2a 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 = bm 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 = z2 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:
`
` a. 2159 < q < 2160
` b. 2L-1 < p < 2L for a specified L, where L = 512 + 64j for some 0 ≤ j ≤ 8
`
`13
`
`16
`
`

`

` c. q divides p - 1.
`
`This prime generation scheme starts by using the SHA-1 and a user supplied SEED to construct a
`prime, q, in the range 2159 < q < 2160. Once this is accomplished, the same SEED value is used to
`construct an X in the range 2L-1 < X < 2L. The prime, p, is then formed by rounding X to a number
`congruent to 1 mod 2q as described below.
`An integer x in the range 0 ≤ x < 2g may be converted to a g-long sequence of bits by using its binary
`expansion as shown below:
`
`x = x1*2g-1 + x2*2g-2 + ... + xg-1*2 + xg -> { x1,...,xg }.
`
`Conversely, a g-long sequence of bits { x1,...,xg } is converted to an integer by the rule
`
`{ x1,...,xg } -> x1*2g-1 + x2*2g-2 + ... + xg-1*2 + xg.
`
`Note that the first bit of a sequence corresponds to the most significant bit of the corresponding
`integer and the last bit to the least significant bit.
`Let L - 1 = n*160 + b, where both b and n are integers and 0 ≤ 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
`
` U = SHA-1[SEED] XOR SHA-1[(SEED+1) mod 2g ].
`
` Step 3. Form q from U by setting the most significant bit (the 2159 bit) and the least significant
` bit to 1. In terms of boolean operations, q = U OR 2159 OR 1. Note that 2159 < q < 2160.
`
` Step 4. Use a robust primality testing algorithm to test whether q is prime1.
`
` 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
`
`Vk = SHA-1[(SEED + offset + k) mod 2g ].
`
`1A robust primality test is one where the probability of a non-prime number passing the test is at
`most 2-80.
`
`14
`
`17
`
`

`

` Step 8. Let W be the integer
`
` W = V0 + V1*2160 + ... + Vn-1*2(n-1)*160 + (Vn mod 2b) * 2n*160
`and let X = W + 2L-1. Note that 0 ≤ W < 2L-1 and hence 2L-1 ≤ X < 2L.
` Step 9. Let c = X mod 2q and set p = X - (c - 1). Note that p is congruent to 1 mod 2q.
`
` Step 10. If p < 2L-1, then go to step 13.
`
` Step 11. Perform a robust primality test on p.
`
` Step 12. If p passes the test performed in step 11, go to step 15.
`
` Step 13. Let counter = counter + 1 and offset = offset + n + 1.
` Step 14. If counter ≥ 212 = 4096 go to step 1, otherwise (i.e. if counter < 4096) go to step 7.
` Step 15. Save the value of SEED and the value of counter for use in certifying the proper
`generation of p and q.
`
`15
`
`18
`
`

`

`APPENDIX 3. RANDOM NUMBER GENERATION FOR THE DSA
`
`Any implementation of the DSA requires the ability to generate random or pseudorandom integers.
` Such numbers are used to derive a user's private key, x, and a user's per message secret number, k.
` These randomly or pseudorandomly generated integers are selected to be between 0 and the 160-bit
`prime q (as specified in the standard). They shall be generated by the techniques given in this
`appendix, or using other FIPS approved security methods.
`
`One FIPS approved pseudorandom integer generator is supplied in Appendix C of ANSI X9.17,
`"Financial Institution Key Management (Wholesale)."
`
`Other pseudorandom integer generators are given in this appendix. These permit generation of
`pseudorandom values of x and k for use in the DSA. The algorithm in section 3.1 may be used to
`generate values for x. An algorithm for k and r is given in section 3.2. The latter algorithm allows
`most of the signature computation to be precomputed without knowledge of the message to be
`signed.
`The algorithms employ a one-way function G(t,c), where t is 160 bits, c is b bits (160 ≤ b ≤ 512) and
`G(t,c) is 160 bits. One way to construct G is via the Secure Hash Algorithm (SHA-1), as defined
`in the Secure Hash Standard (SHS). The 160-bit message digest output of the SHA-1 algorithm
`when message M is input is denoted by SHA-1(M). A second method for constructing G is to use
`the Data Encryption Standard (DES). The construction of G by these techniques is discussed in
`sections 3.3 and 3.4 of this appendix.
`
`In the algorithms in sections 3.1 and 3.2, a secret b-bit seed-key is used. The algorithm in section
`3.1 optionally allows the use of a user provided input. If G is constructed via the SHA-1 as defined
`in section 3.3, then b is between 160 and 512. If DES is used to construct G as defined in section
`3.4, then b is equal to 160.
`
`3.1. ALGORITHM FOR COMPUTING m VALUES OF x
`
`Let x be the signer's private key. The following may be used to generate m values of x:
`
` Step 1. Choose a new, secret value for the seed-key, XKEY.
`
` Step 2. In hexadecimal notation let
`
`t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0.
`
` This is the initial value for H0 || H1 || H2 || H3 || H4 in the SHS.
`
` Step 3. For j = 0 to m - 1 do
`
`16
`
`19
`
`

`

` a. XSEEDj = optional user input.
` b. XVAL = (XKEY + XSEEDj) mod 2b.
`
` c. xj = G(t,XVAL) mod q.
`
` d. XKEY = (1 + XKEY + xj) mod 2b.
`
`3.2. ALGORITHM FOR PRECOMPUTING ONE OR MORE k AND r VALUES
`
`This algorithm can be used to precompute k, k-1, and r for m messages at a time. Note that
`implementation of the DSA with precomputation may be covered by U.S. and foreign patents.
`
`Algorithm:
`
` Step 1. Choose a secret initial value for the seed-key, KKEY.
`
` Step 2. In hexadecimal notation let
`
`t = EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301.
`
` This is a cyclic shift of the initial value for H0 || H1 || H2 || H3 || H4 in the SHS.
`
` Step 3. For j = 0 to m - 1 do
`
` a. k = G(t,KKEY) mod q.
`
` b. Compute kj
`
`-1 = k-1 mod q.
`
` c. Compute rj = (gk mod p) mod q.
`
` d. KKEY = (1 + KKEY + k) mod 2b.
`
` Step 4. Suppose M0 , ... , Mm-1 are the next m messages. For j = 0 to m - 1 do
`
` a. Let h = SHA-1(Mj).
`
` b. Let sj = (kj
`
`-1(h + xrj)) mod q.
`
` c. The signature for Mj is (rj,sj).
`
` Step 5. Let t = h.
`
` Step 6. Go to step 3.
`
`17
`
`20
`
`

`

`Step 3 permits precomputation of the quantities needed to sign the next m messages. Step 4 can
`begin whenever the first of these m messages is ready. The execution of step 4 can be suspended
`whenever the next of the m messages is not ready. As soon as steps 4 and 5 have completed, step
`3 can be executed, and the results saved until the first member of the next group of m messages is
`ready.
`
`In addition to space for KKEY, two arrays of length m are needed to store r0 , ... rm-1 and k0-1, ... , km-
`
`-1 when they are computed in step 3. Storage for s0 , ... , sm-1 is only needed if the signatures for a
`1
`group of messages are stored; otherwise sj in step 4 can be replaced by s and a single space allocated.
`
`3.3. CONSTRUCTING THE FUNCTION G FROM THE SHA-1
`
`G(t,c) may be constructed using steps (a) - (e) in section 7 of the Specifications for the Secure Hash
`Standard. Before executing these steps, {Hj} and M1 must be initialized as follows:
`
` i. Initialize the {Hj} by dividing the 160 bit value t into five 32-bit segments as follows:
`
`t = t0 || t1 || t2 || t3 || t4
`
` Then Hj = tj for j = 0 through 4.
`
` ii. There will be only one message block, M1, which is initialized as follows:
`
` M1 = c || 0512-b
`
` (The first b bits of M1 contain c, and the remaining (512-b) bits are set to zero).
`
`Then steps (a) through (e) of section 7 are executed, and G(t,c) is the 160 bit string represented by
`the five words:
`
` H0 || H1 || H2 || H3 || H4
`
`at the end of step (e).
`
`3.4. CONSTRUCTING THE FUNCTION G FROM THE DES
`
`Let a XOR b denote the bitwise exclusive-or of bit strings a and b. Suppose a1, a2, b1, b2 are 32-bit
`strings. Let b1' be the 24 least significant bits of b1. Let K = b1' || b2 and A = a1 || a2. Define
`
` DESb1,b2(a1,a2) = DESK(A)
`
`In the above, DESK(A) represents ordinary DES encryption of the 64-bit block A using the 56-bit
`
`18
`
`21
`
`

`

`key K. Now suppose t and c are each 160 bits. To compute G(t,c):
`
` Step 1. Write
`
`t = t1 || t2 || t3 || t4 || t5
`
`c = c1 || c2 || c3 || c4 || c5
`
` In the above, each ti and ci is 32 bits.
`
` Step 2. For i = 1 to 5 do
`
`xi = ti XOR ci
`
` Step 3. For i = 1 to 5 do
`
`b1 = c((i+3) mod 5) + 1
`
`b2 = c((i+2) mod 5) + 1
`
`a1 = xi
`
`a2 = x(i mod 5) + 1 XOR x((i+3) mod 5) + 1
`
`yi,1 || yi,2 = DESb1,b2(a1,a2)
`
`(yi,1, yi,2 = 32 bits)
`
` Step 4. For i = 1 to 5 do
`
`zi = yi,1 XOR y((i+1) mod 5)+1,2 XOR y((i+2) mod 5)+1,1
`
` Step 5. Let
`
`G(t,c) = z1 || z2 || z3 || z4 || z5
`
`19
`
`22
`
`

`

`APPENDIX 4. GENERATION OF OTHER QUANTITIES FOR THE DSA
`
`This appendix is for informational purposes only and is not required to meet the standard.
`
`The algorithms given in this appendix may be used to generate the quantities g, k-1, and s-1 used in
`the DSA.
`
`To generate g:
`
` Step 1. Generate p and q as specified in Appendix 2.
`
` Step 2. Let e = (p - 1)/q.
`
` Step 3. Set h = any integer, where 1 < h < p - 1 and h differs from any value previously tried.
`
` Step 4. Set g = he mod p.
`
` Step 5. If g = 1, go to step 3.
`
`To compute the multiplicative inverse n-1 mod q for n with 0 < n < q, where 0 < n-1 < q:
`
` Step 1. Set i = q, h = n, v = 0, and d = 1.
`
` Step 2. Let t = i DIV h, where DIV is defined as integer division.
`
` Step 3. Set x = h.
`
` Step 4. Set h = i - tx.
`
` Step 5. Set i = x.
`
` Step 6. Set x = d.
`
` Step 7. Set d = v - tx.
`
` Step 8. Set v = x.
`
` Step 9. If h > 0, go to step 2.
`
` Step 10. Let n-1 = v mod q.
`
`Note that in step 10, v may be negative. The v mod q operation should yield a value between 1 and
`q - 1 inclusive.
`
`20
`
`23
`
`

`

`APPENDIX 5. EXAMPLE OF THE DSA
`
`This appendix is for informational purposes only and is not required to meet the standard.
`Let L = 512 (size of p). The values in this example are expressed in hexadecimal notation. The p
`and q given here were generated by the prime generation standard described in appendix 2 using the
`160-bit SEED:
`d5014e4b 60ef2ba8 b6211b40 62ba3224 e0427dd3
`With this SEED, the algorithm found p and q when the counter was at 105. x was generated by the
`algorithm described in appendix 3, section 3.1, using the SHA-1 to construct G (as in appendix 3,
`section 3.3) and a 160-bit XKEY:
`
`XKEY =
`
`t =
`
`bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6
`
`67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0
`x = G(t,XKEY) mod q
`
`k was generated by the algorithm described in appendix 3, section 3.2, using the SHA-1 to construct
`G (as in appendix 3, section 3.3) and a 160-bit KKEY:
`
`KKEY =
`
`t =
`
`687a66d9 0648f993 867e121f 4ddf9ddb 01205584
`
`EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301
`k = G(t,KKEY) mod q
`
`h = 2
`
`p =
`
`8df2a494 492276aa 3d25759b b06869cb eac0d83a fb8d0cf7
`cbb8324f 0d7882e5 d0762fc5 b7210eaf c2e9adac 32ab7aac
`
`21
`
`24
`
`

`

`49693dfb f83724c2 ec0736ee 31c8