37.3.7.1 Parameters Format

Polynomials in GF(2n)

Polynomials in GF(2n) are binary polynomials reduced modulo the polynomial P[X]. This polynomial is called the modulus and may be abbreviated to P in this document. The storage of these polynomials in memory area is described in Aligned Significant Length (see Aligned Significant Length from Related Links).

For notation simplicity the comparison signs “<“ or “>” may be used for polynomials, this is to be interpreted as a comparison between the degree of the polynomials.

In GF(2n) fully reduced polynomials are of degree strictly lower than degree(P[X]). In many cases the polynomials used in this library are only partially reduced and so have a degree higher or equal than degree(P[X]), but this degree is maintained strictly lower than (degree(P[X]) + 15).

Coordinates System

In this implementation, several choices have been made related to the coordinate systems managed by the elliptic curve primitives.

There are two systems currently managed by the library:

  • Affine Coordinates System where each curve point has two coordinates (X,Y)
  • Projective Coordinates System where each point is represented with three coordinates (X,Y,Z)

Converting from the affine coordinates system to a projective coordinates system and is performed by extending its representation having Z = 1:

(X,Y) ⇒ (X,Y, Z= 1)

Converting from a projective coordinate to an affine one is a service offered by the library. The formula to perform this conversion is:

(X,Y, Z) ⇒ (X ⇒ Z,Y/Z2)

Points Representation in Memory

Depending on the representation (Projective or Affine), points are represented in memory as shown in the following figure.
Figure 37-15. Point Representation in Memory

In this figure, the modulus is represented as a reference, and to show that coordinates are always to be provided on the length of the modulus plus one 32-bit word.

Different types of representations are listed here:

Affine representation:   P t = [ X A f f i n e < P × X 15 Y A f f i n e < P × X 15 ]
Projective representation:   P t = [ X Pr ⁡ o j e c t i v e < P × X 15 Y Pr ⁡ o j e c t i v e < P × X 15 Z Pr ⁡ o j e c t i v e < P × X 15 ]
Note:
  1. The minimum value for u2ModLength is 12 bytes. Therefore, the significant length of the modulus must be at least three 32-bit words.
  2. In some cases the point can be the infinite point. In this case it is represented with its Z coordinates equal or congruent to zero.

Modulus and Modular Constant Parameters

In most of the services the following parameters must be provided:

  • P the Modulus (often pointed by {nu1ModBase,u2ModLength + 4}): This parameter contains the Modulus Polynomial P[X] defining the Galois Field used in points coordinates computations. The Modulus must be u2ModLength bytes long, while having a supplemental zeroed 32-bit word on the MSB side.
    Note: Most of the Elliptic Curve computations are reduced modulo P. In many functions the reductions are made with the Fast Reduction.
  • Cns the Modular Constant (often pointed by {nu1CnsBase,u2ModLength + 12}): This parameter contains the Modular Constant associated to the Modulus.
Important: The Modular Constant must be calculated before using the GF(2n) Elliptic Curves functions by a call to the Setup for Modular Reductions with the GF(2n) option (see Modular Reduction from Related Links).

Curve Parameters in Memory

Some services need one or both of the Elliptic Curve Equation Parameters a and b. In this case these values are organized in memory as follows:

  • The a Parameter relative to the Elliptic Curve Equation (often pointed by {nu1ABase,u2ModLength +4}). The a Parameter is written in a classical way in memory. It is u2ModLength bytes long and has a supplemental zeroed 32-bit word on the MSB side.
  • The a and b Parameters relative to the Elliptic Curve Equation (often pointed by {nu1ABBase,2*u2ModLength + 8}):
    • The a Parameter is written in memory on u2ModLength bytes long, with a supplemental zeroed 32-bit word on the MSB side.
    • The b Parameter is written in memory after the a Parameter at an offset of (u2ModLength + 4) bytes. It is written in memory on u2ModLength bytes long, with a supplemental zeroed 32-bit word on the MSB side.