Virtually all encryption algorithms, both symmetric and public key, involve arith- metic operations on integers.

**FINITE FIELDS OF
THE FORM GF(2 ^{n})**

Earlier in this chapter, we mentioned that
the order of a finite field must be of the form *p**n*, 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 Z*p*, all of the axioms for a field (Figure 4.2) are
satisfied. For polynomials over *p**n*, with *n *>
1, operations modulo *p**n *do
not produce a field. In this section, we
show what structure satisfies the axioms for a field in a set with *p**n *elements
and concentrate on GF(2*n*).

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 2*n *- 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 2*n *will not
work. Equivalently, the set of integers modulo 2*n *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 Z2*n *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(2*n*), 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(2*n*) are attractive for cryptographic algorithms.

To summarize,
we are looking for a set consisting of 2*n *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 2*n *- 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 Z*p*. 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 Z*p*.

**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 *n*th-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 *n*th-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 **

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 (*x*7 + *x *+ 1) mod
(*x*8 +
*x*4 + *x*3 +
*x
*+ 1). The result is that
(*x*7 + *x *+ 1)- 1 = (*x*7). That is, (*x*7 +
*x *+
1)(*x*7)
K 1( mod (*x*8 + *x*4 + *x*3 + *x *+ 1)).

Computational Considerations

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

can be uniquely represented by the sequence of its *n *binary coefficients (*an *- 1, *an *- 2, ..... , *a*0). Thus,
every polynomial in GF(2*n*) 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^{3} + 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(2

** MULTIPLICATION **There is no simple XOR
operation that will accomplish multiplication
in GF(2

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(2*n*) with an *n*th-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*) = *b*7*x*7 + *b*6*x*6 +

*b*5*x*5 + *b*4*x*4 + *b*3*x*3 + *b*2*x*2 + *b*1*x *+
*b*0. If we multiply by *x*, we have

If *b*7 = 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 *b*7 = 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 (*x*4 +
*x*3 + *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) **

**(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(2*n*), 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, *g*0, *g*1, ..... , *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 *x*3 + *x *+ 1,
discussed previously. Thus,
the
generator *g *must satisfy *f*(*g*) = *g*3 + *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 *g*3 = -*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.

*g*4 = *g*(*g*3) = *g*(*g *+
1) = *g*2 +
*g*

*g*5 = *g*(*g*4) = *g*(*g*2 +
*g*)
= *g*3 +
*g*2 =
*g*2 +
*g *+ 1

*g*6 = *g*(*g*5) = *g*(*g*2 +
*g *+
1) = *g*3 + *g*2 + *g *= *g*2 + *g *+ *g *+ 1
= *g*2 + 1

*g*7 = *g*(*g*6) = *g*(*g*2 +
1) = *g*3 + *g *= *g *+ *g *+ 1
= 1 = *g*0

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^{n})
with irreducible polynomial f(x), determine
g^{n} = f(g) - g^{n}. Then calculate all of the powers
of g from g^{n + 1} through g^{2} - 2. The elements of the field correspond to
the powers of *g *from *g*0 through *g*2 - 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 2*n*. Specifically, we defined GF(2*n*) with the following properties.

**1.
**GF(2*n*)
consists of 2*n *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(2*n*) 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(2*n*) makes use of a generator and that
arithmetic is defined using powers of the
generator.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : One Symmetric Ciphers : Basic Concepts in Number Theory and Finite Fields : Finite Fields of the Form GF(2n) |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.