43.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.

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 43-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).

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.