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.
<draft-kato-pkix-ecc-oef-00.txt>
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]