RSA Security 5.2.2 Elliptic Curve Key Pair Generation, Representing Fields of Even Characteristic

Cryptography Overview

Representing Fields of Even Characteristic

For fields of even characteristic (fields of the form F2m), Crypto-C allows you to choose how you want the field to be represented. The representation you choose is internal to Crypto-C and affects how field arithmetic is performed. The choice of representation is also one of the formal elliptic curve parameters that must be transmitted along with the public key. Some representations lead to more efficient implementations in hardware or software.

When we talk about representations of F2m, we use the term basis to reflect the original mathematics underlying the construction of F2m. From our point of view, it is most important to know that a different basis corresponds to a different representation in Crypto-C. Crypto-C offers two types of representation for fields of even characteristic:

•Polynomial basis: this representation closely reflects how the field was originally constructed by mathematicians. Every field of even characteristic has a polynomial basis representation.

•Optimal normal basis (ONB): this representation is constructed to optimize certain multiplicative operations. Not all fields have an ONB representation; it can be constructed only for certain values of m.

The difference in the choice of basis shows up most clearly in how multiplication is defined. For example, for any polynomial basis representation, the multiplicative identity is represented as (000…01). For any optimal normal basis, the multiplicative identity is (111…11).

Note: Although arithmetic looks different when you choose a different representation, the field is still the same. Just as you can represent “normal”arithmetic using a hexadecimal or a decimal system, you can represent F2m inmore than one way.

Elliptic Curve Key Pair Generation

Elliptic curve parameters can be used to generate a public/private key pair. Elliptic curve parameters can either be common to several key pairs or specific to one key pair. The elliptic curve parameters can be public; the security of the system does not rely on these parameters being secret.

7 2 R S A B S A F E C r y p t o - C D e v e l o p e r ’s G u i d e