Finite Field Arithmetic

Some source code for finite field arithmetic.


Montgomery Multiplication in Finite Fields

• Montgomery Multiplication in the field GF(2^8) [Source Code]
• Bit serial Montgomery Multiplication in the field GF(2^233) [Source Code]

---

Composite Field Isomorphisms

The AES s-box provides the non-linearity in the cipher. It is defined as follows: S(x) = xinv + A

• A is a affine transformation.
• xinv is the inverse of x in the finite field GF(2^8). This means that (xinv * x)mod P = 1, where P is the irreducible polynomial of the field. 

Finding xinv in hardware could have significant area requirement, so developers often use composite fields, which decomposes large arithmetic into smaller ones.  For instance a composite field for GF(2^8) is the field GF((2^4)^2), which breaks down 8 bit arithmetic to 4 bit arithmetic. The requirements is that such a composite field needs to be found.

The source code available here shows how a composite field can constructed [Source Code].

The algorithm is taken from Christoff Paar's PhD thesis.

---

ECC over Optimal Extension Fields (OEF)

OEF field arithmetic is implementation friendly on microprocessors. This code has an implementation of Elliptic curve cryptography over OEF [Source Code].
Three OEF fields are supported. Refer to the SEC X.2 recommendations.