## CIS 628 Introduction to Cryptography## Barbara Nostrand, Ph.D.## Electrical Engineering and Computer Science |

The field *GF(2 ^{8})* is usually defined in the following way. Find a
polynomial

**Addition** is the usual addition of polynomials (reducing coefficients
modulo 2), and **multiplication** is the usual multiplication of
polynomials (reducing coefficients modulo 2), followed by a reduction
modulo *f(x)* (and further coefficient reduction modulo 2) until the
result has degree less than 8. Using these operations, this set forms
a field isomorphic to *GF(2 ^{8})*.

For example, suppose the polynomial were

which is irreducible overf(x) = x^{8}+ x^{6}+ x^{5}+ x + 1

which is the product. In binary we have:x^{11}+ 2*x^{7}+ x^{5}+ x^{4}+ x^{3}+ x + 1 -> x^{11}+ x^{5}+ x^{4}+ x^{3}+ x + 1 -> x^{7}+ x^{2}+ x

f(x) =1 0 1 1 0 0 0 1 1a(x) =1 0 0 0 1 0 1 1b(x) =0 0 0 1 0 0 0 1a*b(x) =1 0 0 0 0 0 1 1 1 0 1 1f(x) =1 0 1 1 0 0 0 1 1r =1 1 0 0 1 0 0 0 1 1f(x) =1 0 1 1 0 0 0 1 1r =1 1 1 1 0 0 1 0 1f(x) =1 0 1 1 0 0 0 1 1r =1 0 0 0 0 1 1 0

Now suppose you wish to invert the byte ` 11001001`.
First figure out what polynomial

Then reduce this equation modulor(x)*a(x) + s(x)*f(x) = 1

r(x)*a(x) = 1 (mod f(x))

Example: Inverse of *x ^{4} + 1*.

and, working backwards,x^{8}+ x^{6}+ x^{5}+ x + 1 = (x^{4}+x^{2}+x+1)*(x^{4}+1) + (x^{2}) x^{4}+ 1 = (x^{2})*(x^{2}) + 1

so, reducing modulo1 = 1*(x4+1) + (x2)*(x2) = 1*(x^{4}+1) + (x^{2})*([x^{4}+x^{2}+x+1]*[x^{4}+1]+[x^{8}+x^{6}+x^{5}+x+1]) = (x^{6}+x^{4}+x^{3}+x^{2}+1)*(x^{4}+1) + (x^{2})*(x^{8}+x^{6}+x^{5}+x+1)

Thus the multiplicative inverse sought is1 = (x^{6}+x^{4}+x^{3}+x^{2}+1)*(x^{4}+1) (mod f(x))

You can remove the need to work backwards by keeping track of some
auxiliary quantities as you perform the **Euclidean Algorithm**.
The Auxiliary column always starts with 0 and 1. The Remainder column
always starts with the *characteristic polynomial* *f(x)* and
our *bit pattern* to invert *a(x)*. To fill in any subsequent row,
divide the remainders in the previous two rows, and put the quotient
in the Quotient column and the remainder in the Remainder column. Then
multiply the quotient times the Auxiliary value in the previous row
and add the Auxiliary value in the row before that, putting the
result in the Auxiliary column. These are not numeric additions and multiplications.
Rather, these repesent polynomial operations. When the remainder is reduced to 1,
the content of the Auxiliary column in that row is the inverse of
*a(x)*.

Remainder | Quotient | Auxiliary | Remainder | Quotient | Auxiliary |
---|---|---|---|---|---|

x^{8}+x^{6}+x^{5}+x+1 | 0 | 1 0 1 1 0 0 0 1 1 | 0 0 0 0 0 0 0 0 | ||

x^{4}+1 | 1 | 0 0 0 0 1 0 0 0 1 | 0 0 0 0 0 0 0 1 | ||

x^{2} | x^{4}+x^{2}+x+1 | x^{4}+x^{2}+x+1 |
0 0 0 0 0 0 1 0 0 | 0 0 0 0 1 0 1 1 1 | 0 0 0 1 0 1 1 1 |

1 | x^{2} | x^{6}+x^{4}+x^{3}+x^{2}+1 |
0 0 0 0 0 0 0 0 1 | 0 0 0 0 0 0 1 0 0 | 0 1 0 1 1 1 0 1 |

Remainder | Quotient | Auxiliary | Remainder | Quotient | Auxiliary |
---|---|---|---|---|---|

x^{8}+x^{4}+x^{3}+x+1 | 0 | 1 0 0 0 1 1 0 1 1 | 0 0 0 0 0 0 0 0 | ||

x+1 | 1 | 0 0 0 0 0 0 0 1 1 | 0 0 0 0 0 0 0 1 | ||

1 | x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+x | x^{7}+x^{6}+x^{5}+x^{4}+x^{2}+x |
0 0 0 0 0 0 0 0 1 | 1 1 1 1 0 1 1 0 | 1 1 1 1 0 1 1 0 |

We will divide our characteristic polynomial x^{8}+x^{4}+x^{3}+x+1 by x+1.

Yielding a quotient with coefficients1 0 0 0 1 1 0 1 1 1 1 -> 1x^{7}1 0 0 1 1 0 1 1 1 1 -> 1x^{6}1 0 1 1 0 1 1 1 1 -> 1x^{5}1 1 1 0 1 1 1 1 -> 1x^{4}-> 0x^{3}1 0 1 1 1 1 -> 1x^{2}1 1 1 1 1 -> 1x^{1}1 -> 0x^{0}

Last modified: 2008 MAR 05 bnostran@syr.edu