4
$\begingroup$

In SEC 2: Recommended Elliptic Curve Domain Parameters two types of finite fields are utilized - $\mathbb{F}_p$ and $\mathbb{F}_{2^m}$. In the case of sect193r1, $\mathbb{F}_{2^m}$ is the finite field, where $m = 193$ and is defined by $f(x) = x^{193}+x^{15}+1$

In SEC 1: Elliptic Curve Cryptography, the following ASN.1 structures are presented:

FieldTypes FIELD-ID ::= {
    { Prime-p IDENTIFIED BY prime-field } |
    { Characteristic-two IDENTIFIED BY characteristic-two-field }
}
prime-field OBJECT IDENTIFIER ::= { id-fieldType 1 }
Prime-p ::= INTEGER -- Field of size p.
id-fieldType OBJECT IDENTIFIER ::= { ansi-X9-62 fieldType(1)}
ansi-X9-62 OBJECT IDENTIFIER ::= {
    iso(1) member-body(2) us(840) 10045
}
characteristic-two-field OBJECT IDENTIFIER ::= { id-fieldType 2 }
Characteristic-two ::= SEQUENCE {
    m INTEGER, -- Field size 2m
    basis CHARACTERISTIC-TWO.&id({BasisTypes}),
    parameters CHARACTERISTIC-TWO.&Type({BasisTypes}{@basis})
}
CHARACTERISTIC-TWO ::= TYPE-IDENTIFIER
BasisTypes CHARACTERISTIC-TWO ::= {
    { NULL IDENTIFIED BY gnBasis } |
    { Trinomial IDENTIFIED BY tpBasis } |
    { Pentanomial IDENTIFIED BY ppBasis },
    ...
}
gnBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 1 }
tpBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 2 }
ppBasis OBJECT IDENTIFIER ::= { id-characteristic-two-basis 3 }
id-characteristic-two-basis OBJECT IDENTIFIER ::= {
    characteristic-two-field basisType(3)
}
Trinomial ::= INTEGER
Pentanomial ::= SEQUENCE {
    k1 INTEGER, -- k1 > 0
    k2 INTEGER, -- k2 > k1
    k3 INTEGER -- k3 > k2
}

$x^{193}+x^{15}+1$ is a trinomial but the "basis type" for it only consists of one integer? It seems to me that there are probably close to three integers - the exponents for $x$? eg. $193$, $15$ and $0$? idk - I guess it's just unclear to me how you're supposed to get $x^{193}+x^{15}+1$ from the ASN.1 or, conversely, how you're supposed to denote $x^{193}+x^{15}+1$ in the ASN.1.

Any ideas?

$\endgroup$
8
$\begingroup$

For a binary field $\mathbb{F}_{2^m}$, the polynomial necessarily has degree $m$ (otherwise the field would not have cardinal $2^m$), and its least significant coefficient must be $1$, not $0$ (otherwise the polynomial would not be irreducible, and the field would not be a field).

Therefore, for $\mathbb{F}_{2^{193}}$, if the polynomial is a trinomial, then it is already known that is is $x^{193}+x^j+1$ for some integer $1<j<193$. Only that integer $j$ needs to be encoded, which is why you only have one INTEGER. In other words, when trying to encode $x^{193}+x^{15}+1$, only the "15" needs to be encoded; the "193" and the "0" are implicit.

Similarly, for a pentanomial, you only have to encode three exponents, since the two extremes (0 and the field size) are implicit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.