A.2. Elliptic curves |
261 |
A.2 Elliptic curves
In the FIPS 186-2 standard, NIST recommended 15 elliptic curves of varying security levels for U.S. federal government use. The curves are of three types:
(i)random elliptic curves over a prime field F p;
(ii)random elliptic curves over a binary field F2m ; and
(iii)Koblitz elliptic curves over a binary field F2m .
Their parameters are listed in §A.2.1, §A.2.2 and §A.2.3, respectively.
In the tables that follow, integers and polynomials are sometimes represented as hexadecimal strings. For example, “0x1BB5” is the hexadecimal representation of the integer 7093. The coefficients of the binary polynomial z13 + z11 + z5 + z2 + z + 1 form a binary string “10100000100111” which has hexadecimal representation “0x2827”.
A.2.1 Random elliptic curves over F p
Table A.3 lists domain parameters for the five NIST-recommended randomly chosen elliptic curves over prime fields F p. The primes p were specially chosen to allow for very fast reduction of integers modulo p (see §2.2.6). The selection a = −3 for the coefficient in the elliptic curve equation was made so that elliptic curve points represented in Jacobian projective coordinates could be added using one fewer field multiplication (see §3.2.2). The following parameters are given for each curve:
p The order of the prime field F p.
S The seed selected to randomly generate the coefficients of the elliptic curve using Algorithm 4.17.
r The output of SHA-1 in Algorithm 4.17.
a, b The coefficients of the elliptic curve y2 = x3 + ax + b satisfying r b2 ≡ a3 (mod p).
n The (prime) order of the base point P. h The cofactor.
x, y The x and y coordinates of P.
A.2. Elliptic curves |
263 |
A.2.2 Random elliptic curves over F2m
Table A.4 lists domain parameters for the five NIST-recommended randomly chosen elliptic curves over binary fields F2m . The extension degrees m are prime and were selected so that there exists a Koblitz curve over F2m having almost-prime group order (see §A.2.3). Algorithm 4.19 was used to generate the coefficient b of an elliptic curve over F2m from the seed S. The output b of the algorithm was interpreted as an element of F2m represented with respect to the Gaussian normal basis specified in FIPS 186-2. A change-of-basis matrix was then used to transform b to a polynomial basis representation—see FIPS 186-2 for more details. The following parameters are given for each curve:
m The extension degree of the binary field F2m . f (z) The reduction polynomial of degree m.
SThe seed selected to randomly generate the coefficients of the elliptic curve.
a, b |
The coefficients of the elliptic curve y2 + x y = x3 + ax2 + b. |
n |
The (prime) order of the base point P. |
h |
The cofactor. |
x, y |
The x and y coordinates of P. |
A.2.3 Koblitz elliptic curves over F2m
Table A.5 lists domain parameters for the five NIST-recommended Koblitz curves over binary fields. The binary fields F2m are the same as for the random curves in §A.2.2. Koblitz curves were selected because point multiplication can be performed faster than for the random curves (see §3.4). The following parameters are given for each curve:
m The extension degree of the binary field F2m . f (z) The reduction polynomial of degree m.
a, b The coefficients of the elliptic curve y2 + x y = x3 + ax2 + b. n The (prime) order of the base point P.
h The cofactor.
x, y The x and y coordinates of P.
A.2. Elliptic curves |
265 |
K-163: m = 163, |
f (z) = z163 + z7 + z6 + z3 + 1, |
a = 1, b = 1, h = 2 |
|
|
|||
n = 0x 00000004 |
00000000 |
00000000 |
00020108 |
A2E0CC0D |
99F8A5EF |
|
|
x = 0x 00000002 |
FE13C053 7BBC11AC AA07D793 DE4E6D5E 5C94EEE8 |
|
|
||||
y = 0x 00000002 |
89070FB0 5D38FF58 321F2E80 0536D538 CCDAA3D9 |
|
|
||||
K-233: m = 233, |
f (z) = z233 + z74 + 1, |
a = 0, b = 1, h = 4 |
|
|
|
||
n = 0x 00000080 |
00000000 |
00000000 |
00000000 |
00069D5B B915BCD4 6EFB1AD5 F173ABDF |
|||
x = 0x 00000172 |
32BA853A 7E731AF1 29F22FF4 149563A4 19C26BF5 0A4C9D6E EFAD6126 |
||||||
y = 0x 000001DB |
537DECE8 |
19B7F70F 555A67C4 27A8CD9B F18AEB9B 56E0C110 56FAE6A3 |
|||||
K-283: m = 283, |
f (z) = z283 + z12 + z7 + z5 + 1, |
a = 0, b = 1, h = 4 |
|
|
|||
n = 0x 01FFFFFF |
FFFFFFFF |
FFFFFFFF FFFFFFFF FFFFE9AE |
2ED07577 |
265DFF7F |
94451E06 |
||
1E163C61 |
|
|
|
|
|
|
|
x = 0x 0503213F |
78CA4488 |
3F1A3B81 62F188E5 53CD265F |
23C1567A |
16876913 |
B0C2AC24 |
||
58492836 |
|
|
|
|
|
|
|
y = 0x 01CCDA38 |
0F1C9E31 |
8D90F95D 07E5426F E87E45C0 |
E8184698 |
E4596236 |
4E341161 |
||
77DD2259 |
|
|
|
|
|
|
|
K-409: m = 409, |
f (z) = z409 + z87 + 1, |
a = 0, b = 1, h = 4 |
|
|
|
||
n = 0x 007FFFFF |
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFE5F 83B2D4EA |
||||||
20400EC4 |
557D5ED3 |
E3E7CA5B 4B5C83B8 E01E5FCF |
|
|
|
||
x = 0x 0060F05F |
658F49C1 AD3AB189 0F718421 0EFD0987 E307C84C 27ACCFB8 F9F67CC2 |
||||||
C460189E |
B5AAAA62 |
EE222EB1 B35540CF E9023746 |
|
|
|
||
y = 0x 01E36905 |
0B7C4E42 ACBA1DAC BF04299C 3460782F 918EA427 E6325165 E9EA10E3 |
||||||
DA5F6C42 |
E9C55215 |
AA9CA27A 5863EC48 D8E0286B |
|
|
|
||
K-571: m = 571, |
f (z) = z571 + z10 + z5 + z2 + 1, |
a = 0, b = 1, h = 4 |
|
|
|||
n = 0x 02000000 |
00000000 |
00000000 00000000 00000000 |
00000000 |
00000000 |
00000000 |
||
00000000 |
131850E1 |
F19A63E4 B391A8DB 917F4138 |
B630D84B |
E5D63938 |
1E91DEB4 |
||
5CFE778F |
637C1001 |
|
|
|
|
|
|
x = 0x 026EB7A8 |
59923FBC 82189631 F8103FE4 AC9CA297 0012D5D4 60248048 01841CA4 |
||||||
43709584 |
93B205E6 47DA304D B4CEB08C BBD1BA39 494776FB 988B4717 4DCA88C7 |
||||||
E2945283 |
A01C8972 |
|
|
|
|
|
|
y = 0x 0349DC80 |
7F4FBF37 4F4AEADE 3BCA9531 4DD58CEC 9F307A54 FFC61EFC 006D8A2C |
||||||
9D4979C0 |
AC44AEA7 4FBEBBB9 F772AEDC B620B01A 7BA7AF1B 320430C8 591984F6 |
||||||
01CD4C14 |
3EF1C7A3 |
|
|
|
|
|
|
Table A.5. NIST-recommended Koblitz curves over binary fields.
This page intentionally left blank
APPENDIX B
ECC Standards
Cryptographic standards are important for two reasons: (i) to facilitate the widespread use of cryptographically sound and well-specified techniques; and (ii) to promote interoperability between different implementations. Interoperability is encouraged by completely specifying the steps of the cryptographic schemes and the formats for shared data such as domain parameters, keys and exchanged messages, and by limiting the number of options available to the implementor.
This section describes the salient features of selected standards and draft standards that describe elliptic curve mechanisms for signatures, encryption, and key establishment. A summary is provided in Table B.1. Electronic copies of the standards can be obtained online from the web sites listed in Table B.2. It should be noted that many of these standards are updated periodically. Readers should consult the web sites for the latest drafts.
American National Standards Institute (ANSI) The ANSI X9F subcommittee of the ANSI X9 committee develops information security standards for the financial services industry. Two elliptic curve standards have been completed: ANSI X9.62 which specifies the ECDSA (§4.4.1), and ANSI X9.63 which specifies numerous elliptic curve key agreement and key transport protocols including STS (§4.6.1), ECMQV (§4.6.2), and ECIES (§4.5.1). The objective of these standards is to achieve a high degree of security and interoperability. The underlying finite field is restricted to being a prime field F p or a binary field F2m . The elements of F2m may be represented using a polynomial basis or a normal basis over F2. If a polynomial basis is desired, then the reduction polynomial must be an irreducible trinomial, if one exists, and an irreducible pentanomial otherwise. To facilitate interoperability, a specific reduction polynomial is recommended for each field F2m ; these polynomials of degree m, where 2 ≤ m ≤ 600, are listed in Tables A.1 and A.2. If a normal basis is desired, a specific Gaussian normal
B. ECC Standards |
269 |
basis is mandated. The primary security requirement is that the order n of the base point P should be greater than 2160. The only hash function employed is SHA-1; however, it is anticipated that ANSI X9.62 and X9.63 will be updated in the coming years to allow for hash functions of varying output lengths.
National Institute of Standards and Technology (NIST) NIST is a non-regulatory federal agency within the U.S. Commerce Department’s Technology Administration. Included in its mission is the development of security-related Federal Information Processing Standards (FIPS) intended for use by U.S. federal government departments. The FIPS standards widely adopted and depolyed around the world include the Data Encryption Standard (DES: FIPS 46), the Secure Hash Algorithms (SHA-1, SHA-256, SHA-384 and SHA-512: FIPS 180-2 [138]), the Advanced Encryption Standard (AES: FIPS 197 [141]), and Hash-based Message Authentication Code (HMAC: FIPS 198 [142]). FIPS 186-2, also known as the Digital Signature Standard (DSS), specifies the RSA, DSA and ECDSA signature schemes. ECDSA is specified simply by reference to ANSI X9.62 with a recommendation to use the 15 elliptic curves listed in §A.2.1, §A.2.2 and §A.2.3. NIST is in the process of developing a recommendation [342] for elliptic curve key establishment schemes that will include a selection of protocols from ANSI X9.63.
Institute of Electrical and Electronics Engineers (IEEE) The IEEE P1363 working group is developing a suite of standards for public-key cryptography. The scope of P1363 is very broad and includes schemes based on the intractability of integer factorization, discrete logarithm in finite fields, elliptic curve discrete logarithms, and lattice-based schemes. The 1363-2000 standard includes elliptic curve signature schemes (ECDSA and an elliptic curve analogue of a signature scheme due to Nyberg and Rueppel), and elliptic curve key agreement schemes (ECMQV and variants of elliptic curve Diffie-Hellman (ECDH)). It differs fundamentally from the ANSI standards and FIPS 186-2 in that there are no mandated minimum security requirements and there is an abundance of options. Its primary purpose, therefore, is to serve as a reference for specifications of a variety of cryptographic protocols from which other standards and applications can select. The 1363-2000 standard restricts the underlying finite field to be a prime field F p or a binary field F2m . The P1363a draft standard is an addendum to 1363-2000. It contains specifications of ECIES and the Pintsov-Vanstone signature scheme providing message recovery, and allows for extension fields F pm of odd characteristic including optimal extension fields (see §2.4).
International Organization for Standardization (ISO) ISO and the International Electrotechnical Commission (IEC) jointly develop cryptographic standards within the SC 27 subcommittee. ISO/IEC 15946 is a suite of elliptic curve cryptographic standards that specifies signature schemes (including ECDSA and EC-KCDSA), key establishment schemes (including ECMQV and STS), and digital signature schemes providing message recovery. ISO/IEC 18033-2 provides detailed descriptions and se-
270 B. ECC Standards
curity analyses of various public-key encryption schemes including ECIES-KEM and PSEC-KEM.
Standards for Efficient Cryptography Group (SECG) SECG is a consortium of companies formed to address potential interoperability problems with cryptographic standards. SEC 1 specifies ECDSA, ECIES, ECDH and ECMQV, and attempts to be compatible with all ANSI, NIST, IEEE and ISO/IEC elliptic curve standards. Some specific elliptic curves, including the 15 NIST elliptic curves, are listed in SEC 2.
New European Schemes for Signatures, Integrity and Encryption (NESSIE) The NESSIE project was funded by the European Union’s Fifth Framework Programme. Its main objective was to assess and select various symmetric-key primitives (block ciphers, stream ciphers, hash functions, message authentication codes) and public-key primitives (public-key encryption, signature and identification schemes). The elliptic curve schemes selected were ECDSA and the key transport protocols PSEC-KEM and ACE-KEM.
Cryptographic Research and Evaluation Committee (CRYPTREC) The Inform- ation-technology Promotion Agency (IPA) in Japan formed the CRYPTREC committee for the purpose of evaluating cryptographic protocols for securing the Japanese government’s electronic business. Numerous symmetric-key and public-key primitives are being evaluated, including ECDSA, ECIES, PSEC-KEM and ECDH.