PKIX Working Group A. Kato Internet Draft NTT Software Corporation Expiration Date: October 2003 T. Kobayashi NTT Corporation T. Saito NTT Corporation April 2003 Use of the Odd Characteristic Extension Field in the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. Status of this Memo This document is an Internet-Draft and is in full conformance with all provisions of Section 10 of RFC2026. Internet-Drafts are working documents of the Internet Engineering Task Force (IETF), its areas, and its working groups. Note that other groups may also distribute working documents as Internet- Drafts. Internet-Drafts are draft documents valid for a maximum of six months and may be updated, replaced, or obsoleted by other documents at any time. It is inappropriate to use Internet-Drafts as reference material or to cite them other than as "work in progress." The list of current Internet-Drafts can be accessed at http://www.ietf.org/ietf/1id-abstracts.txt The list of Internet-Draft Shadow Directories can be accessed at http://www.ietf.org/shadow.html. Comments or suggestions for improvement may be made on the "ietf-pkix" mailing list, or directly to the author. 1. Introduction This document specifies algorithm identifiers and ASN.1 [X.660] encoding formats for additional elliptic curve field for digital signatures and subject public keys used in the Internet X.509 Public Key Infrastructure (PKI). This specification supplements [RFC 3280], "Internet X.509 Public Key Infrastructure: Certificate and Certificate Revocation List (CRL) Profile." and [RFC3279] "Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile. " Implementations of this specification MUST also conform to RFC 3280 and RFC 3279. In RFC 3279 only prime-field and two-characteristic-field were used as field which defines an elliptic curve. This document introduce A. Kato, et al. [Page 1] INTERNET-DRAFT Use of OEF June 2003 odd-characteristic-extension-field as the 3rd field. An odd-characteristic-extension-field is a finite field whose number of elements is a power of an odd prime. For any positive integer m , there is a unique field (up to isomorphism) GF(p^m) with p^m elements. For purposes of conversion, the elements of GF(p^m) shall be represented in a polynomial basis and converted to integers in the set {0, 1, ... , p^m-1} as follows. The polynomial basis representation is determined by choosing a polynomial f(t) of degree m irreducible over GF(p). Then GF(p^m) is isomorphic to GF(p)[t]/(f(t)). The element with representation a_{m-1}*t^{m-1} + ... + a_2*t^2 + a_1*t+ a_0 shall be represented by the integer a_{m-1}*p^{m-1} + ... + a_2*p^2 + a_1*p + a_0. The so-called Optimal Extension Field (OEF) [Bailey] is an odd characteristic extension field such that: 1. p is a pseudo-Mersenne prime, a positive rational integer of the form 2^n-c, log_2(c) < |floor(n/2)|. 2. An irreducible binomial f(t) = t^m-w exists over prime filed. The characteristic p is often chosen based on the implementation platform. Thus, for a machine with efficient 32-bit arithmetic, one would choose p slightly less than 2^32. On the following text, the parameters of odd-characteristic field are chosen as OEF. This specification defines the new field type of the elliptic curve. This document also specifies recommened ellipitic curve over odd characteristic extension field. 1.1 Terminology The key words "MUST", "MUST NOT", "REQUIRED", "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this document (in uppercase, as shown) are to be interpreted as described in [RFC2119]. 2 Odd Characteristic Extension Field This section provides the recommended ASN.1 syntax to identify finite fields and field elements. The identity of a finite field and a specific field element therein may need to be specified, for example, as part of some elliptic curve domain parameters. The syntax follows RFC 3279 [Section 3]. The finite fields of interest in this document are OEF. A finite field is identified by a value of type FieldID: id-fieldType OBJECT IDENTIFIER ::= { ansi-X9-62 fieldType(1) } We add third field type namely, Odd-characteristic-extention field. A. Kato, et al. [Page 2] INTERNET-DRAFT Use of OEF June 2003 FieldTypes FIELD-ID ::= { { Prime-p IDENTIFIED BY prime-field } | { Characteristic-two IDENTIFIED BY characteristic-two-field } { Odd-characteristic-extention IDENTIFIED BY odd-characteristic-extension-field } } A odd characteristic extension field is specified by the identifier odd-characteristic-extension-field comprising prime number, extension degree, n and c of pseudo mersenne prime. Odd-characteristic-extension-field OBJECT IDENTIFIER ::= { id-fieldType 3 } Odd-characteristic-extention ::= SEQUENCE { p INTEGER, -- Characteristic m INTEGER, -- Extension degree n INTEGER, OPTIONAL -- n of pseudo mersenne prime p = 2^n -c c INTEGER, OPTIONAL -- c of pseudo mersenne prime p = 2^n -c } A field element and an elliptic curve point are represented by the following type FieldElement ::= OCTET STRING ECPoint ::= OCTET STRING The value of FieldElement SHALL be the octet string representation of a field element following the conversion routine in [p1363a], Section 5.5.4. The value of ECPoint SHALL be the octet string representation of an elliptic curve point following the conversion routine in [p1363a], Section 5.5.6. Note that this octet string may represent an elliptic curve point in compressed or uncompressed form. Implementations that support elliptic curve according to this specification MUST support the uncompressed form and MAY support the compressed form. 3. Recommended Elliptic Curve Domain Parameters over Optimal Extension Field This section specifies the elliptic curve domain parameters over odd characteristic extension field recommended in this document. The elliptic curve domain parameters over optimal extension field are specified by set of seven numbers: (p;m;w;a;b;N;G) consisting of an integer p specifying characteristic prime, two elements a,b specifying elliptic curve defined by equation y^2 = x^3 + ax + b, a base point G on equation y^2 = x^3 + ax + b which is represented by ECP2OSP in [P1363a], a prime N which is order of G, an integer m specifying extension degree, an integer w specifying w of minimal polynomial: f(x) = x^m - w. A. Kato, et al. [Page 3] INTERNET-DRAFT Use of OEF June 2003 3.1 Recommended Parameters oef16_168 An optimal extension field parameters and an elliptic curve domain parameters over odd characteristic extension curve oef16_168 are defined by: p = 2^14-3 m = 13 w = 2 a = -3 b = -172 N = 0102 3247AFD7 715B303B 806CDB49 E6F23F09 9B55AC89 G = 042A5D 61239F4E A5357B63 754CAF12 C5348D9A AEE5B24A 7E22C8F7 DA1842EF BEB2D5D0 4888F562 E7BF2F33 D7D20DFC 3.2 Recommended Parameters oef32_174 An optimal extension field parameters and an elliptic curve domain parameters over odd characteristic extension curve oef32_174 are defined by: p = 2^29-3 m = 7 w = 2 a = -3 b = -85 N = 00004001 2E3D9401 6C815A2E AF1E63AD F3754413 FF83C6D9 G = 04053D F088F45F 0B07B23B 434DDB4E 13952AE2 89822CEA DCEE7E92 A61E99F8 6772F3F2 010E80DA AF0C75F5 491C922A 6129624A 0C68706B 6F9EAE42 7D7EDCBA 44CA6838 1B9AF47A 714DD12E 76DA116A 40EDD527 CCF73207 3.3 Recommended Parameters oef16_234 An optimal extension field parameters and an elliptic curve domain parameters over odd characteristic extension curve oef16_234 are defined by: p = 2^13-21 m = 19 w = 2 a = -3 b = 73 N = 03E4 2CC7629B 72A7B701 B7C49F01 2FF44C6D F9EEFB85 F955D325 5458315F G = 040368 1D81EA08 842260D2 0D87158D 4F2CA4D9 89864D44 F643B07C A8B0F8CF 2F18E3AE 6ED5C034 07C311E8 D0FCFA61 BDAF9671 B50635D3 2D744BC7 BED08AA1 3.4 Recommended Parameters oef32_310 An optimal extension field parameters and an elliptic curve domain parameters over odd characteristic extension curve oef16_310 are A. Kato, et al. [Page 4] INTERNET-DRAFT Use of OEF June 2003 defined by: p = 2^31-1 m = 11 w = 3 a = -3 b = -68 N = 003FFFD4 B91D3FEB 1C1E9E7B 5C2EEBD5 49875641 6189C111 B8C996FB 6A8C8B6B 690E23EC CBD6F237 G = 04053D F088F45F 0B07B23B 434DDB4E 13952AE2 89822CEA DCEE7E92 A61E99F8 6772F3F2 010E80DA AF0C75F5 491C922A 6129624A 0C68706B 6F9EAE42 7D7EDCBA 44CA6838 1B9AF47A 714DD12E 76DA116A 40EDD527 CCF73207 3.5 Recommended Parameters oef16_360 An optimal extension field parameters and an elliptic curve domain parameters over odd characteristic extension curve oef16_360 are defined by: p = 2^12-3 m = 31 w = 2 a = -3 b = -29 N = 00FC F7E53BD0 F765CAAE 0D3A8790 51D0C477 1FD3E8CB 5E09CEE5 85E8EA95 8921DEE3 89A2AC13 C6D87CC5 8F7F5C95 G = 0401CB 69857849 F0DF7808 69759B33 64AA7E55 2096BCBD EBF6D5F8 BEFAFFB2 29FF228B 6838E75E 85296275 0BED0BFA D60F8905 403AD402 2BF076AE 523877A1 072CFDB3 941F6989 C72DDB61 B1110E5B C33A186C F9C810EC 324879AD 9297630E 3.6 Recommended Parameters oef32_522 An optimal extension field parameters and an elliptic curve domain parameters over odd characteristic extension curve oef32_522 are defined by: p = 2^29-33 m = 19 w = 2 a = -3 b = -213 N = 03FF F9EAA8CC 2A1E0D90 3EE567E7 9E451643 C5A7BC27 BB23F069 D8F445BF 0A5A8ECA 344BBF43 A69E93AB 88849CA5 AE1887A9 374FC202 E221A91E 9809809C 134E25B3 G = 0460F8 E6E06621 E454B36F EC7322F8 BCCDE33C F3046BB8 ACFBA5E4 53ED6949 78BA0AD8 3C9CCF0B 055A217A 481E6AE8 9E496A5B 73241EE2 FF4BCBF1 783DCAD5 8BD11348 E4910C3C A701D24B 099BB477 164B92B5 AF03DA2C 09000E6F 37FF88B6 4DB5E8B2 5426054A 3C4F8772 010D11F9 07A30623 E6137185 C8B54799 674511A0 848877BD F73AE2C7 96725B21 3.7 Recommended Parameters oef16_546 A. Kato, et al. [Page 5] INTERNET-DRAFT Use of OEF June 2003 An optimal extension field parameters and an elliptic curve domain parameters over odd characteristic extension curve oef32_522 are defined by: p = 2^13-21 m = 43 w = 2 a = -3 b = -53 N = 03 93E0381E BF31E130 6CD7D3BB F5E4B2C4 32FA72AE C75160F0 AF14CD88 E6F9C87C 72FE7FAC 9BB6730B 5E083EBB 4C6A0FB5 24CEA664 8DD306FB 60C6E881 52EF8EF5 12C2C21B G = 04 0573F290 F4433237 2DA74E04 F26350FB 3BEB6FAD FA5B608F 8B6B35E2 2694CF80 F5546AC0 3712F084 18A567CF 7BFCEB62 CBE8B931 A2F7814F F1AC7FB0 6F97BC9B 92A8FA25 6EB92038 6F9DF4D3 7CAE9239 AB9A7365 44C9212D E03D6DA2 8C58307E DAE28110 AEDE56FD EE7391A0 1F4A533A 56549037 A08C6027 BD29B311 992949AA F7D308EE 792BC08C 5D445E63 4. Data Conversion This section specifies operations that convert between field elements to integers and opposite one. Other conversion (I2OSP, OS2ECP, etc.) are specified by [P1363a]. 4.1 Field Element-to-Integer Conversion(FE2IP) Field elements should be converted to integers as described in this section. A field element should be represented as a polynomial with integer coefficients, which can be represented as a sequence of the coefficients. Informally, the idea is simply to view the sequence of the coefficients as the radix-p representation of the integer, where p is the characteristic of the field. Formally, the conversion routine, FE2IP(a), is specified as follows: System Parameters: GF(p^m) : a finite field with p^m elements where p is a prime, and m > 0 is an integer Input: a : a field element in GF(p^m) Output: x : an integer in {0, . . . , p^m - 1} Steps: Convert field element a to integer x as follows: if m = 1: Field element a must be represented as an integer in {0, . . . , p^m-1}. 1: Let x := a. 2: Output x. if m > 1: Field element a must be represented as a polynomial of at most (m-1)-th degree with coefficients in {0, . . . , p-1}. Let b be the variable of the polynomial. 1: Determine the coefficients a[i] where element of {0, . . . , p-1} . A. Kato, et al. [Page 6] INTERNET-DRAFT Use of OEF June 2003 a = a[m-1]*b^(m-1) + .... + a[1]*B + a[0]. 2: Compute x = a[m-1]*p^(m-1) + .... + a[1]*p + a[0]. 3: Output x. 4.2 Integer-to-Field Element Conversion(I2FEP) Integers should be converted to field elements as described in this section. A field element should be represented as a polynomial with integer coefficients, and it can be represented as a sequence of the coefficients. Informally, the idea is to represent the integer with radix-p positional number system where p is the characteristic of the field, and then convert the each digit to the each coefficient of the polynomial. Formally, the conversion routine, I2FEP(x), is specified as follows: System Parameters: GF(p^m) : a finite field with p^m elements where p is a prime, and m > 0 is an integer Input: x : an integer in {0, . . . , p^m - 1} Output: a : a field element in GF(p^m) Steps: Convert integer x to field element a as follows: if m = 1: A field element of GF(p^m) must be represented as an integer in {0, . . . , p^m - 1}. 1: Let a := x. 2: Output a. if m > 1: A field element of GF(p^m) must be represented as a polynomial of at most (m-1)-th degree with coefficients in {0, . . . , p-1}. Let b be the variable of the polynomial. 1: Write x in radix-p as follows: x = x[m-1]*p^(m-1) + . . . . + x[1]*p + x[0] where the digits x[i]'s .are elements in {0, . . . , p - 1}. 2: Compute a = x[m-1]*b^(m-1) + . . . . + x[1]*p + x[0]. 3: Output a. 5 ASN.1 Module OddCharacteristicExtensionField { To be defined later } DEFINITIONS EXPLICIT TAGS ::= BEGIN -- EXPORTS All; IMPORTS Parameters FROM PKIX1Algorithms88; -- where fieldType is odd-characteristic-extension-field, the A. Kato, et al. [Page 7] INTERNET-DRAFT Use of OEF June 2003 -- parameters are of type Odd-characteristic Odd-characteristic-extension-field OBJECT IDENTIFIER ::= { id-fieldType 3 } Odd-characteristic-extension ::= SEQUENCE { p INTEGER, -- Characteristic m INTEGER, -- Extension degree n INTEGER, OPTIONAL -- n of pseudo mersenne prime p = 2^n-c c INTEGER, OPTIONAL -- c of pseudo mersenne prime p = 2^n-c } odd-characteristic-extension OBJECT IDENTIFIER ::= { ellipticCurve oddCharacteristicExtension(3) } oef16_168 OBJECT IDENTIFIER ::= { oddCharacteristicExtension 1 } oef32_174 OBJECT IDENTIFIER ::= { oddCharacteristicExtension 2 } oef16_234 OBJECT IDENTIFIER ::= { oddCharacteristicExtension 3 } oef32_310 OBJECT IDENTIFIER ::= { oddCharacteristicExtension 4 } oef16_360 OBJECT IDENTIFIER ::= { oddCharacteristicExtension 5 } oef32_522 OBJECT IDENTIFIER ::= { oddCharacteristicExtension 6 } oef16_546 OBJECT IDENTIFIER ::= { oddCharacteristicExtension 7 } END 6 Security Considerations This specification does not constrain the size of public keys or their parameters for use in the Internet PKI. However, the key size selected impacts the strength achieved when implementing cryptographic services. Selection of appropriate key sizes is critical to implementing appropriate security. This specification does not identify particular elliptic curves for use in the Internet PKI. However, the particular curve selected impact the strength of the digital signatures. Some curves are cryptographically stronger than others! This specification supplements RFC 3280 and RFC 3279. The security considerations section of that document applies to this specification as well. 7. Intellectual Property Statement The IETF has been notified of intellectual property rights claimed in regard to some or all of the specification contained in this document. For more information consult the online list of claimed rights. The IETF takes no position regarding the validity or scope of any intellectual property or other rights that might be claimed to pertain to the implementation or use of the technology described in this document or the extent to which any license under such rights might or might not be available; neither does it represent that it A. Kato, et al. [Page 8] INTERNET-DRAFT Use of OEF June 2003 has made any effort to identify any such rights. Information on the IETF's procedures with respect to rights in standards-track and standards- related documentation can be found in BCP-11. Copies of claims of rights made available for publication and any assurances of licenses to be made available, or the result of an attempt made to obtain a general license or permission for the use of such proprietary rights by implementors or users of this specification can be obtained from the IETF Secretariat. 8. References [P1363a] IEEE, P1363a "Draft Standard Specifications for Public Key Cryptography Amendment 1: Additional Techniques", 12 May 2003. [RFC3279] W. Polk, R. Housley, L. Bassham, "Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", April 2002. [RFC3280] Housley, R., Polk, W., Ford, W. and D. Solo, "Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile", RFC 3280, April 2002. [Bailey] D. V. Bailey, C. Paar, "Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms". CRYPTO 1998. [X.660] ITU-T Recommendation X.660 Information Technology - ASN.1 encoding rules: Specification of Basic Encoding Rules (BER), Canonical Encoding Rules (CER) and Distinguished Encoding Rules (DER), 1997. 9. Authors' Address Akihiro Kato NTT Software Corporation Phone: +81-45-212-7404 FAX: +81-45-212-7410 Email: akato@po.ntts.co.jp Tetutaro Kobayashi Nippon Telegraph and Telephone Corporation Phone: +81-468-59-2007 FAX: +81-468-59-3858 Email: kotetsu@isl.ntt.co.jp Taiichi Saito Nippon Telegraph and Telephone Corporation Phone: +81-468-59-2532 FAX: +81-468-59-3858 Email: taiichi@sucaba.isl.ntt.co.jp 10. Full Copyright Statement Copyright (C) The Internet Society (2003). All Rights Reserved. A. Kato, et al. [Page 9] INTERNET-DRAFT Use of OEF June 2003 This document and translations of it may be copied and furnished to others, and derivative works that comment on or otherwise explain it or assist in its implementation may be prepared, copied, published and distributed, in whole or in part, without restriction of any kind, provided that the above copyright notice and this paragraph are included on all such copies and derivative works. However, this document itself may not be modified in any way, such as by removing the copyright notice or references to the Internet Society or other Internet organizations, except as needed for the purpose of developing Internet standards in which case the procedures for copyrights defined in the Internet Standards process must be followed, or as required to translate it into languages other than English. The limited permissions granted above are perpetual and will not be revoked by the Internet Society or its successors or assigns. This document and the information contained herein is provided on an "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. A. Kato, et al. [Page 10]