Finite Fields of the Form GF(2n)

FINITE FIELDS OF THE FORM GF(2ⁿ)

Earlier in this chapter, we mentioned that the order of a finite field must be of the form pn, where p is a prime and n is a positive integer. In Section 4.5, we looked at the special case of finite fields with order p. We found that, using modular arith- metic in Zp, all of the axioms for a field (Figure 4.2) are satisfied. For polynomials over pn, with n  >  1, operations modulo pn  do not produce a field. In this section,  we show what structure satisfies the axioms for a field in a set with pn elements and concentrate  on GF(2n).

Motivation

Virtually all encryption algorithms, both symmetric and public key, involve arith- metic operations on integers. If one of the operations that is used in the algorithm is division, then we need to work in arithmetic defined over a field. For conve- nience and for implementation efficiency, we would also like to work with inte- gers that fit exactly into a given number of bits with no wasted bit patterns. That is, we wish to work with integers in the range 0 through 2n - 1, which fit into an n-bit word.

Suppose we wish to define a conventional encryption algorithm that operates on data 8 bits at a time, and we wish to perform division. With 8 bits, we can represent integers in the range 0 through 255. However, 256 is not a prime number, so that if arithmetic is performed in Z256 (arithmetic modulo 256), this set of integers will not be a field. The closest prime number less than 256 is 251. Thus, the set Z251, using arithmetic modulo 251, is a field. However, in this case the 8-bit patterns representing the integers 251 through 255 would not be used, resulting in inefficient use of storage.

As the preceding example points out, if all arithmetic operations are to be used and we wish to represent a full range of integers in n bits, then arithmetic modulo 2n will not work. Equivalently, the set of integers modulo 2n for n > 1, is not a field. Furthermore, even if the encryption algorithm uses only addition and multiplication, but not division, the use of the set Z2n is questionable, as the follow- ing example illustrates.

Suppose we wish to use 3-bit blocks in our encryption algorithm and use only the operations of addition and multiplication. Then arithmetic modulo 8 is well defined, as shown in Table 4.2. However, note that in the multiplication table, the nonzero integers do not appear an equal number of times. For example, there are only four occurrences of 3, but twelve occurrences of 4. On the other hand, as was mentioned, there are finite fields of the form GF(2n), so there is in particular a finite field of order 23 = 8. Arithmetic for this field is shown in Table 4.6. In this case, the number of occurrences of the nonzero integers is uniform for multiplication. To summarize,

For the moment, let us set aside the question of how the matrices of Table 4.6 were constructed and instead make some observations.

1.         The addition and multiplication tables are symmetric about the main diagonal, in conformance to the commutative property of addition and multiplication. This property is also exhibited in Table 4.2, which uses mod 8 arithmetic.

2.         All the nonzero elements defined by Table 4.6 have a multiplicative inverse, unlike the case with Table 4.2.

3.         The scheme defined by Table 4.6 satisfies all the requirements for a finite field. Thus, we can refer to this scheme as GF(23).

4.         For convenience, we show the 3-bit assignment used for each of the ele- ments of GF(23).

Intuitively, it would seem that an algorithm that maps the integers unevenly onto themselves might be cryptographically weaker than one that provides a uniform mapping. Thus, the finite fields of the form GF(2n) are attractive for cryptographic algorithms.

To summarize, we are looking for a set consisting of 2n elements, together with a definition of addition and multiplication over the set that define a field. We can assign a unique integer in the range 0 through 2n  -   1 to each element of the set.

Keep in mind that we will not use modular arithmetic, as we have seen that this does not result in a field. Instead, we will show how polynomial arithmetic provides a means for constructing the desired field.

Modular Polynomial Arithmetic

Consider the set S of all polynomials of degree n - 1 or less over the field Zp. Thus, each polynomial has the form

where each ai takes on a value in the set {0, 1,  ..... , p  -   1}. There are a total of pn

different polynomials in S.

With the appropriate definition of arithmetic operations, each such set S is a finite field. The definition consists of the following elements.

1.                                                                               Arithmetic follows the ordinary rules of polynomial arithmetic using the basic rules of algebra, with the following two refinements.

2.                                                                               Arithmetic on the coefficients is performed modulo p. That is, we use the rules of arithmetic for the finite field  Zp.

3.                                                                               If multiplication results in a polynomial of degree greater than n - 1, then the polynomial is reduced modulo some irreducible polynomial m(x) of degree n. That is, we divide by m(x) and keep the remainder. For a polynomial f(x), the remainder is expressed as r(x) = f(x) mod m(x).

As with ordinary modular arithmetic, we have the notion of a set of residues in modular polynomial arithmetic. The set of residues modulo m(x), an nth-degree polynomial, consists of pn elements. Each of these elements is represented by one of the pn polynomials of degree m  < n.

The residue class [x + 1], (mod m(x)), consists of all polynomials a(x) such that a(x) K (x + 1) (mod m(x)). Equivalently, the residue class [x + 1] consists of all polynomials a(x) that satisfy the equality a(x) mod m(x) = x + 1.

It can be shown that the set of all polynomials modulo an irreducible nth-degree polynomial m(x) satisfies the axioms in Figure 4.2, and thus forms a finite field. Furthermore, all finite fields of a given order are isomorphic; that is, any two finite- field structures of a given order have the same structure, but the representation or labels of the elements may be different.

To construct the finite field GF(23), we need to choose an irreducible polynomial of degree  3.  There  are  only  two  such  polynomials:  (x3  + x2  + 1)  and  (x3 + x + 1). Using the latter, Table 4.7 shows the addition and multiplication tables for GF(23). Note that this set of tables has the identical structure to those of Table 4.6. Thus, we have succeeded in finding a way to define a field of order 23.

We can now read additions and multiplications from the table easily. For exam- ple, consider binary 100 + 010 = 110. This is equivalent to x2  +  x. Also consider 100  * 010  = 011, which is equivalent to x2  * x  = x3 and reduces to x  + 1.

Finding the Multiplicative Inverse

Just as the Euclidean algorithm can be adapted to find the greatest common divisor of two polynomials, the extended Euclidean algorithm can be adapted to find the multiplicative inverse of a polynomial. Specifically, the algorithm will find the multi- plicative inverse of b(x) modulo a(x) if the degree of b(x) is less than the degree of a(x) and gcd[a(x), b(x)] = 1. If a(x) is an irreducible polynomial, then it has no factor other than itself or 1, so that gcd[a(x), b(x)] = 1. The algorithm can be charac- terized in the same way as we did for the extended Euclidean algorithm for integers. Given polynomials a(x) and b(x) with the degree of a(x) greater than the degree of b(x), we wish to solve the following equation for the values v(x), w(x), and d(x), where d(x) = gcd[a(x), b(x)]:

a(x)v(x)  + b(x)w(x)  = d(x)

If d(x) = 1, then w(x) is the multiplicative inverse of b(x) modulo a(x).The calculations are as follows.

Table 4.8 shows the calculation of the multiplicative inverse of (x7 + x  +  1)  mod (x8 +  x4  +  x3  +  x  +  1). The result is that (x7  +  x  +  1)- 1  =  (x7). That is, (x7  + x  + 1)(x7)  K 1( mod (x8  + x4  + x3  + x  +  1)).

Computational Considerations

A polynomial f(x) in GF(2n)

can be uniquely represented by the sequence of its n binary coefficients (an - 1, an - 2, ..... , a0). Thus, every polynomial in GF(2n) can be represented by an n-bit number.

Tables 4.6 and 4.7 show the addition and multiplication tables for modulo . m(x) = (x³ + x + 1)  Table 4.6 uses the binary representation, and Table 4.7 uses the polynomial representation.

ADDITION We have seen that addition of polynomials is performed by adding corresponding coefficients, and, in the case of polynomials over Z2, addition is just the XOR operation. So, addition of two polynomials in GF(2n) corresponds to a bitwise XOR operation.

MULTIPLICATION There is no simple XOR operation that will accomplish multiplication in GF(2n). However, a reasonably straightforward, easily implemented technique is available. We will discuss the technique with reference to GF(28) using m(x) = x8 + x4 + x3 + x + 1, which is the finite field used in AES. The technique readily generalizes to GF(2n).

The technique is based on the observation that

A moment’s thought should convince you that Equation (4.12) is true; if you are not sure, divide it out. In general, in GF(2n) with an nth-degree polynomial p(x), we have xn mod p(x) = [p(x) - xn].

Now, consider a polynomial in GF(28), which has the form f(x) = b7x7  + b6x6 +

b5x5 + b4x4 + b3x3 + b2x2 + b1x +  b0. If we multiply by x, we have

If b7 = 0, then the result is a polynomial of degree less than 8, which is already in reduced form, and no further computation is necessary. If b7 = 1, then reduction modulo m(x) is achieved using Equation  (4.12):

It follows that multiplication by x (i.e., 00000010) can be implemented as a 1-bit left shift followed by a conditional bitwise XOR with (00011011), which represents (x4 + x3 + x + 1). To summarize,

Multiplication by a higher power of x can be achieved by repeated application of Equation (4.14). By adding intermediate results, multiplication by any constant in GF(28) can be achieved.

In an earlier example, we showed that for f(x)  = x6  + x4  + x2  + x  + 1, g(x)  =  x7  +        x + 1, and m(x) = x8 + x4 + x3 + x + 1, we have f(x) * g(x) mod m(x) = x7 + x6 + 1. Redoing this in binary arithmetic, we need to compute (01010111) * (10000011). First, we determine the results of multiplication by powers of  x:

(01010111) * (00000010) = (10101110)

(01010111) * (00000100) = (01011100) Ⓧ (00011011) = (01000111)

(01010111) * (00001000) = (10001110)

(01010111) * (00010000) = (00011100) Ⓧ (00011011) = (00000111)

(01010111) * (00100000) = (00001110)

(01010111) * (01000000) = (00011100)

(01010111) * (10000000) = (00111000)

So,

(01010111) * (10000011) = (01010111) * [(00000001) Ⓧ (00000010) Ⓧ (10000000)]

=  (01010111) Ⓧ (10101110) Ⓧ (00111000) = (11000001)

which is equivalent to x7 + x6 + 1.

Using a Generator

An equivalent technique for defining a finite field of the form GF(2n), using the   same irreducible polynomial, is sometimes more convenient. To begin, we need two definitions: A generator g of a finite field F of order q (contains q elements) is an element whose first q  - 1 powers generate all the nonzero elements of F. That is,   the elements of F consist of 0, g0, g1, ..... , gq - 2. Consider a field F defined by a polynomial f(x). An element b contained in F is called a root of the polynomial if  f(b) = 0. Finally, it can be shown that a root g of an irreducible polynomial is a generator of the finite field defined on that   polynomial.

Let us consider the finite field GF(23), defined over the irreducible polynomial x3 + x + 1, discussed  previously.  Thus,  the  generator  g  must  satisfy  f(g) = g3 + g + 1 = 0. Keep in mind, as discussed previously, that we need not find a numerical solution to this equality. Rather, we deal with polynomial arith- metic in which arithmetic on the coefficients is performed modulo 2. Therefore, the solution to the preceding equality is g3  =  -g  -  1  =  g  +  1. We now show that g in fact generates all of the polynomials of degree less than 3. We have the following.

g4  = g(g3)  = g(g  + 1)  = g2  +  g

g5  = g(g4)  = g(g2  + g)  = g3  + g2  = g2  + g  +   1

g6  = g(g5)  = g(g2  + g  + 1)  = g3  + g2  + g  = g2  + g  + g  + 1  = g2  +    1

g7  = g(g6)  = g(g2  + 1)  = g3  + g  = g  + g  + 1  = 1  =   g0

We see that the powers of g generate all the nonzero polynomials in GF(23). Also, it should be clear that gk = gk mod7 for any integer k. Table 4.9 shows the power representation, as well as the polynomial and binary representations.

In   general,  for GF(2ⁿ) with  irreducible  polynomial f(x),  determine   gⁿ = f(g) - gⁿ. Then calculate all of the powers of g from g^{n + 1} through g² - 2. The elements of the field correspond to the powers of g from g0 through g2 - 2 plus the value 0. For  multiplication  of  two  elements  in  the  field,  use  the  equality gk = gk mod(2 - 1) for any integer k.

Summary

In this section, we have shown how to construct a finite field of order 2n. Specifically, we defined GF(2n) with the following properties.

1.                                                  GF(2n) consists of 2n elements.

2.                                                  The binary operations + and x are defined over the set. The operations of addi- tion, subtraction, multiplication, and division can be performed without leav- ing the set. Each element of the set other than 0 has a multiplicative inverse.

We have shown that the elements of GF(2n) can be defined as the set of all polynomials of degree n - 1 or less with binary coefficients. Each such polynomial can be represented by a unique n-bit value. Arithmetic is defined as polynomial arithmetic modulo some irreducible polynomial of degree n. We have also seen that an equivalent definition of a finite field GF(2n) makes use of a generator and that arithmetic is defined using powers of the   generator.