Standards for Efficient Cryptography

SEC X.1: Supplemental Document
for Odd Characteristic Extension Fields
Nippon Telephone and Telegraph Corporation
Contact: Kazumaro Aoki, Tetsutaro Kobayashi, and Akira Nagai(publickey@lab.ntt.co.jp)
Working Draft
May 8, 2009
Version 0.7
c NTT 2008-2009

CONTENTS

CONTENTS

Contents
1 Introduction

3

2 Mathematical Foundations
2.1 Finite Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.X The Finite Field Fpm . . . . . . . . . . . . . . . . . . . . .
2.2 Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.X Elliptic Curves over Fpm . . . . . . . . . . . . . . . . . . .
2.3 Data Types and Conversions . . . . . . . . . . . . . . . . . . . . .
2.3.3 Elliptic-Curve-Point-to-Octet-String-Conversion . . . . . .
2.3.4 Octet-String-to-Elliptic-Curve-Point Conversion . . . . . .
2.3.5 Field-Element-to-Octet-String Conversion . . . . . . . . .
2.3.6 Octet-String-to-Field-Element Conversion . . . . . . . . .
2.3.9 Field-Element-to-Integer Conversion . . . . . . . . . . . .

3
3
3
5
5
5
5
5
5
6
6

3 Cryptographic Components
3.1 Elliptic Curve Domain Parameters . . . . . . . . . . . . . . . . .
3.1.X Elliptic Curves Domain Parameters over Fpm . . . . . . . .
3.1.3 Veriﬁably Random Curves and Base Point Generators . . .
3.2 Elliptic Curve Key Pairs . . . . . . . . . . . . . . . . . . . . . . .

6
6
6
9
11

A Glossary
A.1 Terms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2 Acronyms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.3 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12
12
12
12

B ASN.1

12∗ Possible Corrections or Comments on SEC 1 (Draft Version 1.9) 16†

Verifiable Random Curve Generation in Standards†.1 FIPS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
†.2 SEC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
†.3 ANSI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
†.4 Other Comments . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

19
19
19
20
20

CONTENTS

CONTENTS

Update History
Version 0.7 Add reasons in the comments on SEC1 Version 1.8.
Version 0.6 The followings are updated:• Base document version is replaced from SEC1 Version 1.8 to Version
1.9.
• Add ASN.1 representations.
• Correct editorial mistakes.
Version 0.5 First public release.

22 MATHEMATICAL FOUNDATIONS

1Introduction

This document is intended to make the odd characteristic extension ﬁelds available for elliptic curve cryptography deﬁned in SEC 1. The most of speciﬁcationin SEC 1 can be used for the odd characteristic extension ﬁelds as it is, butsome speciﬁcation should slightly be modiﬁed for them. The following sections
describe the modiﬁcations for the odd characteristic ﬁeld from SEC 1. Note thatthe sections that can be used for the odd characteristic extension ﬁeld as it is areomitted in this document.

2

Mathematical Foundations

2.1

Finite Fields

SEC 1 only deﬁnes the ﬁnite ﬁeld Fq , where q is a prime or a power of 2. Here, theodd characteristic extension ﬁelds Fpm are deﬁned, where p is odd prime greaterthan 3 and m ≥ 2.
Mathematically speaking, odd characteristic means p ≥ 3, and p = 3 is very
special for elliptic curve, and p = 3 is not used in this document. p = 3 is
excluded in the deﬁnition of the odd characteristic extension ﬁelds.
2.1.X

The Finite Field Fpm

The ﬁnite ﬁeld Fpm is the characteristic p ﬁnite ﬁeld containing pm elements.
This section describes the case that p is prime and m ≥ 2, and such a ﬁeld iscalled odd characteristic extension ﬁeld. Although there is only one characteristic
p ﬁnite ﬁeld Fpm for each power pm of p with m ≥ 2, there are many diﬀerent
ways to represent the elements of Fpm .
Here the elements of Fpm should be represented using the polynomial basis,that is, the set of polynomials of degree m − 1 or less with Fp -coeﬃcients:{am−1 xm−1 + am−2 xm−2 + · · · + a1 x + a0 : ai ∈ Fp }with addition and multiplication deﬁned in terms of an irreducible monic polynomial f (x) of degree m with Fp -coeﬃcient, known as the reduction polynomial,
as follows:• Addition: If a = am−1 xm−1 + · · · + a0 , b = bm−1 xm−1 + · · · + b0 ∈ Fpm , thena + b = r in Fpm , where r = rm−1 xm−1 + · · · + r0 with ri ≡ ai + bi (mod p).
• Multiplication: If a = am−1 xm−1 + · · · + a0 , b = bm−1 xm−1 + · · · + b0 ∈ Fpm ,then ab = s in Fpm , where s = sm−1 xm−1 +· · ·+s0 is the remainder when thepolynomial ab is divided by f (x) with all coeﬃcients arithmetic performed
modulo p.

3

2 MATHEMATICAL FOUNDATIONS

2.1 Finite Fields

Addition and multiplication in Fpm can be calculated eﬃciently using standard
algorithms for ordinary integer and polynomial arithmetic. In this representation of Fpm , the additive identity or zero element is the polynomial 0, and themultiplicative identity is the polynomial 1.
Again it is convenient to deﬁne subtraction and division of ﬁeld elements.
To do so, the additive inverse (or negative) and multiplicative inverse of a ﬁeld
element must be described:• Additive inverse: If a ∈ Fpm , then the additive inverse (−a) of a in Fpm isthe unique solution to the equation a + x = 0 in Fpm .
• Multiplicative inverse: If a ∈ Fpm , a 6= 0, then the multiplicative inverse
a−1 of a in Fpm is the unique solution to the equation ax = 1 in Fpm .
Additive inverse and multiplicative inverses in Fpm can be calculated eﬃciently.
Multiplicative inverse can be calculated using the polynomial version of the extended Euclidean algorithm. Division and subtraction are deﬁned in terms ofadditive and multiplicative inverses: a − b in Fpm is a + (−b) in Fpm and a/b in
Fpm is a(b−1 ) in Fpm .
Here the odd characteristic extension ﬁelds Fpm used should have:(p, m) ∈ {(261 − 1, 5), (261 − 1, 7), (261 − 1, 11)}and addition and multiplication in Fpm should be performed using one of theirreducible monic polynomials of degree m in Table 1. As before this restriction
is designed to facilitate interoperability while enabling implementers to deploy
eﬃcient implementations capable of meeting common security requirements.
Field
F(261 −1)5
F(261 −1)7
F(261 −1)11

Reduction Polynomial(s)f (x) = x5 − 3
f (x) = x7 − 3
f (x) = x11 − 3Table 1: Representation of Fpm
The rule used to pick acceptable (p, m)’s was that Fpm becomes an optimal
extension ﬁeld (OEF). p of an OEF should slightly be less than the power of 2,
and the power should also slightly be less than word size in bits. Moreover, (p, m)
was chosen such that an irreducible monic binomial with degree m on Fp exists.
c ∈ Fp in the irreducible monic binomial xm − c chosen that as small in nonnegative integer as possible. Composite m was avoided to align this speciﬁcation
to address concerns expressed by some experts about the security of elliptic curvesdeﬁned over Fpm with m composite.
4

2 MATHEMATICAL FOUNDATIONS

2.2

Elliptic Curves

2.2.X

Elliptic Curves over Fpm

2.2 Elliptic Curves

This section is the same as Section 2.2.1 “Elliptic Curves over Fp ” in SEC 1,
except for the followings:• All expressions “· · · ≡ · · ·(mod p)” are replaced with “· · · = · · · in Fpm ”.

• All prime ﬁeld notations Fp are replaced with Fpm .
Note that the case of p = 3 is not considered, because Section 2.1.X does not
accept this parameter.

2.3

Data Types and Conversions

2.3.3

Elliptic-Curve-Point-to-Octet-String-Conversion

Add the following step in Step 2.2 in Actions:2.2.3. If q = pm is a power of odd prime, set ỹP = 0 if y = 0, otherwise setỹP = yi (mod 2), where y = ym−1 xm−1 + · · · + y1 + y0 , and i is the smallest
integer such that yi 6= 0.
2.3.4

Octet-String-to-Elliptic-Curve-Point Conversion

Add the following step in Step 2.4 in Actions:
2.4.4. If q = pm is a power of odd prime, compute the ﬁeld element α = x3P +axP + b in Fpm , and compute a square root β of α in Fpm . Output “invalid” andstop if there are no square roots of α in Fpm . Otherwise set yP = 0 if β = 0,otherwise set yP = β if βi ≡ ỹP (mod 2), and set yP = −β if βi 6≡ ỹP (mod 2),
where β = βm−1 xm−1 + · · · + β1 x + β0 , and i is the smallest integer such thatβi 6= 0.
2.3.5

Field-Element-to-Octet-String Conversion

Add the following step in Actions:
3. If q = pm is a power of odd prime, convert a to M as follows:
3.1. Convert a to x using the conversion routine speciﬁed in Section 2.3.9 (witha as input).
3.2. Convert x to M using the conversion routine speciﬁed in Section 2.3.7 (witha and mlen as inputs).
3.3. Output M .

5

3 CRYPTOGRAPHIC COMPONENTS
2.3.6

Octet-String-to-Field-Element Conversion

Add the following step in Actions:
3. If q = pm is a power of odd prime, then a needs to be a polynomial of degreem − 1 or less with Fp -coeﬃcient. Convert M to a as follows:
3.1. Convert M to an integer x using the conversion routine speciﬁed in Section
2.3.8.
3.2. Output “invalid” and stop if x does not lie in the interval [0, pm − 1].
3.3. View ai as an integer in the range [0, p − 1] and set:
x=

m−1
∑

p i ai .

i=03.4. Set the ﬁeld element a to be a = am−1 xm−1 + · · · + a1 x + a0 , and output a.
2.3.9

Field-Element-to-Integer Conversion

Add the following step in Actions:
3. If q = pm is a power of odd prime, then a must be a polynomial of degree m−1
or less with Fp -coeﬃcient, — i.e. a = am−1 xm−1 + am−2 xm−2 + · · · + a1 x + a0 . Set:
x=

m−1
∑

pi ai

i=0

Output x.

3

Cryptographic Components

3.1

Elliptic Curve Domain Parameters

Following sections often consider only two types of elliptic curve domain parameters. Whenever “two types” are found, consider that the types should include
the type for odd characteristic extension ﬁeld.
3.1.X

Elliptic Curves Domain Parameters over Fpm

Elliptic curve domain parameters over Fpm are an octuple:
T = (p, m, f (x), a, b, G, n, h)

6

3 CRYPTOGRAPHIC COMPONENTS
3.1 Elliptic Curve Domain Parametersconsisting of an integer p and m specifying the ﬁnite ﬁeld Fpm , two elementsa, b ∈ Fpm specifying the elliptic curve E(Fpm ) deﬁned by the equation:
E : y 2 = x3 + ax + b in Fpm ,a base point G = (xG , yG ) on E(Fpm ), a prime n which is the order of G, and an
integer h which is the cofactor h = #E(Fpm )/n.
Elliptic curve domain parameters over Fpm precisely specify an elliptic curveand base point. This is necessary to precisely deﬁne public-key cryptographic
schemes based on ECC.
If the elliptic curve domain parameters T are veriﬁably random, then theyshould be accompanied by the seed value S from which they are derived. Section
3.1.X.1 describes how to generate elliptic curve domain parameters over Fpm ,and Section 3.1.X.2 describes how to validate elliptic curve domain parameters
over Fpm .
Elliptic Curve Domain Parameters over Fpm Generation Primitive
Elliptic curve domain parameters over Fpm should be generated as follows:

3.1.X.1

Input: The approximate security level in bits required from the elliptic curve
domain parameters — this must be an integer t ∈ {80, 112, 128, 192, 256}.
Optionally, a seed value S.
Output: Elliptic curve domain parameters over Fpm :T = (p, m, f (x), a, b, G, n, h)such that taking logarithms on the associated elliptic curve requires approximately 2t operations.
Actions: Generate elliptic curve domain parameters over Fpm as follows:
1. Select (p, m) ∈ {(261 − 1, 5), (261 − 1, 7), (261 − 1, 11)} to determine theﬁnite ﬁeld Fpm such that 22t < pm for a random curve or 22t < pm−1
for a Koblitz curve.
2. Select an irreducible monic polynomial f (x) of degree m from Table 1
in Section 2.1.X to determine the representation of Fpm .
3. Select elements a, b ∈ Fpm to determine the elliptic curve E(Fpm ) deﬁned by the equation:
E : y 2 = x3 + ax + b in Fpm ,a base point G = (xG , yG ) on E(Fpm ), a prime n which is the order ofG, and an integer h which is the cofactor h = #E(Fpm )/n, subject tothe following constraints:
7

3 CRYPTOGRAPHIC COMPONENTS
3.1 Elliptic Curve Domain Parameters• 4a3 + 27b2 6= 0 in Fpm .
• #E(Fpm ) 6= pm .
• pB 6≡ 1 (mod n) for any 1 ≤ B < 100m.
• h ≤ p2t/8 .
• n − 1 and n + 1 should each have a large prime factor r, which is19
in the sense that logn (r) > 20.
If seed S is provided, then the coeﬃcient pair (a, b), or the point G
should be derived from S, or both See Section 3.1.3.
4. Output T = (p, m, f (x), a, b, G, n, h).
This primitive allows any of the known curve selection methods to be used — forexample the methods based on complex multiplication and the methods based on
general point counting algorithms. However to foster interoperability it is strongly
recommended that implementers use one of the elliptic curve domain parameters
over Fpm speciﬁed in SEC X.2. See Appendix B for further discussion.
3.1.X.2 Validation of Elliptic Curve Domain Parameters over Fpm
This section is the same as Section 3.1.1.2 “Validation of Elliptic Curve Domain
Parameters over Fp ” in SEC 1, except for the followings:• All prime ﬁeld notation Fp is replaced with Fpm .
• “Section 3.1.1.2.1” is replaced with “Section 3.1.X.2.1”.
• “Section 3.1.1.1” is replaced with “Section 3.1.X.1”.
Elliptic Curve Domain Parameters over Fpm Validation Primitive
The elliptic curve domain parameters over Fpm validation primitive should be
used to check that elliptic curve domain parameters over Fpm are valid as follows:
3.1.X.2.1

Input: Elliptic curve domain parameters over Fpm :T = (p, m, f (x), a, b, G, n, h)along with an integer t ∈ {80, 112, 128, 192, 256} which is the approximate
security level in bits required from the elliptic curve domain parameters.
Output: An indication of whether the elliptic curve domain parameters are valid
or not — either “valid” or “invalid”.
Actions: Validate the elliptic curve domain parameters over Fpm as follows:83 CRYPTOGRAPHIC COMPONENTS
3.1 Elliptic Curve Domain Parameters
1. Check that (p, m) is an integer in the set {(261 −1, 5), (261 −1, 7), (261 −1, 11)} such that 22t < pm for a random curve or 22t < pm−1 for a
Koblitz curve.
2. Check that f (x) is an irreducible monic polynomial of degree m with
Fp -coeﬃcient which is listed in Table 1 in Section 2.1.X.
3. Check that a, b, xG , and yG are in Fpm .
4. Check that 4a3 + 27b2 6= 0 in Fpm .
2
5. Check that yG= x3G + axG + b in Fpm .

6. Check that n is prime.

√
7. Check that h ≤ p2t/8 , and that h = b( pm + 1)2 /nc.

8. Check that nG = O.
9. Check that pB 6≡ 1
nh 6= pm .

(mod n) for any 1 ≤ B < 100m, and that

10. If any of the checks fail, output “invalid”, otherwise output “valid”.
Step 9 above excludes the known weak classes of curves which are susceptible
to either the Menezes-Okamoto-Vanstone attack, or the Frey-Rück attack, orSemaev-Smart-Satoh-Araki attack. See Appendix B in SEC 1 for further discussion.
If the elliptic curve domain parameters have generated veriﬁably at random as
described in Section 3.1.3, it may also be checked that a and b have been correctly
derived from the seed, and it may also checked that G has been correctly derived
from S.
3.1.3

Verifiably Random Curves and Base Point Generators

The subsections of this section include several unclear descriptions. The following is the modiﬁcation proposal. When modifying the procedures, the following
problems are considered:• Hash is assumed as one deﬁned in Section 3.5, that is, Hash inputs an octet
string and also outputs an octet string, not a bit string.
• Unlike other procedures, one of inputs, “seed”, is a bit string, not an octet
string.
3.1.3.1 Curve Selection
For generating Koblitz curve over Fpm , the input of ﬁeld size q is chosen as p
instead of pm , otherwise choose q = pm .
Input: A “seed” octet string S of length g, ﬁeld size q, hash function Hash of
output length t, and ﬁeld element a ∈ Fq .
9

3 CRYPTOGRAPHIC COMPONENTS
3.1 Elliptic Curve Domain Parameters
Output: A ﬁeld element b ∈ Fq or “failure”.
Actions: Generate the element b as follows:
1. If a = 0, then output “failure” and stop.
2. Let u = dlog2 qe.
3. Let s = b(u − 1)/tc.
4. Let k = u − st if q is even, and let k = u − st − 1 if q is odd.
5. Convert S to an integer s0 using the conversion routine speciﬁed in
Section 2.3.8 (with S as input).
6. For j from 0 to s, do the following:
6.1 Let sj = s0 + j mod 28g .
6.2 Let Sj be the integer sj converted to an octet string of length goctets using the conversion routine speciﬁed in Section 2.3.7 (withSj and g as inputs).
6.3 Let Hj = Hash(Sj ).
6.4 Convert Hj to an integer ej using the conversion routine speciﬁedin Section 2.3.8 (with Hj and t as inputs).
7. Let e = e0 2ts + e1 2t(s−1) + · · · + es mod 2k+st .
8. Convert e to an octet string x using the conversion routine speciﬁedin Section 2.3.7 (with e and du/8e as inputs).
9. Convert x to a ﬁeld element r ∈ Fq using the conversion routine speciﬁed in Section 2.3.6 (with the indication of the ﬁeld Fq and x as
inputs).
10. If q is even, then do as follows:
10.1 If r = 0, then output “failure” and stop.
10.2 If r 6= 0, then output b = r ∈ Fq and stop.
11. If q is odd, then do as follows:
11.1 If r = 0, then output “failure” and stop.
11.2 If 4r + 27 = 0 in Fq , then output “failure” and stop.
11.3 If a3 /r does not have a square root in Fq , then output “failure”
and stop.
√
11.4 Otherwise, choose one of ± a3 /r ∈ Fq as b and output b and
stop.

10

3 CRYPTOGRAPHIC COMPONENTS

3.2 Elliptic Curve Key Pairs

3.1.3.2 Point Selection
Input: A “seed” octet string S of length g, ﬁeld size q, hash function Hash of
output length t, and elliptic curve parameters a and b, and elliptic curve
cofactor h.
Output: An elliptic curve point G.
Actions: Generate an elliptic curve point G as follows:
1. Let A = 4261736520706F 696E7416 , which is the octet string associated with the ASCII representation of the text string “Base point”.
2. Let B = 0116 , an octet string of length 1.
3. Let an integer c = 1.
4. Convert integer c to an octet string C of length 1+blog256 (c)c using theconversion routine speciﬁed in Section 2.3.7 (with c and 1 + blog256 (c)cas inputs).
5. Let H = Hash(AkBkCkS).
6. Convert H to an integer e using the conversion routine speciﬁed in
Section 2.3.8 (with H as input).
7. Let s = e mod 2q.
8. Let u = s mod q and ỹR = bs/qc.
9. Convert integer u to an octet string x using the conversion routine
speciﬁed in Section 2.3.7 (with u and 1 + blog256 qc as inputs).
10. Convert octet string x to a ﬁeld element xR ∈ Fq using the conversion
routine speciﬁed in Section 2.3.6 (with the indication of the ﬁeld Fq
and x as inputs).
11. Recover a y-coordinate from the compressed point information (xR , ỹR ),as appropriate to the elliptic curve followed by Step 2.4 in Section 2.3.4.
12. If there is no valid yR , then increment c and go back to Step 4.
13. Let R = (xR , yR ).
14. Compute G = hR.
15. Output G.

3.2

Elliptic Curve Key Pairs

Modiﬁcation request: Please do not use the speciﬁc descriptions regarding Fp
or F2m such as “T = (p, a, b, G, n, h) or (m, f (x), a, b, G, n, h)” in the schemes
including ECDSA for the following sections.

11B ASN.1

A

Glossary

A.1

Terms

Add the following term(s):odd characteristic extension field A ﬁnite ﬁeld containing pm elements, wherep > 3 is an odd prime number and m ≥ 2 is an integer.
Modify the following term(s):reduction polynomial The irreducible monic polynomial f (x) of degree mwith F2 - or Fp -coeﬃcient that is used to determine a representation of F2m
or Fpm .

A.2

Acronyms

Add the following acronym(s):OEF optimal extension ﬁeld

A.3

Notation

Modify the following notation(s):Fq The ﬁnite ﬁeld containing q elements. In this document attention is restricted
to the cases that q is an odd prime number p or a power of 2 (2m ) or a
power of an odd prime p (pm ).

B

ASN.1

--###################################################################-- finite field, group, and elliptic curve representations
Group ::= CHOICE {groupOid OBJECT IDENTIFIER,
groupHashId OCTET STRING, -- defined in RFC2528
groupParameters GroupParameters}
GroupParameters ::= CHOICE {explicitFiniteFieldSubgroup[0] ExplicitFiniteFieldSubgroupParameters,
ellipticCurveSubgroup[1] EllipticCurveSubgroupParameters}
12B ASN.1
ExplicitFiniteFieldSubgroupParameters ::= SEQUENCE {fieldID FieldID {{FieldTypes}},
generator FieldElement,
subgroupOrder INTEGER,
subgroupIndex INTEGER}FIELD-ID ::= TYPE-IDENTIFIER
FieldID { FIELD-ID:IOSet } ::= SEQUENCE {fieldType FIELD-ID.&id({IOSet}),parameters FIELD-ID.&Type({IOSet}{@fieldType}) OPTIONAL}
FieldTypes FIELD-ID ::= {{ Prime-p IDENTIFIED BY prime-field } |{ Characteristic-two IDENTIFIED BY characteristic-two-field }|{ Odd-characteristic IDENTIFIED BY id-ft-odd-characteristic },... -- expect additional field types}-- prime fieds
Prime-p ::= INTEGER-- characteristic two fields
CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER-- when basis is gnBasis then the basis shall be an optimal-- normal basis of Type T where T is determined as follows:-- if an ONB of Type 2 exists for the given value of m then-- T shall be 2, otherwise if an ONB of Type 1 exists for the-- given value of m then T shall be 1, otherwise T shall be-- the least value for which an ONB of Type T exists for the-- given value of m-- when basis is gnBasis then m shall not be divisible by 8-- note: the above rule is from ANSI X9.62-- note: for the given m and T the ONB is unique
Characteristic-two ::= SEQUENCE {m INTEGER,-- extension degreebasis CHARACTERISTIC-TWO.&id({BasisTypes}),parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis})}
BasisTypes CHARACTERISTIC-TWO ::= {{ NULL IDENTIFIED BY gnBasis } |{ Trinomial IDENTIFIED BY tpBasis } |{ Pentanomial IDENTIFIED BY ppBasis } |{ CharTwoPolynomial IDENTIFIED BY charTwoPolynomialBasis },... -- expect additional basis types}
13

B ASN.1
Trinomial ::= INTEGER
Pentanomial ::= SEQUENCE {k1 INTEGER,
k2 INTEGER,
k3 INTEGER}-- characteric two general irreducible polynomial representation-- the irreducible polymial-- a(n)*x^n + a(n-1)*x^(n-1) + ... + a(1)*x + a(0)-- is encoded in the bit string with a(n) in the first bit, the-- following coefficients in the following bit positions and a(0)-- in the last bit of the bit string (one could omit a(n) and a(0)-- but it may be simpler and less error-prone to leave them in-- the encoding)-- the degree of the polynomial is to be inferred from the length-- of the bit string
CharTwoPolynomial ::= BIT STRING-- odd characteristic extension fields
ODD-CHARACTERISTIC ::= TYPE-IDENTIFIER
Odd-characteristic ::= SEQUENCE {characteristic INTEGER(3..MAX),
degree INTEGER(2..MAX),
basis ODD-CHARACTERISTIC.&id({OddCharBasisTypes}),parameters ODD-CHARACTERISTIC.&Type({OddCharBasisTypes}{@basis})}
OddCharBasisTypes ODD-CHARACTERISTIC ::= {{ OddCharPolynomial IDENTIFIED BY oddCharPolynomialBasis },... -- expect additional basis types}-- the monic irreducible polynomial is encoded as follows-- the leading coefficient is ignored-- the remaining coefficients define an element of the finite field-- which is encoded in an octet string using FE2OSP
OddCharPolynomial ::= FieldElement
EllipticCurveSubgroupParameters ::= SEQUENCE {version INTEGER { ecpVer1(1) } (ecpVer1),
fieldID FieldID {{ FieldTypes }},curve Curve,
generator ECPoint, -- Base point G
subgroupOrder INTEGER, -- Order mu of the base point
subgroupIndex INTEGER, -- The integer nu = #E(F)/mu
...
}
14

B ASN.1
Curve ::= SEQUENCE {aCoeff FieldElement,bCoeff FieldElement,
seed BIT STRING OPTIONAL}

15

∗ POSSIBLE CORRECTIONS OR COMMENTS ON SEC 1 (DRAFT
VERSION 1.9)∗

Possible Corrections or Comments on SEC 1(Draft Version 1.9)

page 1, Section 1, 1st line: “sectiongives” should be “section gives”.
Reason: trivial mistake.
page 14, Section 2.3.8, 1st line: “range [1, 256]” should be “range [0, 255]”.
Note that Version 1.0 does not contain this problem.
Reason: If the range [1, 256] is adopted, Integer-to-Octet-String Conversion in
Section 2.3.7 is not an inverse procedure of this section.
page 14, Section 2.3.9, 3rd line: The formal procedure does not convert thebinary polynomial to an octet string.
Reason: This section speciﬁes the conversion to an integer, not to an octet
string.
page 14, Section 2.3.9, Step 2 in Actions: The degree of a may be less thanm − 1.
Reason: When am−1 = 0, we do usually not call the degree of polynomial am−1 xm−1 +am−2 xm−2 + · · · + a1 x + a0 is m − 1.
page 16, Section 3.1.1.1, last line in Step 2 in Actions: “§” is used insteadof “Section”.
Reason: This version of SEC1 document sometimes use § and sometimes use“Section”. These expression should be consistent.
page 18, Section 3.1.1.2.1, Step 8 in Actions: “n 6= p” should be replacedwith “nh 6= p”.
Reason: This condition is valuable when h = 1, thus there is no problem even if
the procedure is not changed. However, the condition seems strange, since
we usually considers the number of rational points is equal to nh.
page 19, Section 3.1.2.1, last line in Step 3 in Actions: “§” is used insteadof “Section”.
Reason: same as the comments on page 16.
page 20, Section 3.1.2.2, last line: The description for CA is omitted while
Section 3.1.1.2 writes.
Reason: The last two lines in Section 3.1.1.2 describes the use of CA, and Section 3.1.2.2 is the same as Section 3.1.1.2 except for the ﬁeld type. It seems
strange that there is no description regarding CA for the ﬁeld type F2m .

16

∗ POSSIBLE CORRECTIONS OR COMMENTS ON SEC 1 (DRAFT
VERSION 1.9)
page 21, Section 3.1.3: This section only generates an elliptic curve or a basepoint. Sections 3.1.1.2.1 and 3.1.2.2.1 certainly describe the use of seed S.
However, this section does not express the generated curves (or base point)
is valid for the use of secure cryptosystem.
Reason: See the next comment.
page 21, Section 3.1.3, 2nd line: A veriﬁcation procedure such as Appendix
6.5 in FIPS186-2 (+ Change Notice) cannot be found. (See Appendix †.1
for the problem in FIPS186-2.)
Reason: A generation procedure should exist with a veriﬁcation procedure.
page 21, Section 3.1.3, 2nd line: “ANS” may be replaced with “ANSI”.
Reason: There is two expression such as ANS X9.62 and ANSI X9.62. They
should be consistent.
page 21, Section 3.1.3, 2nd paragraph, 4th line: “based point” should be
replaced with “base point”.
Reason: We cannot ﬁnd the term “based point” except for this location.
page 21, Section 3.1.3.1: The following problems are identiﬁed:• Section 3.5 seems to deﬁne Hash outputs octet string, but t seems anumber of bits.
Reason: First, the output length of Hash is ambiguous. Section 3.5 describes
how to compute the hash value, and it is octet string. So, the the unitof t seems the number of octets of hash value. However, the unit of t
in Actions should be bit. If t is the number of octets, Actions should
totally be rewritten.
• “is q is odd” in Step 3 should be replaced with “if q is odd”.
Reason: Trivial mistake.
• Which conversion procedure is used is not written in Steps 4 and 7.
Reason: Before this section, what procedure is used is written for this kind of
conversion.
• Step 7 may output “invalid”.
Reason: The deﬁnition of the output of this procedure does not include “invalid”.
• Step 9.1 does not conﬁrm the case r = 0.
Reason: The condition r = 0 hardly occurs, but Step 8.1 considers the case.
Actually, the division in Step 9.3 cannot be computed when r = 0.
• Lack of period in Step 9.1.
Reason: Trivial mistake.
17∗ POSSIBLE CORRECTIONS OR COMMENTS ON SEC 1 (DRAFT
VERSION 1.9)
• In Step 9.2, “in Fq ” should be added for 4r + 27 = 0.
Reason: Actually, r is an ﬁeld element, so this equation should be evaluated in
Fq . However, this condition is important and former section describes
what ﬁeld should be used in the evaluation, for example, Steps 4 and 5
in Actions in Section 3.1.2.2.1.
√• Describe how to choose one of a3 /r in Step 9.4.
Reason: The number of square roots of a3 /r is two. Currently there is no known
attack to utilize the opposite sign of square root. We think that thevalidation procedure should not contain ambiguity. So, this generation
procedure should deﬁne which square root is chosen, but it depends onthe expecting validation procedure.
page 22, Section 3.1.3.2: The following problems are identiﬁed:• The output of the procedure includes “failure”. However, the procedure outputs “failure” when c is almost larger than the input boundof Hash. It is very hardly occurs.
Reason: This “rare case” treatment is diﬀerent from Section 3.1.3.1. See 4thitem in the comments for Section 3.1.3.1. They should be consistent.
• t is used for the output length of Hash and Step 7.
Reason: The same letter should not be used for diﬀerent meaning.
• If the output length of Hash is small, u is not uniform when q is odd.
Moreover, z is always 0 in Step 10.
Reason: There is no known attack for “small” numbers on these parameters.
However, the uniformly chosen parameters give some good feeling for
security.
• The compressed point information (x, z) in Step 10 is not deﬁned before.
Reason: The deﬁnition appears in the later section. The pointer should be described, or the deﬁnition should be appeared in advance in this section.
page 22-, Section 3.2-: The following sections only considers for the prime
ﬁeld and the characteristic two ﬁeld. It seems very easy to modify thatthe descriptions for prime ﬁelds considers for both prime ﬁeld odd characteristic extension ﬁelds. Could you include this comments?
Reason: We consider to include OEF to SEC document. However, the current
descriptions of the following sections only consider the case for the binary
ﬁeld and prime ﬁeld.
page 29-30, Section 3.5: The hash functions written in the section inputs andoutputs octet strings, but hash function Hash in Actions inputs and outputs bit strings.
18

† VERIFIABLE RANDOM CURVE GENERATION IN STANDARDS
Reason: First, the interface of Hash is not consistent. Recently, the trend in
the standardization in the cryptography uses octet instead of bit for the basic
unit. We suggest to use octet.
page 72-73, Section B.2.1: Add the comments regarding the following problem. Section 3.1.3 describes the veriﬁable parameter generations. Someparameters generated by the procedures described in the section are notchosen uniformly random from acceptable range. This may not be a problem, but the thought why the procedures are okay should be described.
page 96-99, Section B.6: Many “ANS” are found. Actually, the expression
both ANS X9.62 and ANSI X9.62 seems acceptable, but the combination
seems strange.

†

Verifiable Random Curve Generation in Standards

†.1

FIPS

c is generated by SHA-1, and one cannot control the value of c.
• Step 9 of APPENDIX 6.4 (page 63) in FIPS 186-2 (+ Change Notice)
Step 9 of Section E.5 (page 114) in FIPS 186-3 (March 2006 Draft)
9. Choose integers a, b ∈ GF (p) such thatcb2 ≡ a3

(mod p)(The simplest choice is a = c and b = c. However, one may want
to choose diﬀerently for performance reasons.)• Step 7 of APPENDIX 6.5 (page 64) in FIPS 186-2 (+ Change Notice)
Step 7 of Section E.6 (pp.114–115) in FIPS 186-3 (March 2006 Draft)
7. Verify that b2 c ≡ −27 (mod p).
The veriﬁcation procedure seems to assume a = −3, but the generation procedure
accepts the case of a 6= −3.

†.2

SEC

r is derived with Hash, and one cannot control the value of r. a is one of the
input of the generation procedure, similar to the input of hash function. In SEC
1, Draft 1.9:
19

† VERIFIABLE RANDOM CURVE GENERATION IN STANDARDS†.3 ANSI• Step 9 (page 21) in Section 3.1.3.1:
9.1 If a = 0, then output “failure” and stop
9.2 If 4r + 27 = 0, then output “failure” and stop.
9.3 If a3 /r does not have a square root in Fq , then output “failure” and stop.
√
9.4 Otherwise output b = a3 /r ∈ Fq and stop.
• The veriﬁcation procedure is undeﬁned.

†.3

ANSI

r is derived with Hash, and one cannot control the value of r. a is arbitrary
chosen. In ANSI X.62-2005:• Step l in Section A.3.3.1
1) Solve the equation b2 r = a3 for b in Fq if a solution exists;
otherwise, stop and output “Failure” (see NOTE 2).
2) If 4a3 + 27b2 = 0, then stop and output “Failure” (see NOTE
3).
• Step d in Section A.3.3.2
If SEED is provided and the curve E does not match the curvethat would be generated using A.3.3.1, then stop and output“Invalid”.

†.4

Other Comments• The random number generated from hash function is not uniform in thevalid range. Uniformly random value seems better.
• To decide a and b in the equation y 2 = x3 + ax + b has some freedom. The
algebraic closure of the curve has the same group structure, however, theorder of the elliptic curve over the ﬁnite ﬁeld may vary. It seems betterthat a and b does not have freedom to choose by the generation.

20