Calculating the modular inverse of a polynomial with coefficients in GF(2^8). (AES)

Question

AES uses the following polynomial with coefficients in GF(2^8):

a(x) = {03}x^3 + {01}x^2 + {01}x + {02}

The inverse of this polynomial mod x^4 + 1 is:

a'(x) = {0b}x^3 + {0d}x^2 + {09}x + {0e}

But how do you calculate the inverse of a polynomial with coefficients in GF(2^8)? I have found a partial worked example here, but I cannot calculate the correct result and I'm not sure where I am going wrong.

---

Aside: I am using hexadecimal notation to represent the coefficients, which are polynomials themselves with coefficients in GF(2). For example:

{03} = {00000011} = x + 1
{01} = {00000001} = 1
{01} = {00000001} = 1
{02} = {00000010} = x

{0b} = {00001011} = x^3 + x + 1
{0d} = {00001101} = x^3 + x^2 + 1
{09} = {00001001} = x^3 + 1
{0e} = {00001001} = x^3 + 1

These elements of GF(2^8) are reduced modulo x^8 + x^4 + x^3 + x + 1 (the irreducible polynomial).

---

I have attempted to use the Extended Euclidean Algorithm to find the inverse, but I haven't been able to get the same result.

The following is my calculation so far.

Euclidean Algorithm

a(x) = {03}x^3 + {01}x^2 + {01}x + {02}
p(x) = {01}x^4 + {01}

I'm using polynomial long division to perform the Euclidean Algorithm:

Step 0:
                                   {f6}x   + {52}
                                 --------------------------------------------
{03}x^3 + {01}x^2 + {01}x + {02} | {01}x^4 + {00}x^3 + {00}x^2 + {00}x + {01}
                                   {01}x^4 + {f6}x^3 + {f6}x^2 + {f7}x
                                   ------------------------------------------
                                             {f6}x^3 + {f6}x^2 + {f7}x + {01}
                                             {f6}x^3 + {52}x^2 + {52}x + {a4}
                                             --------------------------------
                                                       {a4}x^2 + {a5}x + {a5}

Firstly, to find "how many times" {03} "goes in to" {01}, I work out the inverse of {03} mod x^8 + x^4 + x^3 + x + 1, which works out to be {f6}. This seems to work because when I multiply {f6} by {03} I get {01}, which "cancels" the first term.

The step of subtracting the two polynomials seems straightfoward. It's basically an XOR of the two bytes.

Next, I need to find out how many times {03} goes in to {f6}. I used long division to find {52}, which seems to work because {52} * {03} = {f6}. However, I don't think this method of using long division will always work, as this one just so happens to leave no remainder.

So far, my results are the same as the ones here.

Step 1:
                         {8a}x   + {4f}
                       ----------------------------------
{a4}x^2 + {a5}x + {a5} | {03}x^3 + {01}x^2 + {01}x + {02}
                         {03}x^3 + {89}x^2 + {89}x        
                         --------------------------------
                                   {88}x^2 + {88}x + {02}         
                                   {88}x^2 + {c7}x + {c7}
                                   ----------------------
                                             {4f}x + {c5}            

Again, I need to find out how many times {a4} "goes in to" {03}. I do this by finding the inverse of {a4} (which is {8f}), so {a4} * {8f} = {01}. Now that I can get to {01}, I believe I can get to {03} by multiplying this inverse by {03}, so {8f} * {03} = {8a}. Therefore, by the associative law I believe {a4} * {8a} = {03}, so {8a} must be the first coefficient in the quotient.

The same process applies for finding that {a4} * {4f} = {88}:

{a4} * {8f} = {01} (find inverse)
{8f} * {88} = {4f} (multiply)
{a4} * {4f} = {88} (check)

This seems to be working okay.

After multiplying back out and subtracting again, the remainder is {4f}x + {e5}. However, this is where I believe I am going wrong, as according to this example the remainder should be {4f}x + {a8} (or in decimal 79x + 168). I don't know where this {a8} is coming from.

Nonetheless, I've continued using the same method as above for the rest of the Euclidean Algorithm.

Step 2:

               {f3}x   + {ca}  
             ------------------------
{4f}x + {c5} | {a4}x^2 + {a5}x + {a5}
               {a4}x^2 + {bf}x         
               ----------------------
                         {1a}x + {a5}                  
                         {1a}x + {3f}          
                         ------------
                                 {9a}       

{4f} * {09} = {01}  (find inverse)
{09} * {a4} = {f3}  (multiply)

{4f} * {09} = {01}  (find inverse)
{09} * {1a} = {ca}  (multiply)

And the final step of the Euclidean Algorithm:

Step 3:

       {a8}x + {9a}       
     --------------
{9a} | {4f}x + {c5}
       {4f}x                
       ------------
               {c5}                      
               {c5}              
               ----
               {00}       

{9a} * {9f} = {01}  (find inverse)
{9f} * {4f} = {a8}  (multiply)

{9a} * {9f} = {01}  (find inverse)
{9f} * {c5} = {9a}  (multiply)

The remainder is zero, so I stop the Euclidean Algorithm.

Extended Euclidean Algorithm

To find the inverse of {03}x^3 + {01}x^2 + {01}x + {02}, I perform the auxillary calcuations (the "extended" part of the extended Euclidean Algorithm) using the quotients found above.

pi = pi-2 - (pi-1 * qi-2)

p0 = {00}

p1 = {01}

p2 = {00} - ({01})*({f6}x + {52})
   = {00} - {f6}x - {52}
   = {f6}x + {52}

p3 = {01} - ({f6}x + {52})*({8a}x + {4f})
   = {01} - ({8f}x^2 + {cc}x + {8c}x + {44})
   = {8f}x^2 + {40}x + {45}

p4 = ({f6}x + {52}) - ({8f}x^2 + {40}x + {45})*({f3}x + {ca})
   = ({f6}x + {52}) - ({09}x^3 + {ea}x^2 + {92}x^2 + {50}x + {80}x + {9f})
   = {09}x^3 + {78}x^2 + {26}x + {cd}

So according to my calculation the inverse of {03}x^3 + {01}x^2 + {01}x + {02} mod {01}x^4 + {01} is {09}x^3 + {78}x^2 + {26}x + {cd}.

However this isn't correct, as the inverse specified by AES should be {0b}x^3 + {0d}x^2 + {09}x + {0e}.

I realise that this is quite a worked example, but I was wondering if anyone could give me advice on where I may be going wrong. I'm using the extended algorithm and performing arithmetic on the coefficients in GF(2^8) (e.g. addition, multiplication).

I haven't been able to find a complete example of how to calculate inverse of a polynomial with coefficients in GF(2^8) anywhere (only a partial one), and I'm interested to find out how it can be done.

Answer 1

[Update]

Your calculation are individually correct. However, the polyonmial p4 you get at the end is almost the modular inverse you are looking for.

The steps of the extended Eulclid algorithm are: $$ \begin{array}{rcccc} p & = & 1 \times p & + & 0 \times a\\ a & = & 0 \times p & + & 1 \times a \\ r_0 & = & 1\times p & + &q_0 \times a \\ r_1 & = & q_1 \times p & + &(q_0q_1 + 1) \times a \\ r_2 & = & (q_1q_2 + 1)\times p & + & (q_2(q_0q_1 + 1) + q_0)\times a \end{array} $$ and the coefficients in front of $a$ are the polynomials $p_0$, $p_1$, $p_2$, $p_3$ and $p_4$ you computed. As you will see, the last line says that $$ p_4\times a \equiv r_2 \bmod p, $$ so the inverse of $a$ is indeed $p_4 \times r_2^{-1}$ and here the value $r_2$ is {9a}.

You are only one modular inverse in $GF(2^8)$ away from finishing your calculation.

---

I will present an alternative method to find the inverse of the polynomial.

Let $p(x) = ax^3 + bx^2 + cx + d$ a polynomial of degree $3$ in the polynomial ring of the finite field $GF(2^8)$. We want to find $q(x) = \alpha x^3 + \beta x^2 + \gamma x + \delta$ such that $p(x)q(x) \equiv 1 \bmod x^4 + 1$.

We compute the product $p(x)q(x)$: $$ \begin{array}{rcl} p(x)q(x) & = & a\alpha x^6 + (a\beta + \alpha b) x^5 + (a\gamma + b\beta + c\alpha) x^4 + \\ & & (a\delta + b\gamma + c\beta + d\alpha) x^3 + (b\delta + c\gamma + d\beta) x^2 +\\ & & (c\delta + d\gamma) x + d\delta. \end{array} $$ But we want the product mod $x^4 + 1$, and we have $x^4 \equiv -1 \bmod x^4 + 1$, and even better since we are in a field of characteristic two, we have $x^4 \equiv 1 \bmod x^4 + 1$, so $x^5 \equiv x \bmod x^4 + 1$ and $x^6 \equiv x^2 \bmod x^4 + 1$.

Therefore we have $$ \begin{array}{rcl} p(x)q(x) & \equiv & (a\delta + b\gamma + c\beta + d\alpha) x^3 +\\ & & (b\delta + c\gamma + d\beta + a\alpha) x^2 + \\ & & (c\delta + d\gamma + a\beta + b\alpha) x + \\ & & (d\delta + a\gamma + b\beta + c\alpha) \end{array}\mod x^4 + 1 $$ Since we want $p(x)q(x) \equiv 1 \bmod x^4 + 1$, we have to solve a system of linear equations: $$ \left\{\begin{array}{rcl} a\delta + b\gamma + c\beta + d\alpha & = & 0 \\ b\delta + c\gamma + d\beta + a\alpha & = & 0 \\ c\delta + d\gamma + a\beta + b\alpha & = & 0 \\ d\delta + a\gamma + b\beta + c\alpha & = & 1, \end{array}\right. $$ which can be rewritten as $$ \begin{bmatrix} a & b & c & d \\ b & c & d & a \\ c & d & a & b \\ d & a & b & c \end{bmatrix}\cdot \begin{bmatrix}\delta\\ \gamma \\ \beta \\ \alpha\end{bmatrix} = \begin{bmatrix}0\\0\\0\\1\end{bmatrix} $$ To find the coefficients $\alpha$, $\beta$, $\gamma$ and $\delta$ of the polynomial, we have only to find the inverse of the matrix: $$ \begin{bmatrix}\delta\\ \gamma \\ \beta \\ \alpha\end{bmatrix} = \begin{bmatrix} a & b & c & d \\ b & c & d & a \\ c & d & a & b \\ d & a & b & c \end{bmatrix}^{-1}\cdot\begin{bmatrix}0\\0\\0\\1\end{bmatrix} $$ In fact, the coefficients will be the last column of this matrix.

You can compute the inverse with a method such as Gauss elimination, where all computations are in the field $GF(2^8)$.

In this specific case, the matrix keeping your notation) is: $$ \begin{bmatrix} 03 & 01 & 01 & 02 \\ 01 & 01 & 02 & 03 \\ 01 & 02 & 03 & 01 \\ 02 & 03 & 01 & 01 \end{bmatrix} $$

Whichever method you use, I hope you will get through all the calculation.