CIS 428 Introduction to Cryptography

Barbara Nostrand, Ph.D.

Electrical Engineering and Computer Science


Multiplicative Inverses in GF(28)

The field GF(28) is usually defined in the following way. Find a polynomial f(x) of degree 8 which is irreducible over GF(2). There are 30 of these to choose from. Then the polynomials of degree less than 8 over GF(2) form a set of size 28=256

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(28)

For example, suppose the polynomial were

     f(x) = x8 + x6 + x5 + x + 1
which is irreducible over GF(2). Then to add x7 + x3 + x + 1 and x4 + 1,  you would get x7 + x4 + x3 + x + 2,  and reducing the coefficients modulo 2, you get x7 + x4 + x3 + x,  which is the sum.  To multiply these same polynomials,  you get: 

        x11 + 2*x7 + x5 + x4 + x3 + x + 1
     -> x11 + x5 + x4 + x3 + x + 1
     -> x7 + x2 + x
which is the product.  In binary we have: 
  f(x) =       1 0 1 1 0 0 0 1 1
  a(x) =         1 0 0 0 1 0 1 1
  b(x) =         0 0 0 1 0 0 0 1

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

Now suppose you wish to invert the byte 11001001.  First figure out what polynomial a(x) the byte you want to invert is equivalent to.  Given a polynomial a(x) whose inverse you seek, perform the Extended Euclidean Algorithm on a(x) and f(x). If a(x) is not zero,  you will obtain polynomials r(x) and s(x) such that


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

     r(x)*a(x) = 1 (mod f(x))
a(x) will be the multiplicative inverse of r(x).

Example: Inverse of x4 + 1.


     x8 + x6 + x5 + x + 1 = (x4+x2+x+1)*(x4+1) + (x2)
     x4 + 1 = (x2)*(x2) + 1
and,  working backwards, 

     1 = 1*(x4+1) + (x2)*(x2)
       = 1*(x4+1) + (x2)*([x4+x2+x+1]*[x4+1]+[x8+x6+x5+x+1])
       = (x6+x4+x3+x2+1)*(x4+1) + (x2)*(x8+x6+x5+x+1)
so,  reducing modulo f(x)

     1 = (x6+x4+x3+x2+1)*(x4+1) (mod f(x))
Thus the multiplicative inverse sought is x6 + x4 + x3 + x2 + 1 which yields the byte 01011101

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)

Example 1

RemainderQuotientAuxiliary RemainderQuotientAuxiliary
x8+x6+x5+x+10 1 0 1 1 0 0 0 1 10 0 0 0 0 0 0 0
x4+11 0 0 0 0 1 0 0 0 10 0 0 0 0 0 0 1
x2x4+x2+x+1x4+x2+x+1 0 0 0 0 0 0 1 0 00 0 0 0 1 0 1 1 10 0 0 1 0 1 1 1
1x2x6+x4+x3+x2+1 0 0 0 0 0 0 0 0 10 0 0 0 0 0 1 0 00 1 0 1 1 1 0 1

Example 2

RemainderQuotientAuxiliary RemainderQuotientAuxiliary
x8+x4+x3+x+10 1 0 0 0 1 1 0 1 10 0 0 0 0 0 0 0
x+11 0 0 0 0 0 0 0 1 10 0 0 0 0 0 0 1
1x7+x6+x5+x4+x2+xx7+x6+x5+x4+x2+x 0 0 0 0 0 0 0 0 11 1 1 1 0 1 1 01 1 1 1 0 1 1 0

Polynomial Division over GF(2)

We will divide our characteristic polynomial x8+x4+x3+x+1 by x+1. 


1 0 0 0 1 1 0 1 1
1 1                 -> 1x7
  1 0 0 1 1 0 1 1
  1 1               -> 1x6
    1 0 1 1 0 1 1
    1 1             -> 1x5
      1 1 1 0 1 1
      1 1           -> 1x4
                    -> 0x3
          1 0 1 1
          1 1       -> 1x2
            1 1 1
            1 1     -> 1x1
                1   -> 0x0            
Yielding a quotient with coefficients 1 1 1 1 0 1 1 0 and a remainder of 0 0 0 0 0 0 0 1
Last modified: 2008 MAR 05
bnostran@syr.edu