Digital Signature Standard (DSS)

From Wikisource
Jump to navigation Jump to search

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.

Fips186-2.svg

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:

  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:

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

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 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. ∎

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 = 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′. ∎

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:

  1. 2159 < q < 2160
  2. 2L-1 < p < 2L for a specified L, where L = 512 + 64j for some 0 ≤ j ≤ 8
  3. Page:Fips186-2-change1.pdf/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.
    Page:Fips186-2-change1.pdf/19 Page:Fips186-2-change1.pdf/20 Page:Fips186-2-change1.pdf/21 Page:Fips186-2-change1.pdf/22 Page:Fips186-2-change1.pdf/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: X

    KEY =

    bd029bbe 7f51960b cf9edb2b 61f06f0f eb5a38b6

    t =

    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 =

    687a66d9 0648f993 867e121f 4ddf9ddb 01205584

    t =

    EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301

    k = G(t,KKEY) mod q




    Finally:

    h = 2

    p =

    8df2a494 492276aa 3d25759b b06869cb eac0d83a fb8d0cf7 cbb8324f 0d7882e5 d0762fc5 b7210eaf c2e9adac 32ab7aac
    Page:Fips186-2-change1.pdf/25 Page:Fips186-2-change1.pdf/26

    APPENDIX 6. RECOMMENDED ELLIPTIC CURVES FOR FEDERAL GOVERNMENT USE
    July 1999


    This collection of elliptic curves is recommended for Federal government use and contains choices of private key length and underlying fields.


    1. Parameter Choices


    1.1 Choice of Key Lengths

    The principal parameters for elliptic curve cryptography are the elliptic curve E and a designated point G on E called the base point. The base point has order r, a large prime. The number of points on the curve is n = fr for some integer f (the cofactor) not divisible by r. For efficiency reasons, it is desirable to take the cofactor to be as small as possible.

    All of the curves given below have cofactors 1, 2, or 4. As a result, the private and public keys are approximately the same length. Each length is chosen to correspond to the cryptovariable length of a common symmetric cryptologic. In each case, the private key length is, at least, approximately twice the symmetric cryptovariable length.


    1.2 Choice of Underlying Fields

    For each cryptovariable length, there are given two kinds of fields.

    • A prime field is the field GF(p) which contains a prime number p of elements. The elements of this field are the integers modulo p, and the field arithmetic is implemented in terms of the arithmetic of integers modulo p.
    • A binary field is the field GF(2m) which contains 2m elements for some m (called the degree of the field). The elements of this field are the bit strings of length m, and the field arithmetic is implemented in terms of operations on the bits.

    The following table gives the sizes of the various underlying fields. By ||p|| is meant the length of the binary expansion of the integer p.

    Symmetric Example
    CV Length Algorithm Prime Field Binary Field
    80 SKIPJACK ||p|| = 192 m = 163
    112 Triple-DES ||p|| = 224 m = 233
    128 AES Small ||p|| = 256 m = 283
    192 AES Medium ||p|| = 384 m = 409
    256 AES Large ||p|| = 521 m = 571


    1.3 Choice of Basis

    To describe the arithmetic of a binary field, it is first necessary to specify how a bit string is to be interpreted. This is referred to as choosing a basis for the field. There are two common types of bases: a polynomial basis and a normal basis.

    • A polynomial basis is specified by an irreducible polynomial modulo 2, called the field polynomial. The bit string (am-1a2 a1 a0) is taken to represent the polynomial

      am-1tm-1 + … + a2t2 + a1t + a0

      over GF(2). The field arithmetic is implemented as polynomial arithmetic modulo p(t), where p(t) is the field polynomial.

    • A normal basis is specified by an element θ of a particular kind. The bit string (a0 a1 a2am-1) is taken to represent the element

      a0θ + a1θ2 + a2θ22 + am-1θ2m-1

      Normal basis field arithmetic is not easy to describe or efficient to implement in general, but is for a special class called Type T low-complexity normal bases. For a given field degree m, the choice of T specifies the basis and the field arithmetic (see Appendix 6.2).

    There are many polynomial bases and normal bases from which to choose. The following procedures are commonly used to select a basis representation.

    • Polynomial Basis: If an irreducible trinomial tm + tk + 1 exists over GF(2), then the field polynomial p(t) is chosen to be the irreducible trinomial with the lowest-degree middle term tk. If no irreducible trinomial exists, then one selects instead a pentanomial tm + ta + tb + tc + 1. The particular pentanomial chosen has the following properties: the second term ta has the lowest degree m; the third term tb has the lowest degree among all irreducible pentanomials of degree m and second term ta; and the fourth term tc has the lowest degree among all irreducible pentanomials of degree m, second term ta, and third term tb.
    • Normal Basis: Choose the Type T low-complexity normal basis with the smallest T.

    For each binary field, the parameters are given for the above basis representations.


    1.4 Choice of Curves

    Two kinds of curves are given:

    • Pseudo-random curves are those whose coefficients are generated from the output of a seeded cryptographic hash. If the seed value is given along with the coefficients, it can be verified easily that the coefficients were indeed generated by that method.
    • Special curves whose coefficients and underlying field have been selected to optimize the efficiency of the elliptic curve operations.

    For each size, the following curves are given:

    • A pseudo-random curve over GF(p).
    • A pseudo-random curve over GF(2m).
    • A special curve over GF(2m) called a Koblitz curve or anomalous binary curve.

    The pseudo-random curves are generated via the SHA-1 based method given in the ANSI X9.62 and IEEE P1363 standards. (The generation and verification processes are given in Appendices 6-4 through 6-7.)


    1.5 Choice of Base Points

    Any point of order r can serve as the base point. Each curve is supplied with a sample base point G = (Gx, Gy). Users may want to generate their own base points to ensure cryptographic separation of networks.


    2. Curves over Prime Fields

    For each prime p, a pseudo-random curve

    E: y2x3 - 3x + b (mod p)

    of prime order r is listed[1]. (Thus, for these curves, the cofactor is always f = 1.)

    The following parameters are given:

    • The prime modulus p
    • The order r
    • the 160-bit input seed s to SHA-1 based algorithm
    • The output c of the SHA-1 based algorithm
    • The coefficient b (satisfying b2 c ≡ -27 (mod p))
    • The base point x coordinate Gx
    • The base point y coordinate Gy

    The integers p and r are given in decimal form; bit strings and field elements are given in hex.

    Curve P-192

    p = 6277101735386680763835789423207666416083908700390324961279
    r = 6277101735386680763835789423176059013767194773182842284081
    s = 3045ae6f c8422f64 ed579528 d38120ea e12196d5
    c = 3099d2bb bfcb2538 542dcd5f b078b6ef 5f3d6fe2 c745de65
    b = 64210519 e59c80e7 0fa7e9ab 72243049 feb8deec c146b9b1
    Gx = 188da80e b03090f6 7cbf20eb 43a18800 f4ff0afd 82ff1012
    Gy = 07192b95 ffc8da78 631011ed 6b24cdd5 73f977a1 1e794811

    Curve P-224

    p = 26959946667150639794667015087019630673557916260026308143510066298881
    r = 26959946667150639794667015087019625940457807714424391721682722368061
    s = bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5
    c = 5b056c7e 11dd68f4 0469ee7f 3c7a7d74 f7d12111 6506d031 218291fb
    b = b4050a85 0c04b3ab f5413256 5044b0b7 d7bfd8ba 270b3943 2355ffb4
    Gx = b70e0cbd 6bb4bf7f 321390b9 4a03c1d3 56c21122 343280d6 115c1d21
    Gy = bd376388 b5f723fb 4c22dfe6 cd4375a0 5a074764 44d58199 85007e34

    Curve P-256

    p = 115792089210356248762697446949407573530086143415290314195533631308867097853951
    r = 115792089210356248762697446949407573529996955224135760342422259061068512044369
    s = c49d3608 86e70493 6a6678e1 139d26b7 819f7e90
    c = 7efba166 2985be94 03cb055c 75d4f7e0 ce8d84a9 c5114abc af317768 0104fa0d
    b = 5ac635d8 aa3a93e7 b3ebbd55 769886bc 651d06b0 cc53b0f6 3bce3c3e 27d2604b
    Gx = 6b17d1f2 e12c4247 f8bce6e5 63a440f2 77037d81 2deb33a0 f4a13945 d898c296
    Gy = 4fe342e2 fe1a7f9b 8ee7eb4a 7c0f9e16 2bce3357 6b315ece cbb64068 37bf51f5

    Curve P-384

    p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319
    r = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643
    s = a335926a a319a27a 1d00896a 6773a482 7acdac73
    c = 79d1e655 f868f02f ff48dcde e14151dd b80643c1 406d0ca1 0dfe6fc5 2009540a 495e8042 ea5f744f 6e184667 cc722483
    b = b3312fa7 e23ee7e4 988e056b e3f82d19 181d9c6e fe814112 0314088f 5013875a c656398d 8a2ed19d 2a85c8ed d3ec2aef
    Gx = aa87ca22 be8b0537 8eb1c71e f320ad74 6e1d3b62 8ba79b98 59f741e0 82542a38 5502f25d bf55296c 3a545e38 72760ab7
    Gy = 3617de4a 96262c6f 5d9e98bf 9292dc29 f8f41dbd 289a147c e9da3113 b5f0b8c0 0a60b1ce 1d7e819d 7a431d7c 90ea0e5f

    Curve P-521

    p = 6864797660130609714981900799081393217269435300143305409394463459185543183397656052122559640661454554977296311391480858037121987999716643812574028291115057151
    r = 6864797660130609714981900799081393217269435300143305409394463459185543183397655394245057746333217197532963996371363321113864768612440380340372808892707005449
    s = d09e8800 291cb853 96cc6717 393284aa a0da64ba
    c = 0b4 8bfa5f42 0a349495 39d2bdfc 264eeeeb 077688e4 4fbf0ad8 f6d0edb3 7bd6b533 28100051 8e19f1b9 ffbe0fe9 ed8a3c22 00b8f875 e523868c 70c1e5bf 55bad637
    b = 051 953eb961 8e1c9a1f 929a21a0 b68540ee a2da725b 99b315f3 b8b48991 8ef109e1 56193951 ec7e937b 1652c0bd 3bb1bf07 3573df88 3d2c34f1 ef451fd4 6b503f00
    Gx = c6 858e06b7 0404e9cd 9e3ecb66 2395b442 9c648139 053fb521 f828af60 6b4d3dba a14b5e77 efe75928 fe1dc127 a2ffa8de 3348b3c1 856a429b f97e7e31 c2e5bd66
    Gy = 118 39296a78 9a3bc004 5c8a5fb4 2c7d1bd9 98f54449 579b4468 17afbd17 273e662c 97ee7299 5ef42640 c550b901 3fad0761 353c7086 a272c240 88be9476 9fd16650


    3. Curves over Binary Fields

    For each field degree m, a pseudo-random curve is given, along with a Koblitz curve. The pseudo-random curve has the form

    E: y2 + xy = x3 + x2 + b,

    and the Koblitz curve has the form

    Ea: y2 + xy = x3 + ax2 + 1

    where a = 0 or 1.

    For each pseudorandom curve, the cofactor is f = 2. The cofactor of each Koblitz curve is f = 2 if a = 1 and f = 4 if a = 0.

    The coefficients of the pseudo-random curves, and the coordinates of the base points of both kinds of curves, are given in terms of both the polynomial and normal basis representations discussed in 1.3.

    For each m, the following parameters are given:

    Field Representation:

    • The normal basis type T
    • The field polynomial (a trinomial or pentanomial)

    Koblitz Curve:

    • The coefficient a
    • The base point order r
    • The base point x coordinate Gx
    • The base point y coordinate Gy

    Pseudo-random curve:

    • The base point order r

    Pseudo-random curve (Polynomial Basis representation):

    • The coefficient b
    • The base point x coordinate Gx
    • The base point y coordinate Gy

    Pseudo-random curve (Normal Basis representation):

    • The 160-bit input seed s to the SHA-1 based algorithm
    • The coefficient b (i.e., the output of the SHA-1 based algorithm)
    • The base point x coordinate Gx
    • The base point y coordinate Gy

    Integers (such as T, m, and r) are given in decimal form; bit strings and field elements are given in hex.

    Degree 163 Binary Field

    T = 4
    p(t) = t163 + t7 + t6 + t3 + 1

    Curve K-163

    a = 1
    r = 5846006549323611672814741753598448348329118574063

    Polynomial Basis:

    Gx = 2 fe13c053 7bbc11ac aa07d793 de4e6d5e 5c94eee8
    Gy = 2 89070fb0 5d38ff58 321f2e80 0536d538 ccdaa3d9

    Normal Basis:

    Gx = 0 5679b353 caa46825 fea2d371 3ba450da 0c2a4541
    Gy = 2 35b7c671 00506899 06bac3d9 dec76a83 5591edb2

    Curve B-163

    r = 5846006549323611672814742442876390689256843201587

    Polynomial Basis:

    b = 2 0a601907 b8c953ca 1481eb10 512f7874 4a3205fd
    Gx = 3 f0eba162 86a2d57e a0991168 d4994637 e8343e36
    Gy = 0 d51fbc6c 71a0094f a2cdd545 b11c5c0c 797324f1

    Normal Basis:

    s = 85e25bfe 5c86226c db12016f 7553f9d0 e693a268
    b = 6 645f3cac f1638e13 9c6cd13e f61734fb c9e3d9fb
    Gx = 0 311103c1 7167564a ce77ccb0 9c681f88 6ba54ee8
    Gy = 3 33ac13c6 447f2e67 613bf700 9daf98c8 7bb50c7f

    Degree 233 Binary Field

    T = 2
    p(t) = t233 + t74 + 1

    Curve K-233

    a = 0
    r = 3450873173395281893717377931138512760570940988862252126328087024741343

    Polynomial Basis:

    Gx = 172 32ba853a 7e731af1 29f22ff4 149563a4 19c26bf5 0a4c9d6e efad6126
    Gy = 1db 537dece8 19b7f70f 555a67c4 27a8cd9b f18aeb9b 56e0c110 56fae6a3

    Normal Basis:

    Gx = 0fd e76d9dcd 26e643ac 26f1aa90 1aa12978 4b71fc07 22b2d056 14d650b3
    Gy = 064 3e317633 155c9e04 47ba8020 a3c43177 450ee036 d6335014 34cac978

    Curve B-233

    r = 6901746346790563787434755862277025555839812737345013555379383634485463

    Polynomial Basis:

    b = 066 647ede6c 332c7f8c 0923bb58 213b333b 20e9ce42 81fe115f 7d8f90ad
    Gx = 0fa c9dfcbac 8313bb21 39f1bb75 5fef65bc 391f8b36 f8f8eb73 71fd558b
    Gy = 100 6a08a419 03350678 e58528be bf8a0bef f867a7ca 36716f7e 01f81052

    Normal Basis:

    s = 74d59ff0 7f6b413d 0ea14b34 4b20a2db 049b50c3
    b = 1a0 03e0962d 4f9a8e40 7c904a95 38163adb 82521260 0c7752ad 52233279
    Gx = 18b 863524b3 cdfefb94 f2784e0b 116faac5 4404bc91 62a363ba b84a14c5
    Gy = 049 25df77bd 8b8ff1a5 ff519417 822bfedf 2bbd7526 44292c98 c7af6e02

    Degree 283 Binary Field

    T = 6
    p(t) = t283 + t12 + t7 + t5 + 1

    Curve K-283

    a = 0
    r = 3885337784451458141838923813647037813284811733793061324295874997529815829704422603873

    Polynomial Basis:

    Gx = 503213f 78ca4488 3f1a3b81 62f188e5 53cd265f 23c1567a 16876913 b0c2ac24 58492836
    Gy = 1ccda38 0f1c9e31 8d90f95d 07e5426f e87e45c0 e8184698 e4596236 4e341161 77dd2259

    Normal Basis:

    Gx = 3ab9593 f8db09fc 188f1d7c 4ac9fcc3 e57fcd3b db15024b 212c7022 9de5fcd9 2eb0ea60
    Gy = 2118c47 55e7345c d8f603ef 93b98b10 6fe8854f feb9a3b3 04634cc8 3a0e759f 0c2686b1

    Curve B-283

    r = 7770675568902916283677847627294075626569625924376904889109196526770044277787378692871

    Polynomial Basis:

    b = 27b680a c8b8596d a5a4af8a 19a0303f ca97fd76 45309fa2 a581485a f6263e31 3b79a2f5
    Gx = 5f93925 8db7dd90 e1934f8c 70b0dfec 2eed25b8 557eac9c 80e2e198 f8cdbecd 86b12053
    Gy = 3676854 fe24141c b98fe6d4 b20d02b4 516ff702 350eddb0 826779c8 13f0df45 be8112f4

    Normal Basis:

    s = 77e2b073 70eb0f83 2a6dd5b6 2dfc88cd 06bb84be
    b = 157261b 894739fb 5a13503f 55f0b3f1 0c560116 66331022 01138cc1 80c0206b dafbc951
    Gx = 749468e 464ee468 634b21f7 f61cb700 701817e6 bc36a236 4cb8906e 940948ea a463c35d
    Gy = 62968bd 3b489ac5 c9b859da 68475c31 5bafcdc4 ccd0dc90 5b70f624 46f49c05 2f49c08c

    Degree 409 Binary Field

    T = 4
    p(t) = t409 + t87 + 1


    Curve K-409

    a = 0
    r = 330527984395124299475957654016385519914202341482140609642324395022880711289249191050673258457777458014096366590617731358671

    Polynomial Basis:

    Gx = 060f05f 658f49c1 ad3ab189 0f718421 0efd0987 e307c84c 27accfb8 f9f67cc2 c460189e b5aaaa62 ee222eb1 b35540cf e9023746
    Gy = 1e36905 0b7c4e42 acba1dac bf04299c 3460782f 918ea427 e6325165 e9ea10e3 da5f6c42 e9c55215 aa9ca27a 5863ec48 d8e0286b

    Normal Basis:

    Gx = 1b559c7 cba2422e 3affe133 43e808b5 5e012d72 6ca0b7e6 a63aeafb c1e3a98e 10ca0fcf 98350c3b 7f89a975 4a8e1dc0 713cec4a
    Gy = 16d8c42 052f07e7 713e7490 eff318ba 1abd6fef 8a5433c8 94b24f5c 817aeb79 852496fb ee803a47 bc8a2038 78ebf1c4 99afd7d6

    Curve B-409

    r = 661055968790248598951915308032771039828404682964281219284648798304157774827374805208143723762179110965979867288366567526771

    Polynomial Basis:

    b = 021a5c2 c8ee9feb 5c4b9a75 3b7b476b 7fd6422e f1f3dd67 4761fa99 d6ac27c8 a9a197b2 72822f6c d57a55aa 4f50ae31 7b13545f
    Gx = 15d4860 d088ddb3 496b0c60 64756260 441cde4a f1771d4d b01ffe5b 34e59703 dc255a86 8a118051 5603aeab 60794e54 bb7996a7
    Gy = 061b1cf ab6be5f3 2bbfa783 24ed106a 7636b9c5 a7bd198d 0158aa4f 5488d08f 38514f1f df4b4f40 d2181b36 81c364ba 0273c706

    Normal Basis:

    s = 4099b5a4 57f9d69f 79213d09 4c4bcd4d 4262210b
    b = 124d065 1c3d3772 f7f5a1fe 6e715559 e2129bdf a04d52f7 b6ac7c53 2cf0ed06 f610072d 88ad2fdc c50c6fde 72843670 f8b3742a
    Gx = 0ceacbc 9f475767 d8e69f3b 5dfab398 13685262 bcacf22b 84c7b6dd 981899e7 318c96f0 761f77c6 02c016ce d7c548de 830d708f
    Gy = 199d64b a8f089c6 db0e0b61 e80bb959 34afd0ca f2e8be76 d1c5e9af fc7476df 49142691 ad303902 88aa09bc c59c1573 aa3c009a

    Degree 571 Binary Field

    T = 10
    p(t) = t571 + t10 + t5 + t2 + 1

    Curve K-571

    a = 0
    r = 1932268761508629172347675945465993672149463664853217499328617625725759571144780212268133978522706711834706712800825351461273674974066617311929682421617092503555733685276673

    Polynomial Basis:

    Gx = 26eb7a8 59923fbc 82189631 f8103fe4 ac9ca297 0012d5d4 60248048 01841ca4 43709584 93b205e6 47da304d b4ceb08c bbd1ba39 494776fb 988b4717 4dca88c7 e2945283 a01c8972
    Gy = 349dc80 7f4fbf37 4f4aeade 3bca9531 4dd58cec 9f307a54 ffc61efc 006d8a2c 9d4979c0 ac44aea7 4fbebbb9 f772aedc b620b01a 7ba7af1b 320430c8 591984f6 01cd4c14 3ef1c7a3

    Normal Basis:

    Gx = 04bb2db a418d0db 107adae0 03427e5d 7cc139ac b465e593 4f0bea2a b2f3622b c29b3d5b 9aa7a1fd fd5d8be6 6057c100 8e71e484 bcd98f22 bf847642 37673674 29ef2ec5 bc3ebcf7
    Gy = 44cbb57 de20788d 2c952d7b 56cf39bd 3e89b189 84bd124e 751ceff4 369dd8da c6a59e6e 745df44d 8220ce22 aa2c852c fcbbef49 ebaa98bd 2483e331 80e04286 feaa2530 50caff60
    Page:Fips186-2-change1.pdf/50 Page:Fips186-2-change1.pdf/51

    APPENDIX 6.1: IMPLEMENTATION OF MODULAR ARITHMETIC

    The prime moduli in the above examples are of a special type (called generalized Mersenne numbers) for which modular multiplication can be carried out more efficiently than in general. This appendix provides the rules for implementing this faster arithmetic, for each of the prime moduli appearing in the examples.

    The usual way to multiply two integers (mod m) is to take the integer product and reduce it (mod m). One therefore has the following problem: given an integer A less than m2, compute

    B := A mod m.

    In general, one must obtain B as the remainder of an integer division. If m is a generalized Mersenne number, however, then B can be expressed as a sum or difference (mod m) of a small number of terms. To compute this expression, one can evaluate the integer sum or difference and reduce the result modulo m. The latter reduction can be accomplished by adding or subtracting a few copies of m.

    The prime moduli p for each of the five example curves is a generalized Mersenne number.

    Page:Fips186-2-change1.pdf/53 Page:Fips186-2-change1.pdf/54 Page:Fips186-2-change1.pdf/55 Page:Fips186-2-change1.pdf/56 Page:Fips186-2-change1.pdf/57 Page:Fips186-2-change1.pdf/58 Page:Fips186-2-change1.pdf/59 Page:Fips186-2-change1.pdf/60 Page:Fips186-2-change1.pdf/61 Page:Fips186-2-change1.pdf/62 Page:Fips186-2-change1.pdf/63 Page:Fips186-2-change1.pdf/64 Page:Fips186-2-change1.pdf/65 Page:Fips186-2-change1.pdf/66 Page:Fips186-2-change1.pdf/67 Page:Fips186-2-change1.pdf/68 Page:Fips186-2-change1.pdf/69 Page:Fips186-2-change1.pdf/70 Page:Fips186-2-change1.pdf/71 Page:Fips186-2-change1.pdf/72 Page:Fips186-2-change1.pdf/73 FIPS 186-2, DIGITAL SIGNATURE STANDARD
    CHANGE NOTICE 1

    U.S. DEPARTMENT OF COMMERCE
    NATIONAL INSTITUTE OF STANDARDS AND TECHNOLOGY
    Gaithersburg, MD 20899

    DATE OF CHANGE: 2001 October 5

    Federal Information Processing Standard (FIPS) 186-2, Digital Signature Standard, specifies the Digital Signature Algorithm (DSA) that may be used in the generation and verification of digital signatures for sensitive, unclassified applications. FIPS 186-2 also allows the use of the digital signature techniques specified in American National Standards Institute (ANSI) X9.31 (Digital Signatures Using Reversible Public Key Cryptography for the Financial Services Industry (rDSA)) and ANSI X9.62 (Public Key Cryptography for the Financial Services Industry: The Elliptic Curve Digital Signature Algorithm (ECDSA)). The standard also specifies a transition period for the use of existing (legacy) digital signature systems. Reversible public key algorithms, such as the RSA or Rabin-Williams algorithms, are often used in these legacy systems.

    FIPS 186-2 is used in conjunction with the hash function specified in FIPS 180-1, Secure Hash Standard (SHS), and includes specifications for the size of the prime modulus p, and algorithms for the generation of a user's private key, x, and a user's per message secret number, k.

    This change notice provides changes for the continued use of DSA as specified in FIPS 186-2 about the size of the prime modulus p, modifications for the random number generation techniques specified in Appendix 3 of FIPS 186-2, and provides instructions for the use of these techniques when used in contexts other than the generation of DSA keys. This change notice also provides guidance for the use of the reversible public key algorithms within legacy systems.

    Questions regarding this change notice may be directed to FIPS186@nist.gov or to Elaine Barker (ebarker@nist.gov, 301-975-2911).


    The Size of the Prime Modulus

    Section 4 of FIPS 186-2 specifies that the prime modulus p of DSA is defined for the range of prime integers 2L-1 < p < 2L, where 512 ≤ L ≤ 1024 and L is a multiple of 64. This change notice specifies that L should assume only the value 1024 for DSA as specified in FIPS 186-2, i.e., the prime modulus p should be defined in the range 21023 < p < 21024.

    The RSA and Rabin-Williams algorithms used within legacy systems are defined with a modulus n and prime factors p and q of n. This change notice specifies that n should be at least 1024 bits in length, and p and q should be approximately half the size of n in bits.


    Random Number Generation

    FIPS 186-2 includes algorithms for the generation of a user's private key, x, and a user's per message secret number, k. These values must be generated randomly or pseudorandomly and must have values between 0 and the 160-bit prime q (as specified in the standard). Techniques for generating x and k are provided in Appendix 3 of the standard.

    Recently, an unpublished attack on DSA[2] was found that relies on the non-uniformity of the pseudorandom number generators (PRNGs) specified in Appendix 3 of the standard. The attack has a workfactor of 264 and requires 222 known signatures. This attack can be defended against by either limiting the number of signatures created using a specific key pair to no more than 2 million signatures while using the PRNGs specified in FIPS 186-2, or by modifying the PRNGs.

    If the PRNGs currently defined in FIPS 186-2 are used, the user should be provided with clear guidance about the limitation to the number of signatures that should be created.

    Alternatively, the following modifications of the PRNGs may be used in lieu of those PRNGs specified in FIPS 186-2. These modifications reduce the non-uniformity of the PRNGs and do not affect interoperability.

    The two algorithms described below use a one-way function G(t,c), where t is 160 bits, c is b bits and G(t,c) is 160 bits. Two methods for constructing G are defined in FIPS 186-2: using SHA-1 as defined in FIPS 180-1, and using the Data Encryption Standard (DES) as defined in FIPS 46-3. If G is constructed using SHA-1, b is between 160 and 512 bits (160 ≤ b ≤ 512); if G is constructed using DES, b is equal to 160 bits.

    1. Revised Algorithm for Computing m values of x (Appendix 3.1 of FIPS 186-2)

    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 [FIPS 180-1].

    Page:Fips186-2-change1.pdf/76 Page:Fips186-2-change1.pdf/77

_____________________

  1. The selection a = -3 for the coefficient of x was made for reasons of efficiency; see IEEE P1363.
  2. 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).