Finite Field Arithmetic for Engineers

[gpestana]

Let's dive into the theory and engineering details of finite fields for cryptography. This document is part of a series of guides helping engineers transitioning into applied cryptography.

Groups, Fields and Polynomials

We're especially interested in Finite Fields (FF) (i.e. Galois Fields - GF), which are fields with a finite number of elements. We will focus on how to represent and compute polynomials over FF, which are of big interest in several cryptosystems such as RSA, Elliptic curve and Lattice-based cryptography. The last sections focus on performance (in terms of space and time) of FF arithmetic. Throughout the document, we use Go for code to show how to implement the ideas presented.

A Finite Field is a set of finite elements with two operations (addition and multiplication) and their inverses (subtraction and division). Examples of fields are the real field R, the complex field C, rational numbers Q and the binary field F_2.

Groups

A group is a set of elements G = {a, b, c, ...} and an operation *, with Closure, Associative, Identity and Inverse properties.

Polynomials

A polynomial over Fp are polynomials that coefficients lie in Fp, with polynomial addition and multiplication over Fp.

A polynomial f(x) of degree m over field F is of the form:

f(x) = f_0 + f_1 x + f_2 x^2 + f_3 x^3 + ... + f_m x^m

In cryptography, it is useful to perform computations over polynomials. For example, many asymmetric encryption cryptosystems depend on polynomial arithmetic to generate key pairs, encryption, and decryption. Thus, it is important to be able to represent polynomials and to efficiently perform computation on polynomials.

A fair mechanism to represent and store polynomials is by encoding coefficients in vectors:

// represents a polynomial in Fp with p^m elements
type Polynomial struct {
   coeffs []big.Int
   n uint64
   p uint64
}

Taking Away Points

• For each prime p and positive integer m >= 1, there is a FF with p^m elements.
• In Finite Fields, operations are closed within the field. In practice, this means that the result of the computation of two elements in a field is another element in the field.
• The integers modulo p form a prime field Fp under mod-p addition and multiplication.

Performance Improvements

Further Reading

https://crypto.stackexchange.com/questions/2700/galois-fields-in-cryptography
https://web.stanford.edu/class/ee392d/Chap7.pdf