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

Bounty: 150

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 + {e5}
``````

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:

{f7}x   + {ca}
------------------------
{4f}x + {e5} | {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} = {f7}  (multiply)
``````
``````{4f} * {09} = {01}  (find inverse)
{09} * {1a} = {ca}  (multiply)
``````

And the final step of the Euclidean Algorithm:

``````Step 3:

{a8}x + {fc}
--------------
{9a} | {4f}x + {e5}
{4f}x
------------
{e5}
{e5}
----
{00}
``````
``````{9a} * {9f} = {01}  (find inverse)
{9f} * {4f} = {a8}  (multiply)
``````
``````{9a} * {9f} = {01}  (find inverse)
{9f} * {e5} = {fc}  (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})*({f7}x + {ca})
= ({f6}x + {52}) - ({09}x^3 + {ea}x^2 + {92}x^2 + {50}x + {80}x + {9f})
= ({f6}x + {52}) - ({09}x^3 + {78}x^2 + {d0}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.

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.