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

Mo, M-l

FIPS PUB 186-2

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

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 ofCommerce pursuant

to Section 5131 ofthe 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

verily 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 ofthe 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

Signature Generation Signature Verification

Message Received Message

l l

Secure Hash Algorithm-1 Secure Hash Algorithm-1

l l

Message Digest Message Digest

Private Digital Digital Public

A ds Algorithm

Sign Operation

ds Algorithm

Verify Operation

Key Signature Signature Key

*

Yes - Signature Verified

or

No - Signature Verification Failed

*

Approving Authority: Secretary ofCommerce.

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 ofthe signed data and

the identity ofthe signatory. A ds algorithm may also be used in proving to a third party that data

was actually signed by the generator ofthe signature. A ds algorithm is intended for use in electronic

mail, electronic funds transfer, electronic data interchange, software distribution, data storage, and

2

I

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) Pan 740.17; Title 15, CFR Pan 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).

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 ofsecurity. 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 ofthe House of Representatives and

the Committee on Governmental Affairs ofthe Senate and shall be published promptly in the Federal

Register.

4

When the determination on a waiver applies to the procurement of equipment and/or services, a

notice ofthe waiver determination must be published in the Commerce Business Daily as a part of

the notice ofsolicitation for offers of an acquisition or, ifthe 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 ofthe procurement documentation and

retained by the agency.

Where to Obtain Copies of the Standard: Copies ofthis 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

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.

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 ofthe 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 ofthe 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

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 ofthe 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 ofthe 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 - l, where 21?9 < q < 2160

3. g = h(p'1)/q mod p, where h is any integer with 1 < h < p - 1 such that htp‘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

r = (gk mod p) mod q and

s = (k ‘(SHA-l(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-l(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 ifr = 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

ul = ((SHA-l(M'))w) mod q

u2 = ((r')w) mod q

v = (((g)ul (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

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 ofthe DSA. ECDSA is

described in ANSI X9.62. The recommended elliptic curves for Federal Government use are

included in Appendix 6.

10

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 ofthis 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 g4 mod p = 1, and if m mod q = n mod q, then gni mod p = gn mod p.

Proof: We have

g4 mod p = (hlp 1,4 mod p)4 mod p

= h(p'n mod p

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) (g4 mod p)k) mod p

= gn mod p

since g4 mod p = 1.

We are now ready to prove the main result.

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

Proof: We have

w = (s')"1 mod q = s"1 mod q

ul = ((SHA-l(M'))w) mod q = ((SHA-l(M))w) mod q

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

11

Now y = gx mod p, so that by the lemma,

v = C(gu' yu2) mod p) mod q

= ((gSHA-l<M)w /*) mod p) mod q

= ((gSHA-l‘M,w g* ) mod p) mod q

= ((g(SHA-l(MKxr)w) mod p) mod q.

Also

s = (k'’(SHA-l(M) + xr)) mod q.

Hence

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

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

Thus by the lemma,

v = (gk mod p) mod q

= r

= r'.

12

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 ofGary 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 l/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. Ifj = 0 and z = 1, or if z = w - 1, go to step 9.

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

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

Step 8. w is not prime. Stop.

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

2.2. GENERATION OF PRIMES

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

a. 2159 < q < 2160

b. 2L1 < p < 2l for a specified L, where L = 512 + 64j for some 0 < j < 8

13

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 2 '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 < 2s may be converted to a g-long sequence of bits by using its binary

expansion as shown below:

x = xi*28'' + x?*28'2 + ... + xg.i*2 + xg -> { xi,...,xg }.

Conversely, a g-long sequence of bits { xi,...,xg } is converted to an integer by the rule

{ xi,...,xg } -> Xi*28_1 + x2*28'2 + ... + xg.i*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 28 ].

Step 3. Form q from U by setting the most significant bit (the 21V'1 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 28 ].

'A robust primality test is one where the probability of a non-prime number passing the test is at

most 2'80.

14

Step 8. Let W be the integer

W = V0 + V,*2160 + ... + Vn.,*2(n'ln60 + (Vn mod 2b) * 2n’160

and let X = W + 2LA. Note that 0 < W < 2L1 and hence 2LA < 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 < 2L1, 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

APPENDIX 3. RANDOM NUMBER GENERATION FOR THE DSA

Any implementation ofthe 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 ofthis 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 Ho || Hi || H21| H31| FL in the SHS.

Step 3. Forj = 0 to m - 1 do

16

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 ofthe 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 ofthe initial value for H01| Hi || H21| H31| H4 in the SHS.

Step 3. Forj = 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 Mo ,... , Mm.i are the next m messages. Forj = 0 to m - 1 do

a. Let h = SHA-l(Mj).

b. Let Sj = (kj"’(h + xrj)) mod q.

c. The signature for Mj is (r^Sj).

Step 5. Let t = h.

Step 6. Go to step 3.

17

Step 3 permits precomputation of the quantities needed to sign the next m messages. Step 4 can

begin whenever the first ofthese m messages is ready. The execution ofstep 4 can be suspended

whenever the next ofthe 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 ofthe next group of m messages is

ready.

In addition to space for KJCJEY, two arrays of length m are needed to store r0,... rm-i and ko'1,..., km.

i"1 when they are computed in step 3. Storage for so ,..., Sn,_i is only needed ifthe signatures for a

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 ofthe Specifications for the Secure Hash

Standard. Before executing these steps, {Hj} and Mi must be initialized as follows:

i. Initialize the {Hj f by dividing the 160 bit value t into five 32-bit segments as follows:

t = to || ti || t2 || t3 || t4

Then Hj = tj for j = 0 through 4.

ii. There will be only one message block. Mi, which is initialized as follows:

Mi = c || 0512'b

(The first b bits of M, contain c, and the remaining (512-b) bits are set to zero).

Then steps (a) through (e) ofsection 7 are executed, and G(t,c) is the 160 bit string represented by

the five words:

Ho || Hi || H2 || Hi || H4

at the end ofstep (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 al, a2, bl, b2 are 32-bit

strings. Let bl’ be the 24 least significant bits of bl. Let K = bl' || b2 and A = al || a2. Define

DESbi.b2(al ,a2) = DESk(A)

In the above, DESk(A) represents ordinary DES encryption ofthe 64-bit block A using the 56-bit

18

key K. Now suppose t and c are each 160 bits. To compute G(t,c):

Step 1. Write

t = ti || t21| t3 Hull t5

c = Cl II c2 II c3 II c4 II c5

In the above, each tj and Cj is 32 bits.

Step 2. For i = 1 to 5 do

Xj = tj XOR Cj

Step 3. For i = 1 to 5 do

bl =c((i*3) mod 5)^1

b2 — C((j^2) mod 5) * i

al = Xj

a2 — X(j mo(j 5) +. i XOR X((j+3) mod 5) + 1

yu II yi.2 = DESbi,b2(al,a2) (yu, y;.2 - 32 bits)

Step 4. For i = 1 to 5 do

— yi. 1 XOR y((j*i) mod 5)-*-1.2 XOR y((j-2) mod 5)+l,l

Step 5. Let

G(t,c) = Zi || Z2 || Z3 || Z4 || z3

19

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 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 - l)/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 D1V 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

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 =

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 =

687a66d9 0648f993 867el21f 4ddf9ddb 01205584

t =

EFCDAB89 98BADCFE 10325476 C3D2E1F0 67452301

k = G(t,KKEY) mod q

Finally:

h = 2

P =

8df2a494 4 92 27 6aa 3d25759b b06869cb eac0d83a fb8d0cf7

cbb8324f 0d7882e5 d0762fc5 b7210eaf c2e9adac 32ab7aac

21

4 96 93dfb f83724c2 ec0736ee 31c80291

q =

C773218C 737ec8ee 993b4f2d ed30f48e dace915f

g =

626d0278 39ea0al3 413163a5 5b4cb500 299d5522

3bfflOf3 99ce2c2e 71cb9de5 fa24babf 58e5b795

c42e9f6f 464b088c c572af53 e6d78802

X =

207 0b322 3dba372f delcOffc 7b2e3b49 8b260614

k =

358dad57 1462710f 50e254cf Ia376b2b deaadfbf

k! =

0d516729 82 02e4 9b 4116acl0 4fc3f415 ae52f917

M = ASCII form of"abc" (See FIPS PUB 180-1, Appendix A)

(SHA-1 )(M) =

a9993e36 4706816a ba3e2571 7850c26c 9cd0d89d

19131871 d75bl612 a819f29d 78dlb0d7 346f7aa7

9bfd6c56 75da9d21 2d3a36ef 1672ef66 0b8c7c25

858fba33 f44c0669 9630a76b 030ee333

r =

8baclab6 6410435c b7181f95 bl6ab97c 92b341c0

w

4le2345f If56df24 58f426dl 55b4ba2d b6dcd8c8

9df4ece5 826be95f ed406d41 b43edc0b lcl8841b

956cefcb

2192 5c9c

7bb62a8 5

5cc0ec74

22

ul =

u2 =

gul mod p

bf655bd0 46f0b35e c791b004 804afcbb 8ef7d69d

821a9263 12e97ade abcc8d08 2b527897 8a2df4b0

51blbf86 7888e5f3 af6fb476 9dd016bc fe667a65

9063bd3d 2bl38b4c e02cc0c0 2ec62bb6 7306c63e

6f96662a 1987a21b e4ec!071 010b6069

y112 mod p

8b510071 2957e950 50d6b8fd 376a668e 4b0d633c

5c611a72 e2b28483 beB2c74d 4b30de61 a668966e

c!9441f4 22bf3c34 08aebalf 0a4dbec7

8baclab6 6410435c b7181f95 bl6ab97c 92b341c0

aafc2753

4db9 5bbf

Ie46e665

dc307a67

23

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 ofKey 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/(the

cofactor) not divisible by r. For efficiency reasons, it is desirable to take the

cofactor to be as small as possible.

All ofthe 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 ofUnderlying 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 ofthis field are the integers modulo p, and the

24

field arithmetic is implemented in terms ofthe arithmetic of integers

modulo p.

• A binaryfield is the field GF{2"') which contains 2"' elements for some m

(called the degree ofthe field). The elements ofthis 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 ofthe various underlying fields. By ///?// is

meant the length ofthe binary expansion ofthe integer p.

Symmetric

CV Length

80

Example

Algorithm

SKIPJACK

Prime Field

M=192

Binarv Field

m = 163

112 Triple-DES IIpII = 224 m = 233

128 AES Small IIpII = 256 m = 283

192 AES Medium IIpII = 384 m = 409

256 AES Large m

CN

II

r~-

5II

1.3 Choice ofBasis

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.

25

• A polynomial basis is specified by an irreducible polynomial modulo 2,

called thefieldpolynomial. The bit string (am.\ ... a2 a \ a0) is taken to

represent the polynomial

am.11m 1 +... 4- a.2t2 + a 11 + <2o

over GF(2). The field arithmetic is implemented as polynomial arithmetic

modulo p{t), where pit) is the field polynomial.

• A normal basis is specified by an element 6 of a particular kind. The bit

string (fl0 a\ a2 ... am.\) is taken to represent the element

aoO + a\62 + a2d~ + am.\62

Normal basis field arithmetic is not easy to describe or efficient to

implement in general, but is for a special class called Type T lowcomplexity’ 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 t + t + 1 exists over GF

(2), then the field polynomial pit) 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 f 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 f has the lowest degree among all irreducible

pentanomials of degree m, second term f, and third term tb.

26

• 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 ofCurves

Two kinds of curves are given:

• Pseudo-random curves are those whose coefficients are generated from

the output of a seeded cryptographic hash. Ifthe 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 ofthe 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 PI363 standards. (The generation and verification

processes are given in Appendices 6-4 through 6-7.)

1.5 Choice ofBase Points

27

Any point of order r can serve as the base point. Each curve is supplied with

a sample base point G = (Gx , Gv). Users may want to generate their own base

points to ensure cryptographic separation of networks.

2. Curves over Prime Fields

For each prime /?, a pseudo-random curve

E : y2 = x2 - 3x +b (modp)

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

The following parameters are given:

• The prime modulus p

• The order r

• the 160-bit input seed 5 to SHA-1 based algorithm

• The output c ofthe SHA-1 based algorithm

• The coefficient b (satisfying b2 c = -27 (modp))

• The base point x coordinate Gx

• The base point v coordinate Gv

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

given in hex.

1 The selection a = -3 for the coefficient ofx was made for reasons of efficiency; see IEEE PI 363.

28

Curve P-192

62771017353866807638357894232076664160839087\

00390324961279

62771017353866807638357894231760590137671947\

73182842284081

3045ae6f c8422f64 ed579528 d38120ea el2196d5

3099d2bb

bfcb2538 542dcd5f b078b6ef 5f3d6fe2 c745de65

64210519

e59c80e7 0fa7e9ab 72243049 feb8deec cl46b9bl

188da80e

b03090f6 7cbf20eb 43a 18800 f4ff0afd 82ffl012

07192b95

ffc8da78 63101 led 6b24cdd5 73f977al le794811

29

Curve P-224

p = 26959946667150639794667015087019630673557916\

260026308143510066298881

r= 26959946667150639794667015087019625940457807\

714424391721682722368061

5 = bd713447 99d5c7fc dc45b59f a3b9ab8f 6a948bc5

c — 5b056c7e Ildd68f4

0469ee7f 3c7a7d74 f7d 12111 6506d031 218291 fb

b = b4050a85 0c04b3ab

f5413256 5044b0b7 d7bfd8ba 270b3943 2355ffb4

Gx = b70e0cbd 6bb4bf7f

321390b9 4a03c 1 d3 56c21122 343280d6 115c 1 d21

Gy= bd376388 b5f723fb

4c22dfe6 cd4375a0 5a074764 44d58199 85007e34

30

Curve P-256

11579208921035624876269744694940757353008614\

3415290314195533631308867097853951

11579208921035624876269744694940757352999695\

5224135760342422259061068512044369

c49d3608 86e70493 6a6678el 139d26b7 819f7e90

7efbal66 2985be94 03cb055c

75d4f7e0 ce8d84a9 c5114abc aO 17768 0104fa0d

5ac635d8 aa3a93e7 b3ebbd55

769886bc 651d06b0 cc53b0f6 3bce3c3e 27d2604b

6bl7dlf2 el2c4247 f8bce6e5

63a440f2 77037d81 2deb33a0 f4a 13945 d898c296

4fe342e2 fela7f9b 8ee7eb4a

7c0f9e 16 2bce3357 6b315ece cbb64068 37bf51 f5

31

Curve P-384

p = 39402006196394479212279040100143613805079739\

27046544666794829340424572177149687032904726V

6088258938001861606973112319

r = 39402006196394479212279040100143613805079739V

27046544666794690527962765939911326356939895V

6308152294913554433653942643

5 = a335926a a319a27a 1 d00896a 6773a482 7acdac73

c = 79dle655 £868f02f

ff48dcde e 14151 dd b80643cl 406d0cal 0dfe6fc5

2009540a 495e8042 ea5f744f 6e 184667 cc722483

b= b3312fa7 e23ee7e4

988e056b e3f82dl9 181d9c6e fe814112 0314088f

5013875a c656398d 8a2edl9d 2a85c8ed d3ec2aef

G, = aa87ca22 be8b0537

8eblc71e f320ad74 6eld3b62 8ba79b98 59f741e0

82542a38 5502f25d bf55296c 3a545e38 72760ab7

Gy= 3617de4a 96262c6f

5d9e98bf 9292dc29 f8f41 dbd 289a 147c e9da3113

b5fOb8cO 0a60blce Id7e819d 7a431d7c 90ea0e5f

32

Curve P-521

p = 68647976601306097149819007990813932172694353\

00143305409394463459185543183397656052122559\

64066145455497729631139148085803712198799971\

6643812574028291115057151

r = 68647976601306097149819007990813932172694353\

00143305409394463459185543183397655394245057\

74633321719753296399637136332111386476861244\

0380340372808892707005449

^ - d09e8800 291 cb853 96cc6717 393284aa a0da64ba

c = 0b4 8bfa5f42

0a349495 39d2bdfc 264eeeeb 077688e4 4fbf0ad8

f6d0edb3 7bd6b533 28100051 8el9flb9 ffbe0fe9

ed8a3c22 00b8f875 e523868c 70cle5bf 55bad637

b= 051 953eb961

8e 1 c9a 1 f 929a21 aO b68540ee a2da725b 99b3150

b8b48991 8efl09el 56193951 ec7e937b 1652c0bd

3bb 1 bf07 3573df88 3d2c34fl ef451fd4 6b503f00

G,= c6 858e06b7

0404e9cd 9e3ecb66 2395b442 9c648139 053fb521

f828af60 6b4d3dba al4b5e77 efe75928 feldcl27

a2ffa8de 3348b3cl 856a429b f97e7e31 c2e5bd66

Gy = 118 39296a78

9a3bc004 5c8a5fb4 2c7dlbd9 98f54449 579b4468

17afbd 17 273e662c 97ee7299 5ef42640 c550b901

33

3fad0761 353c7086 a272c240 88be9476 9fd 16650

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: v2 + x y — x3 + x2 + b,

and the Koblitz curve has the form

Ea: y +xy=x + ax +1

where a = 0 or 1.

For each pseudorandom curve, the cofactor is/= 2. The cofactor of each

Koblitz curve is/= 2 if a = 1 and/= 4 if a = 0.

The coefficients ofthe pseudo-random curves, and the coordinates ofthe

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 jc coordinate G x

• The base point y coordinate G v

Pseudo-random curve:

• The base point order r

34

Pseudo-random curve (Polynomial Basis representation):

• The coefficient h

• The base point x coordinate G x

• The base point y coordinate G v

Pseudo-random curve (Normal Basis representation):

• The 160-bit input seed 5 to the SHA-1 based algorithm

• The coefficient b (i.e., the output ofthe SHA-1 based algorithm)

• The base point x coordinate G x

• The base point y coordinate G v

Integers (such as 7", m, and r) are given in decimal form; bit strings and

field elements are given in hex.

35

Degree 163 Binary Field

T = 4

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

Curve K-163

a = 1

r=5846006549323611672814741753598448348329118574063

Polynomial Basis:

Gx= 2 fe 13c053 7bbc 11 ac aa07d793 de4e6d5e 5c94eee8

Gy= 2 89070fb0 5d38ff58 321f2e80 0536d538 ccdaa3d9

Normal Basis:

G x = 0 5679b353 caa46825 fea2d371 3ba450da 0c2a4541

Gy= 2 35b7c671 00506899 06bac3d9 dec76a83 5591edb2

Curve B-163

r - 5846006549323611672814742442876390689256843201587

Polynomial Basis:

b= 2 0a601907 b8c953ca 1481ebl0 512f7874 4a3205fd

Gx= 3 fOeba 162 86a2d57e a0991168 d4994637 e8343e36

Gy= 0 d51 fbc6c 71 a0094f a2cdd545 b 11 c5c0c 797324f1

Normal Basis:

s = 85e25bfe 5c86226c dbl2016f 7553f9d0 e693a268

b = 6 645f3cac fl638el3 9c6cdl3e f61734fb c9e3d9fb

Gx= 0 311103c 1 7167564a ce77ccb0 9c681 f88 6ba54ee8

36

G v = 3 33ac 13c6 447f2e67 613bf700 9daf98c8 7bb50c7f

37

Degree 233 Binary Field

T= 2

p{t) = t 233 + t74 + 1

Curve K-233

a = 0

r =34508731733952818937173779311385127605709409888622521 \

26328087024741343

Polynomial Basis:

Gx =

Gv =

Normal Basis:

Gx =

Gv =

172 32ba853a 7e731afl

29f22ff4 149563a4 19c26bf5 0a4c9d6e efad6126

ldb 537dece8 19b7f70f

555a67c4 27a8cd9b fl8aeb9b 56e0cl 10 56fae6a3

Ofd e76d9dcd 26e643ac

26flaa90 laa 12978 4b71fc07 22b2d056 14d650b3

064 3e317633 155c9e04

47ba8020 a3c43177 450ee036 d6335014 34cac978

38

Curve B-233

r = 69017463467905637874347558622770255558398127373450135\

55379383634485463

Polynomial Basis:

b = 066 647ede6c 332c7f8c

0923bb58 213b333b 20e9ce42 81fel 15f 7d8f90ad

Gx= Ofa c9dfcbac 8313bb21

39flbb75 5fef65bc 391f8b36 f8f8eb73 71fd558b

Gy= 100 6a08a419 03350678

e58528be bfSaObef fS67a7ca 36716f7e 01 f81052

Normal Basis:

s = 74d59ffO 7f6b413d Oea 14b34 4b20a2db 049b50c3

6= laO 03e0962d 4f9a8e40

7c904a95 38163adb 82521260 0c7752ad 52233279

G x = 18b 863524b3 cdfefb94

f2784e0b 116faac5 4404bc91 62a363ba b84al4c5

Gy= 049 25df77bd 8b8ffla5

ff519417 822bfedf 2bbd7526 44292c98 c7af6e02

39

Degree 283 Binary Field

T= 6

pit) = t 283 +*12 + r7 + r5 + l

Curve K-283

a = 0

r = 38853377844514581418389238136470378132848117337930613\

24295874997529815829704422603873

Polynomial Basis:

Gx= 503213f78ca4488 3fla3b81 62fl88e5

53cd265f 23c 1567a 16876913 b0c2ac24 58492836

Gy = 1 ccda38 Of1 c9e31 8d90f95d 07e5426f

e87e45c0 e8184698 e4596236 4e341161 77dd2259

Normal Basis:

G x = 3ab9593 f8db09fc 188fl d7c 4ac9fcc3

e57fcd3b db 15024b 212c7022 9de5fcd9 2eb0ea60

Gy= 2118c47 55e7345c d8f603ef 93b98b 10

6fe8854f feb9a3b3 04634cc8 3a0e759f 0c2686bl

40

Curve B-283

r= 77706755689029162836778476272940756265696259243769048\

89109196526770044277787378692871

Polynomial Basis:

b = 27b680a c8b8596d a5a4af8a 19a0303f

ca97fd76 45309fa2 a581485a f6263e31 3b79a2f5

Gx = 5f93925 8db7dd90 e!934f8c 70b0dfec

2eed25b8 557eac9c 80e2el98 f8cdbecd 86bl2053

Gy = 3676854 fe24141c b98fe6d4 b20d02b4

516ff702 350eddb0 826779c8 13fOdf45 be8112f4

Normal Basis:

5 = 77e2b073 70eb0f83 2a6dd5b6 2dfc88cd 06bb84be

b = 157261b 894739fb 5al3503f 55f0b3fl

. 0c560116 66331022 01138cc 1 80c0206b dafbc951

Gx = 749468e 464ee468 634b21f7 f61cb700

701817e6 bc36a236 4cb8906e 940948ea a463c35d

Gy = 62968bd 3b489ac5 c9b859da 68475c31 5bafcdc4

ccd0dc90 5b70f624 46f49c05 2f49c08c

41

r = 4

Degree 409 Binary Field

pit) = t 409 + t87 + 1

Curve K-409

a = 0

r = 33052798439512429947595765401638551991420234148214060\

96423243950228807112892491910506732584577774580140963\

66590617731358671

Polynomial Basis:

G x =

Gv =

Normal Basis:

Gx =

060f05f 658f49cl ad3abl89

OH 18421 0efd0987 e307c84c 27accfb8 f9f67cc2

c460189e b5aaaa62 ee222ebl b35540cf e9023746

le36905 0b7c4e42 acbaldac

bf04299c 3460782f 918ea427 e6325165 e9eal0e3

da5f6c42 e9c55215 aa9ca27a 5863ec48 d8e0286b

Ib559c7 cba2422e 3affel33

43e808b5 5e012d72 6ca0b7e6 a63aeafb cle3a98e

lOcaOfcf 98350c3b 7f89a975 4a8eldc0 713cec4a

16d8c42 052f07e7 713e7490

efO 18ba labd6fef 8a5433c8 94b24f5c 817aeb79

852496fb ee803a47 bc8a2038 78ebflc4 99afd7d6

42

Curve B-409

r= 66105596879024859895191530803277103982840468296428121\

92846487983041577748273748052081437237621791109659798V

67288366567526771

Polynomial Basis:.

b = 021a5c2 c8ee9feb 5c4b9a75

3b7b476b 7fd6422e flOdd67 4761fa99 d6ac27c8

a9al97b2 72822f6c d57a55aa 4f50ae31 7bl3545f

G x = 15d4860 d088ddb3 496b0c60

64756260 441 cde4a f1771 d4d bO 1 ffe5b 34e59703

dc255a86 8a 118051 5603aeab 60794e54 bb7996a7

G v = 061 b 1 cf ab6be5D 2bbfa783

24edl06a 7636b9c5 a7bdl98d 0158aa4f 5488d08f

38514f1 f df4b4f40 d2181 b36 81 c364ba 0273c706

Normal Basis:

s = 4099b5a4 57f9d69f 79213d09 4c4bcd4d 426221 Ob

b = 124d065 Ic3d3772 f7f5alfe

6e715559 e2129bdfa04d52f7 b6ac7c53 2cf0ed06

f610072d 88ad2fdc c50c6fde 72843670 f8b3742a

G x = Oceacbc 9f475767 d8e69f3b

5dfab398 13685262 bcacf22b 84c7b6dd 981899e7

318c96f0 761f77c6 02c016ce d7c548de 830d708f

G y= 199d64b a8f089c6 db0e0b61

e80bb959 34afd0ca f2e8be76 dlc5e9affc7476df

43

49142691 ad303902 88aa09bc c59cl573 aa3c009a

44

Degree 571 Binary Field

T= 10

p(t) = r571 + /10 + /5 + ?2 + i

Curve K-571

<3=0

r=19322687615086291723476759454659936721494636648532174\

99328617625725759571144780212268133978522706711834706V

71280082535146127367497406661731192968242161709250355V

5733685276673

Polynomial Basis:

G v =

Normal Basis:

Gx =

26eb7a8 59923fbc 82189631

f8103fe4 ac9ca297 0012d5d4 60248048 01841ca4

43709584 93b205e6 47da304d b4ceb08c bbdlba39

494776fb 988b4717 4dca88c7 e2945283 aO 1 c8972

349dc80 7f4fbf37 4f4aeade

3bca9531 4dd58cec 9f307a54 ffcblefc 006d8a2c

9d4979c0 ac44aea7 4fbebbb9 f772aedc b620b01a

7ba7aflb 320430c8 591984f6 01cd4cl4 3eflc7a3

04bb2db a418d0db 107adae0

03427e5d 7ccl39ac b465e593 4f0bea2a b2f3622b

c29b3d5b 9aa7alfd fd5d8be6 6057c 100 8e71e484

bcd98f22 bf847642 37673674 29ef2ec5 bc3ebcf7

45

Gy = 44cbb57 de20788d 2c952d7b

56cf39bd 3e89bl89 84bdl24e 751ceff4 369dd8da

c6a59e6e 745df44d 8220ce22 aa2c852c fcbbef49

ebaa98bd 2483e331 80e04286 feaa2530 50caff60

46

Curve B-571

r = 38645375230172583446953518909319873442989273297064349V

98657235251451519142289560424536143999389415773083133\

88112192694448624687246281681307023452828830333241139V

3191105285703

Polynomial Basis:

b = 2f40e7e 2221 f295 de297117

b7f3d62f 5c6a97ff cb8ceffl cd6ba8ce 4a9al8ad

84ffabbd 8efa5933 2be7ad67 56a66e29 4afdl85a

78ffl2aa 520e4de7 39baca0c 7ffeff7f 2955727a

G v = 303001 d 34b85629 6c 16c0d4

0d3cd775 0a93dld2 955fa80a a5f40fc8 db7b2abd

bde53950 f4c0d293 cdd71 la3 5b67fbl4 99ae6003

8614f139 4abfa3b4 c850d927 ele7769c 8eec2dl9

G y = 37bf273 42da639b 6dccfffe

b73d69d7 8c6c27a6 009cbbca 1980f853 3921e8a6

84423e43 bab08a57 6291af8f 461bb2a8 b3531d2f

0485c 19b 16e2f151 6e23dd3c la4827af Ib8acl5b

Normal Basis:

s = 2aa058f7 3a0e33ab 486b0f61 0410c53a 7f132310

b = 3762d0d 47116006 179da356

88eeaccf 591a5cde a7500011 8d9608c5 9132d434

26101 a 1 d fb377411 5f586623 f75fOOOO lce61198

3c 1275fa 31 f5bc9f 4be 1 a0f4 67f01ca8 85c74777

G x = 0735e03 5def5925 cc33173e

47

b2a8ce77 67522b46 6d278b65 0a291612 7dfea9d2

d361089f 0a7a0247 a 184e 1 c7 0d417866 eOfeOfeb

0ff8f2f3 f9176418 f97dl 17e 624e2015 dfl662a8

G y = 04a3642 0572616c df7e606f

ccadaecf c3b76dab 0ebl248d d03fbdfc 9cd3242c

4726be57 9855e812 de7ec5c5 00b4576a 24628048

b6a72d88 0062eed0 dd34bl09 6d3acbb6 b01a4a97

48

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 ofthe 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 m 2, 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 ofterms. 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 ofthe five example curves is a generalized

Mersenne number.

49

Curve P-192:

The modulus for this curve is p = 2 192 - 2 64 - 1. Every integer A less than p~

can be written

A =A5 • 2320 + A4 • 2256 + A3 • 2192 + A2 • 2128 + At 264 + A0,

where each A, is a 64-bit integer. The expression for B is

B := T + S\ + S2 + Si mod p;

where the 192-bit terms are given by

T = A2 2128 +A\ 264 + Aq

S\ — At, 264 + At,

S2 = A4 2128 + A4 264

S3=A5-2l28+A5 264+A5.

50

Curve P-224:

The modulus for this curve is p = 2 224 - 2 % + 1. Every integer A less than

p2 can be written

A — A O416 , A ->384 , A ->352 , A ^320 , A ->288 , A ->256 . A ->224 , A-A\3-2 + A ,2-2 + A n-2 + ^i0-2 +Ag-2 + Ag-2 + A7-2 +

A6 • 2 + >45 • 2 + A4 • 2 + A3*2 + ^2*2 + ^1 • 2 +

where each /t, is a 32-bit integer. As a concatenation of 32-bit words, this can be

denoted by

A = {A\i // A\2 // // A0 ).

The expression for B is

B := T + S i + S 2 - D\ - D2 mod p,

where the 224-bit terms are given by

T = ( AIM, II 44II 43|| A2\\ A,\\A0)

5,=( ^10 ||4, || 1|^,|| 0 || 0 || 0 )

S2 = { 0 || A\31| A\ 21| A w || 0 || 0 || 0 )

D1 = (A 13 || v-i 12 II ^lllMloll Aq\\ Ag || Ay )

D2 = ( 0 || 0 || 0 || 0 \\An \\Al2\\ An).

51

Curve P-256:

The modulus for this curve is p — 2256 - 2224 + 2192 + 2% - 1. Every integer A

less than p2 can be written

A=A]5-2480+ A i4 2448 + Ajj • 24l6+ An-2384+ Air 2352 +

A}o- 2320+ - 2288+ /t8 - 2256 + /t7- 2224 + A6-2l92+ As-2l60 +

^4- 2128 + A3 - 296 + A2- 264+ /tr 232 + /to,

where each /t, is a 32-bit integer. As a concatenation of 32-bit words, this can be

denoted by

A = (An \\A\41| • • • || Aq ).

The expression for B is

B := T + 2S\ + 2S2 + S3 + S4 - D\ - D2 - D3 - D4 mod p,

where the 256-bit terms are given by

T = ( ^7 || A & || A5 || A4 || A3 || A 2 || A\ || Aq )

S\=( ^15 IM14 II 13 II 12 II ^11 II 0 || 0 || 0 )

S2 = ( 0 || ^15 Mull ^ 13 || ^ 12 || 0 || 0 || 0 )

•$3 = ( ^15 |Ml4 || 0 || 0 || 0 || ^10 || ^9 ||^8 )

S4 — ( A 8 13 || ^15 MuH 13 || /tn||^io|| Ag )

D\=( A\q

Di ~ ( A11

D3 ~ (A\2

C>4~{ A 13

^8

Ag

0 I

I ^ II 0 II 0 || ^13II ^12 II A\\ )

0 II 0 IMlS II A 14 || A\3 || 12 )

^ 10 II Ag || A8 MisIMull ^ 13 )

0 II ^11 II ^10 II Ag || 0 || /t 15 || A\4 ).

52

Curve P-384:

The modulus for this curve is/? = 2 384 - 2 128 - 2 96 + 2 32 - 1. Every integer A

less than p~ can be written

A=A23-2736+ A22 2?04 + A2r 2672+ A20 - 2640+ Aig- 2608 +

-<4i8• 2576+ Ax7 - 2544+ v416-25,2+ i415• 2480+ /t14- 2448+ ^13-24l6+ ^12

• 2384 + Au-2352+ /t10 • 2320+ ^-2288+ ^8 - 2256+ ^7-2224 +

Aft - 2 + A 5*2 +^4*2 + At, - 2 + Ai- 2 + A \ - 2 + /io,

where each A, is a 32-bit integer. As a concatenation of 32-bit words, this can be

denoted by

A = (A231| A221| • • • || Aq ).

The expression for B is

B T + 25"] + S2 + 5*3 + S4 + S5 + Ss - D\ - D2 - D3 mod /?,

where the 384-bit terms are given by

T = {A\ \ || A10 || Ag || As || A7 || A(, || As || A4 || A3 || A2 || A\ || A0 )

Sx=( 0 || 0 || 0 || 0 || 0 || ^23 || ^22|M2.||0 || 0 || 0 || 0)

52 = (A23 || A 22 \\A2\ || Aro || A\() || A 18 || ^17|| -4 16 II 1 s|| A\4 II A\3 || A 12)

53 = (A20 II A19 || A 18 \\A 17 || A 16 || ^ 15 || ^14 II ^13 IM 12 II ^23|| ^22|| ^2l)

S* — (Aw || A is || ^4171| A\t || A\s || A 1| A\3 || ^ 121| ^201| 0 || ^231| 0 )

Ss = { 0 || 0 II 0 || 0 IM23IM22M21IM20II o|| 01| 0 || 0 )

56 = ( 0 || 0 || 0 || 0 || 0 || 0 || A23 \\A22 \\A2x\\ 0 || 0 || A2G)

D\ = (A22 IM2I II A2o || A 19 || ^4 18 IMl7 II Ai6 || ^15 II ^14 || ^13 IM12IM23)

D2 = ( 0 II 0 II 0 II 0 II 0 II 0 II 0 II a23\\a22\\a2\\ a20 II 0)

D3=( 0 || 0 || 0 || 0 || 0 || 0 || 0 |M23 II ^23II 0II 0 || 0).

53

Curve P-521:

The modulus for this curve is/? = 2 >21 - 1. Every integer A less thanp2 can

be written

A-A\-2'~ + Aq,

The expression for B is

B :=A0 + Ai mod/?

54

APPENDIX 6.2: NORMAL BASES

The elements of GF{2m) are expressed in terms ofthe type T normal

basis 2 B for GF{2"'), for some T. Each element has a unique representation

as a bit string

(a0ai... amA )

The arithmetic operations are performed as follows.

Addition: addition oftwo elements is implemented by bitwise addition modulo 2.

Thus, for example,

(1100111) ^ (1010010) = (0110101).

Squaring: if

a = ( flo .. . am.i )

then

a2 = (amA a0ai ... am.2 )

Multiplication-, to perform multiplication, one first constructs a function F{u,v) on

inputs

u = ( u0 u\ . . . um. i ) and v = (v0vl... vmA )

as follows.

1. Set p <—Tm + 1

2. Let u be an integer having order T modulo p

2 It is assumed in this section that m is odd and T is even, since this is the only case considered in this standard.

55

3. Compute the sequence F(l); F(2F(p-\) as follows:

3.1 Set w<— 1

3.2 Fory from 0 to T-\ do

Set n <—w

For i from 0 to m-\ do

Set F(n) <— i

Set n <— 2n mod p

Set w <— uw mod p

4. Output the formula

p-2

F(ip v) := X Uffk+i) vF(p-k).

k=\

This computation need only be performed once per basis.

Given the function F for B, one computes the product

( Co c, . . . cm_i ) = ( a0 ax . . . am.x ) x ( b0 bx . .. bmA )

as follows.

1. Set ( wo ui . . . um.i ) <- ( w0 ax .. . amA )

2. Set ( v0 V! . . . vmA ) ( b0 bx . . . bmA )

3. For k from 0 to m - 1 do

3.1 Compute

ck := F(u, y)

3.2 Set u <— LeftShift (w) and v LeftShift (v), where LeftShift

denotes the circular left shift operation.

4. Output c := ( Co ci ... cmA )

56

EXAMPLE. For the type 4 normal basis for GF(27), one has p = 29 and

u = 12 or 17. Thus the values ofF are given by

F(1) = 0 F(8) = 3 F(15) = 6 F(22) = 5

F (2) = 1 F (9) = 3 F(16) = 4 F(23) = 6

F(3) = 5 F( 10) = 2 F (17) = 0 F(24)= 1

F (4) = 2 F (\ 1) = 4 F(18) = 4 F(25)= 2

F(5)= 1 F(12) = 0 F(19) = 2 F(26) = 5

F (6) = 6 F(13) = 4 F (20) = 3 F (27) = 1

F( 7) = 5 F(14) = 6 F(21) = 3 F(28)= 0

Therefore

F (u; y) = uq v\ + U\ (v0 + v2 + v5 + v6 ) + «2 (vi + v3 + v4 + v5)

+ W3 (v2 + V5 ) + U4 (v2 + v6 ) + U5 (V! + v2 + v3 + v6 )

+ u6 (V] + v4 + v5 + v6 ).

Thus, if

a = (1 0 1 0 1 1 1) and b = (1 10 0 0 0 1),

then

c0 = F( (1 0 1 0 1 1 1), (1 10000 1))=!,

C\ = F((0 1 0 1 1 1 1),(1 0000 1 1) ) = 0,

c6 = F(( 1 10 10 1 I); (1 1 1 0000))= 1,

so that c = ab = (1 0 1 10 0 1).

57

APPENDIX 6.3: SCALAR MULTIPLICATION ON KOBLITZ CURVES

This appendix describes a particularly efficient method of computing the

scalar multiple nP on the Koblitz curve Ea over GF(2m).

The operation ris defined by

r(x, y) = (x2, v2)

When the normal basis representation is used, then the operation r is

implemented by performing right circular shifts on the bit strings representing jc and

v.

Given m and a, define the following parameters:

• C is some integer greater than 5.

• H :=(-W'a

• For i = 0 and / = 1, define the sequence s,{m) by

5/(0) =0, 5/(1) =1-/,

s,(m) = /j • s,(m - 1) - 2 5,(w - 2) + (-1)'

• Define the sequence V{m)

F(0) = 2, V(\)=/J

V(m) = n • v{m -1) - 2 V(m - 2).

58

For the example curves, the quantities s,{m) and V(m) are as follows.

Cur\>e K-163:

5o( 163) = 2579386439110731650419537

sd 163) = -755360064476226375461594

K(163) = -4845466632539410776804317

Curve K-233:

50(233) = -27859711741434429761757834964435883

5,(233) = -44192136247082304936052160908934886

F(233) = -137381546011108235394987299651366779

Curve K-283:

50( 283) = -665981532109049041108795536001591469280025

5,(283)= 1155860054909136775192281072591609913945968

F(283)= 7777244870872830999287791970962823977569917

Curve K-409:

50(409) = -1830751045600238213781031719875646137859054248755686V

9338419259

5,(409) = -8893048526138304097196653241844212679626566100996606V

444816790

F(409)=l045728873731562592744768538704832073763879695768757V

5791173829

Curve K-571:

59

s0(571) = -373731944687646369242938589247611556714729396459613\

1024123406420235241916729983261305

^j(571) = -3191857706446416099583814595948959674131968912148564\

65861056511758982848515832612248752

V(511 )=-148380926981691413899619140297051490364542574180493\

936232912339534208516828973111459843

The following algorithm computes the scalar multiple nP on the Koblitz

curve Ea over GF(2m). The average number of elliptic additions and subtractions is

at most ~ 1 + (m/3), and is at most ~ ml3 with probability at least 1 - 25 C.

For / = 0 to 1 do

n'*~ L « /2‘"c*12J

g'<r- Si(m) n'

L g'l T J

j'<— V(m) h'

l'<r- Round((g'+yV2,m+5)/2)

k <— r/2c

f <— RoundfA,^

Hi b ~fi

hi <r- 0

r?<-2rj0+ p rji

If 77 >1

then

60

if Xj0 - 3 /i771 <-l

then set /?] 4- ^

else set hG <— 1

else

if r7o +4/j 7], >2

then set /?i <— n

If 7JC-1

then

if /7o - 3 ju r]x > 1

then set /7] <— /i

else set A0 <—1

else

if rio + 4 n rh < -2

then set h\ <— /u

<7i <-/i +/«i

r()<- n - (s0 + /us0 g0- 2s,

n <- 5i - 50 q\

Set Q O

Pq^P

While or rj ^0

If r() odd then

set u <— 2 - (r0 - 2 ^ mod 4)

set r0 <— r0 - u

61

if u = 1 then set Q <— Q + P0

if u = -1 then set Q <— Q - Po

Set Pq <— tPo

Set (r0 , n) <- (n + jur0 /2, - r0 /l)

Endwhile

Output Q

62
I
APPENDIX 6.4: GENERATION OF

PSEUDO-RANDOM CURVES (PRIME CASE)

Let / be the bit length of/?, and define

v =L(/- 1) /160j

w = l - 160v - 1

1. Choose an arbitrary 160-bit string 5.

2. Compute/?:= SHA-1(5).

3. Let hQ be the bit string obtained by taking the w rightmost bits of h.

4. Let z be the integer whose binary expansion is given by the 160-bit string s.

5. For i from 1 to v do:

5.1 Define the 160-bit string s, to be binary expansion ofthe integer

(z + /) mod (2 160 ).

5.2 Compute h, :=SHA-l(s,).

6. Let h be the bit string obtained by the concatenation of h0 , h\,..., hv as follows:

h=h0 UM---II hv

7. Let c be the integer whose binary expansion is given by the bit string h.

8.1fc = 0or4c + 27 = 0(mod /?), then go to Step 1.

9. Choose integers a, b e GF(p) such that

c b2 = a (mod p).

(The simplest choice is a = c and b = c. However, one may want to choose

differently for performance reasons.)

10. Check that the elliptic curve E over GF(p) given by y 2 =x3 + ax + b has

suitable order. If not, go to Step 1.

63
Il
APPENDIX 6.5: VERIFICATION OF CURVE

PSEUDO-RANDOMNESS (PRIME CASE)

Given the 160-bit seed value 5, one can verify that the coefficient b was

obtained from 5 via the cryptographic hash function SHA-1 as follows.

Let / be the bit length ofp, and define

v =[_(/- D/160J

w = l - 160v - 1

1. Compute h := SHA-IO).

2. Let ho be the bit string obtained by taking the w rightmost bits of h.

3. Let z be the integer whose binary expansion is given by the 160-bit string s.

4. For i from 1 to v do

4.1 Define the 160-bit string 5, to be binary expansion ofthe integer

(z + i) mod (2160 ).

4.2 Compute/?, :=SHA-1(5,).

5. Let h be the bit string obtained by the concatenation of h0, hu .. ., hv as follows:

h=h0 || hx || ... || K

6. Let c be the integer whose binary expansion is given by the bit string /?.

7. Verify that b~ c = -27 (mod p).

64

I APPENDIX 6.6: GENERATION OF

PSEUDO-RANDOM CURVES (BINARY CASE)

Let:

v = L (m- \)/B]

w = m - Bv

1. Choose an arbitrary 160-bit string s.

2. Compute h := SHA-l(s)

3. Let h0 be the bit string obtained by taking the w rightmost bits of h.

4. Let z be the integer whose binary expansion is given by the 160-bit string 5.

5. For i from 1 to v do:

5.1 Define the 160-bit string s, to be binary expansion ofthe integer

(z + z) mod (2160 ).

5.2 Compute/?, :=SHA-1(57).

6. Let h be the bit string obtained by the concatenation of h0, h\,..., hv as follows:

h=K || /i, ||...|\hv.

7. Let b be the element of GF(2m) which binary expansion is given by the bit string

h.

8. Choose an element a of GF(2m).

9. Check that the elliptic curve E over GF(2m) given by y: + xy =

x3 + ax2 + b has suitable order. If not, go to Step 1.

I

APPENDIX 6.7: VERIFICATION OF CURVE

PSEUDO-RANDOMNESS (BINARY CASE)

Given the 160-bit seed value 5, one can verify that the coefficient b was

obtained from 5 via the cryptographic hash function SHA-1 as follows.

Define

v = L (m - 1)/160J

w= m - 160v

1. Compute h := SHA-1 (s)

2. Let hQ be the bit string obtained by taking the w rightmost bits of h.

3. Let z be the integer whose binary expansion is given by the 160-bit string

4. For / from 1 to v do

4.1 Define the 160-bit string s, to be binary expansion of the integer (z

+ 0 mod (2160)

4.2 Compute /?, :=SHA-l(s, ).

5. Let h be the bit string obtained by the concatenation of ho, h\,..., hv as

follows:

h = ho || ||... || K.

6. Let c be the element of GF(2m ) which is represented by the bit string h.

7. Verify that c = b.

66
4
APPENDIX 6.8: POLYNOMIAL BASIS TO NORMAL BASIS CONVERSION

Suppose that a an element ofthe field GF{2m). Denote by p the bit string

representing 'Y with respect to a given polynomial basis. It is desired to compute n,

the bit string representing a with respect to a given normal basis. This is done via

the matrix computation

p r = n

Where F is an m-by-m matrix with entries in GF(2). The matrix T, which depends

only on the bases, can be computed easily given its second-to-last row. The

second-to-last row for each conversion is given in the table below.

Degree 163:

3 e 173bfaf 3a86434d 883a2918 a489ddbd 69fe84e 1

Degree 233:

Obe 19b89595 28bbc490

038f4bc4 da8bdfcl ca36bb05 853fd0ed 0ae200ce

Degree 283:

3347fl7 521fdabc 62ecl551 acfl56fb

0bceb855 f174d4c 1 7807511c 9f745382 add53bc3

Degree 409:

OebOOfZ ea95fd6c 64024e7f

0b68b81f 5ff8a467 acc2b4c3 b9372843 6265c7ff

67

a06d896c ae3a7e31 e295ec30 3eb9f769 de78bef5

Degree 571:

7940ffa ef996513 4d59dcbf

e5bf239b e4fe4b41 05959c5d 4d942ffd 46ea35f3

e3cdbOel 04a2aa01 cef30a3a 49478011 196bfb43

c55091b6 1174d7c0 8d0cdd61 3bf6748a bad972a4

Given the second-to-last row r of T, the rest ofthe matrix is computed as

follows. Let /} be the element of GF(2m) whose representation with respect to the

normal basis is r. Then the rows of T, from top to bottom, are the bit strings

representing the elements

/r-'./r-2,...,u2,u, i

with respect to the normal basis. (Note that the element 1 is represented by the all-1

bit string.)

Alternatively, the matrix is the inverse ofthe matrix described in Appendix

6.9.

More details ofthese computations can be found in Annex A.7 ofthe IEEE

PI363 standard.

68

APPENDIX 6.9: NORMAL BASIS TO POLYNOMIAL BASIS CONVERSION

Suppose that a an element ofthe field GF(2m). Denote by n the bit string

representing a with respect to a given normal basis. It is desired to compute p, the

bit string representing a with respect to a given polynomial basis. This is done via

the matrix computation

n r = p

where F is an m-by-m matrix with entries in GF(2). The matrix T, which depends

only on the bases, can be computed easily given its top row. The top row for each

conversion is given in the table below.

Degree 163:

7 15169c 10 9c612e39 0d347c74 8342bcd3 b02a0bef

Degree 233:

149 9e398ac5 d79e3685

59b35ca4 9bb7305d a6c0390b cf9e2300 253203c9

Degree 283:

31 e0ed7 91 c3282d c5624a72 0818049d

053e8c7a b8663792 be 1 d792e ba9867fc 7b317a99

Degree 409:

0dfa06b e206aa97 b7a41fff

b9b0c55f 8f048062 fbe8381b 4248adf9 2912ccc8

e3f91a24 elcfb395 0532b988 971c2304 2e85708d

69

Degree 571:

452186b bf5840a0 bcf8c9fO

2a54efa0 4e813b43 c3d41496 06c4d27b 487bfl07

393c8907 f79d9778 beb35ee8 7467d328 8274caeb

da6ce05a eb4ca5cf 3c3044bd 4372232f 2c 1 a27c4

Given the top row r of T, the rest ofthe matrix is computed as follows. Let (3

be the element of GF{2 m) whose representation with respect to the polynomial

basis is r. Then the rows of T, from top to bottom, are the bit strings representing

the elements

n ' 2 ' ^ ' 2"!'1

p.V , v “, .... v

with respect to the polynomial basis.

Alternatively, the matrix is the inverse ofthe matrix described in Appendix

6.8.

More details ofthese computations can be found in Annex A.7 of the IEEE

PI363 standard.

70
3'