Finite Fields Of the Form GF(2n)

4.6. 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 pⁿ where p is a prime and n is a positive integer. In Section 4.4, we looked at the special case of finite fields with order p. We found that, using modular arithmetic in Z_p, all of the axioms for a field (Figure 4.1) are satisfied. For polynomials over pⁿ, with n > 1, operations modulo pⁿ do not produce a field. In this section, we show what structure satisfies the axioms for a field in a set with pⁿ elements, and concentrate on GF(2ⁿ).

Motivation

Virtually all encryption algorithms, both symmetric and public key, involve arithmetic 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 convenience and for implementation efficiency, we would also like to work with integers 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 2ⁿ 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 will not work; equivalently, the set of integers modulo 2ⁿ, 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 Z_2ⁿ is questionable, as the following example illustrates.

---

[Page 120]

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.1. 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.5. In this case, the number of occurrences of the nonzero integers is uniform for multiplication. To summarize,   Integer 1 2 3 4 5 6 7   Occurrences in Z8 4 8 4 12 4 8 4   Occurrences in GF(23) 7 7 7 7 7 7 7 For the moment, let us set aside the question of how the matrices of Table 4.5 were constructed and instead make some observations. 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.1, which uses mod 8 arithmetic. All the nonzero elements defined by Table 4.5 have a multiplicative inverse, unlike the case with Table 4.1. The scheme defined by Table 4.5 satisfies all the requirements for a finite field. Thus, we can refer to this scheme as GF(23). For convenience, we show the 3-bit assignment used for each of the elements 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.