Reversing a Finite Field Multiplication Optimization

Binary Finite Field elements into Binary Strings

We work in the binary finite field GF($2^{128}$). Elements are represented as binary polynomials of degree at most 127. Such elements are stored through the sequence of their binary coefficients, which means an element is represented as a 128-bit word, where the coefficient of the degree $i$ monomial is stored at position $i$. Then, the most significant bit represents the coefficient of the monomial of degree 127 and the least significant bit represents the constant of the polynomial.

The finite field addition of two elements is simply carried out by the binary sum of the coefficients of the monomials having the same degree. It corresponds to the bitwise XOR of the two 128-bit words representing the polynomials. It means, we denote by $+$ the addition of two polynomials and we denote by $\oplus$ the addition of two elements of the finite field, as it is a bitwise XOR on the bit string representation.

As we work with binary polynomials, subtraction is the same as addition and in the following we will not use any minus signs.

The polynomial multiplication of two polynomials is the usual one you already know.

The finite field multiplication of two elements, that we denote by $\bullet$, corresponds to the modular multiplication of the two corresponding polynomials modulo the defining polynomial of the finite field. The GCM standard specifies that the defining polynomial one should use is $P(X) = X^{128} + R(X)$ with $R(X) = X^7 + X^2 + X + 1$.

The finite field multiplication by $X^n$ is an important special case. It simply corresponds to the left shift by $n$ positions, when the degree of the polynomial to multiply is smaller than $127-n$ (when this degree is bigger than $128-n$ it resorts to the former general case finite field multiplication).

The polynomial division is denoted by $\mathrm{div}$ and is the usual Euclidean division (like the integer division but for polynomials).

The finite field division of $a$ by $b$, that we denote by $a/b$, corresponds to $a \bullet b^{-1}$ where $b^{-1}$ is computed thanks to the extended Euclidean algorithm. As we represent elements by polynomials, the operation is denoted by $a(X) / b(X) \pmod{P(X)}$, which means we compute first the modular inverse of $b(X)$ modulo $P(X)$ and then we multiply it modulo $P(X)$ by $a(X)$.

The finite field division by $X^n$ is the counterpart of the multiplication case. It corresponds to the right shift by $n$ positions, when the degree of the smallest degree monomial of the polynomial to divide is bigger than $n$ (when this degree is smaller than $n-1$ it resorts to the general case division).

Beware of notions and pieces of notations, especially for division. We denote by $\mathrm{div}$ the polynomial division and by $/$ the finite field division. The only case where $a(X)\:\mathrm{div}\: b(X)$ corresponds to $a(X) / b(X)\pmod{P(X)}$ is the case where $a(X)$ is a multiple of $b(X)$ of degree less than 127. Otherwise, we deal with two distinct notions and computations.

Binary Strings into Binary Finite Field Elements

Suppose you are given a binary file and you want to apply AES-GCM to it. How would you embed the bit strings into elements of a finite field? The straightforward way is to consider the bit string as the sequence of the coefficients of the polynomial representing an element of the finite field we are working in. This leaves to the designer the choice of the bit numbering to use, e.g. either considering the bit string $a =$ 11001001 to be $a = a_7a_6a_5a_4a_3a_2a_1a_0$ (most significant bit is leftmost) or $a = a_0a_1a_2a_3a_4a_5a_6a_7$ (most significant bit is rightmost).

The most usual representation used when manipulating elements in a finite field is the one where most significant bit means leftmost bit and least significant bit means rightmost bit. We used it beforehand to illustrate the representation of finite field elements. The GCM standard counterintuitively specifies that bit strings have to be considered with the opposite convention. It means that with GCM, a 128-bit block has to be numbered $a = a_0a_1a_2a_3\ldots a_{127}$. This implies that on most cases when the two conventions have to be used simultaneously, input bit strings have to be reflected first before being applied finite field operations and the result be reflected back, to comply with the standard (one can find an analysis of such a choice by Rogaway in [Rog2011], Remark 12.4.4, p.130). It is the case with all of the Intel's implementations.

Available Instructions for Binary Finite Field Arithmetic

As we have seen, adding two finite field elements is easy, we use the bitwise XOR. Some cases of multiplications or divisions are easy, we use left or right shifts. Until recently, the general case multiplication or division resorted to special arithmetic operations to be implemented in software. The situation ended for the multiplication with the advent of the pclmulqdq instruction which computes the polynomial multiplication.

Rewriting the Modular Multiplication in GCM on Straight Inputs

As it is a major source of mistakes, we recall first that a binary polynomial represented by a binary word of size $w$ has degree at most $w-1$.

Let us consider the polynomial $A(X) = A_{127}X^{127} + A_{126}X^{126} + \ldots + A_{0}$. If we denote by $ref(A,w)$ the reflected polynomial of $A$ on a binary word of size $w$, with $w \geq 128$ we have $ref(A,w)(X) = A_{0}X^{w-1} + A_{1}X^{w-2} + \ldots + A_{127}X^{w-1-127} = A(X^{-1})X^{w-1}$.

As we mentioned earlier, all Intel's implementations of GCM work on reflected inputs in order to comply with the standard, whose choice of bit numbering is contrary to customs. In that respect, the Intel's GCM way to multiply two inputs A and B is the following:

Intel's GCM modular multiplication
T1 = ref(A, 128)
T2 = ref(B, 128)
T3 = T1 • T2
return ref(T3, 128)

with $T_3(X) = T_1(X) \times T_2(X) \bmod P(X)$. There is an useful and easy property one can check on reflected inputs when working with the polynomial representation (it is straightforward when one writes it):

To grasp the idea intuitively, consider for instance $A$ and $B$ reflected on 128-bit words. The degrees of $ref(A,128)$ and $ref(B, 128)$ is at most 127. The degree of $ref(A, 128) \times ref(B, 128)$ is at most 254, which means it can be represented on a 255-bit word. If it is reflected on a 256-bit word, we need to right shift it to make it become a 255-bit word (and a 255-degree polynomial).

The goal of this section is to explain how to express $ref(T_3,128)$ directly from $A$ and $B$ without using their reflected representations.

As we have $T_3(X) = T_1(X) \times T_2(X) \bmod P(X)$, we will work on $T_1(X) \times T_2(X)$ to find properties to relate $ref(T_3,128)$ directly to $A$ and $B$.

• The Euclidean division rule allows us to write $T_1(X) \times T_2(X) = q(X) \times P(X) + T_3(X)$ with $deg(T_3) < 128$. As the degree of $T_1(X) \times T_2(X)$ is at most 254 and the degree of $P(X)$ is 128, we have $deg(q) \leq 126$.

• The property on the multiplication of reflected inputs allows us to write: $ref(T_1 \times T_2, 256) = ref(T_1, 128) \times ref(T_2, 128) \times X$.

• One can see that the reflection operation is a linear one, then $ref(T_1 \times T_2, 256) = ref(q \times P, 256) + ref(T_3, 256)$.

• By using our knowledge on the degrees of $q \times P$ and $T_3$, we are able to write:

  • $ref(q \times P, 256) = ref(q, 127) \times ref(P, 129) \times X \equiv 0 \pmod{ref(P, 129)}$. We will denote in the sequel $p = ref(P, 129)$.

  • $ref(T_3, 256) = ref(T_3, 128) \times X^{128}$.

We deduce from the above properties that $ref(T_3,128) \times X^{128} \pmod{p} = A \times B \times X \pmod{p}$, which reconstructs the reasoning behind Gueron's equality in Gue2013:

Recognizing Montgomery Fast Reduction

Montgomery reduction (either on integers or on polynomials) is a necessary step in the multiplication using elements in Montgomery form. When working with a fixed modulus $n$, instead of using a residue $a \bmod n$, one uses a residue $a^{\prime} = \lambda a \bmod n$ with $\gcd(\lambda, n) = 1$. All operations are made in the Montgomery domain before putting back the result in its usual form by dividing it by $\lambda$. With a clever choice of $\lambda$, the division can be a shift. Addition of elements in Montgomery form is unchanged as $\lambda a + \lambda b = \lambda (a+b) \pmod{n}$. The multiplication of elements in Montgomery form is a little trickier as $\lambda a \times \lambda b = \lambda^2 (ab) \pmod{n}$. To keep the result of a multiplication in the Montgomery form, one needs to compute efficiently the modular division by $\lambda$; it is the Montgomery reduction algorithm known as REDC.

The variant known as FastREDC is of particular interest to us. In our case, we work on binary polynomials (hence beware of hasty generalizations, e.g. we removed all signs), $\lambda = X^{128}$ and the modulus we consider is $p(X) = X^{128} + X^{127} + X^{126} + X^{121} + 1$.

To recognize the Montgomery reduction in the optimization proposed in Gue2013, we have to notice that $p(X)= X^{128} + \mathtt{0xc2(0^{14})}(X) \times X^{64} + 1$, where $\mathtt{0xc2(0^{14})}(X)$ stands for the polynomial of degree 63 whose sequence of coefficients is 0xc2(0^14). We also have that $p^\prime = p^{-1} \pmod{X^{128}} = \mathtt{0xc2(0^{14})}(X) X^{64} + 1$. The fact that $p$ and $p^{\prime}$ uses the same constant 0xc2(0^14) forces us to understand finely the optimization if we are to apply it with other parameters.

Doing the computation by hand to check that the given algorithm corresponds to the optimization proposed in Gue2013 is left as an exercise to the reader.

Equivalence between Optimizations

If we make the assumption that Ozturk and Gopal's PCLMULQDQ-based reduction and Gueron's Montgomery reduction should rely on the same principle implemented slightly differently, we can simultaneously prove the equivalence between the two optimizations and deduce the value of POLY2.

In fact, by fixing POLY2 to be the constant 0xC2(0^21)1C2(0^6), both computations end up being a Montgomery reduction, trading two vpshufd instructions against one pclumulqdq.

The trick to find the value of POLY2 was to check in one Intel's GCM reference implementation, but it can also be painfully reconstructed by hand with the equivalence assumption in mind.

Again, doing the computation by hand is left as an exercise to the reader.

Putting Things Together

If we refer to BZ2010, Barrett's and Montgomery's algorithms are MSB and LSB variants of a division algorithm. The former is the classical division algorithm where one wants to cancel most significant digits and find the remainder; in the latter, one wants to cancel least significant digits and keep the most significant ones. Therefore, they naturally correspond to each other respectively on reflected and straight inputs.

We can see that the first so-called Barret's optimization allows easily to substitute pclmulqdq instructions by XORs and shifts. It is not the case anymore with the so-called Montgomery's optimization as computations involve modular multiplications with high degree polynomials. This can explain why trying to work directly with reflected inputs was not the priority in times when pclmulqdq was rather slow.