7
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I just wonder have you ever try implement in Mathematica/Maple/Sagemath or similar software and print the partial results and see your error? Like this try We are human and tend to have mistakes in our calculations. $\endgroup$
    – kelalaka
    Jun 12, 2020 at 7:56
  • $\begingroup$ @kelalaka Thanks for the encouragement. I wrote a program to help and came up with the same answer. I think there is a fundamental error in my calculations as opposed to there being a single mistake somewhere along the lines. $\endgroup$
    – inersha
    Jun 13, 2020 at 0:17
  • $\begingroup$ Your mistake is in step 1, the last line. The correct value for the remainder is {4f}x + {c5} and not {4f}x + {e5} since above you have to add {02} and {c7} (c and 0 should add to c and not e). $\endgroup$
    – user69015
    Jun 14, 2020 at 6:22
  • $\begingroup$ @corpsfini Very good spot, thank you. It turns out this was a typo as the calculations work out the same. I updated the post so it shows the correct coefficients. $\endgroup$
    – inersha
    Jun 14, 2020 at 14:23
  • $\begingroup$ @inersha I updated my answer to include why you didn't get the right answer. You were only missing one tiny step. $\endgroup$
    – user69015
    Jun 14, 2020 at 16:25

1 Answer 1

8
+150
$\begingroup$

[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.

$\endgroup$
1
  • $\begingroup$ Thank you for such a clear explanation. I wasn't aware that Gauss elimination would be a possibility for finding the inverse. I will try it and see if I can arrive at the correct inverse. $\endgroup$
    – inersha
    Jun 14, 2020 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.