Problems with calculating inverse of finite field $GF(2^8)$ of AES

Question

I know this question is being asked to death here but please hear me out.

I was learning how to encrypt using AES and in one of the methods, we have to calculate multiplicative inverse in the finite field $\operatorname{GF}(2^8)$ to make $S-box$.

I learned finite fields and its operations but while calculating the inverse of $x^7+x+1$(83 in hex) with $\bmod x^8+x^4+x^3+x+1$(standard for AES).

Here my calculations using extended Euclidean algorithm:

\begin{align} (x^8+x^4+x^3+x+1) &= (x^7+x+1)(x) + (x^4+x^3+x^2+1)\\ (x^7+x+1) &= (x^4+x^3+x^2+1)(x^3+x^2+1) + (x)\\ (x^4+x^3+x^2+1) &= (x)(x^3+x^2+x) + 1\\ \end{align}

now calculating $s$ and $t$ for $$(x^8+x^4+x^3+x+1) \cdot s + (x^7+x+1)\cdot t = 1$$

• let $a = x^8+x^4+x^3+x+1$,
• $b = x^7+x+1$,
• $c = x^4+x^3+x^2+1$,
• $d = x$

$$c + d(x^3+x^2+x) = 1$$

$$c + (x^3+x^2+x)(b + c(x^3+x^2+1)) = 1$$

$$c + (x^3+x^2+x)b + (x^6+x^4+x^3+x^2)c = 1$$

$$(x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)c = 1$$

$$(x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)(a + b(x)) = 1$$

$$(x^3+x^2+x)b + (x^6+x^4+x^3+x^2+1)a + (x^7+x^5+x^4+x^3+x)b$$

$$(x^6+x^4+x^3+x^2+1)a + (x^7+x^5+x^4+x^2)b$$

now, (c inverse) $$c^{-1} = t* \mod a$$

$$c^{-1} = t$$

$$=x^7+x^5+x^4+x^2$$

that is in hex = B4 which is not what this table shows http://tratliff.webspace.wheatoncollege.edu/2016_Fall/math202/inclass/sep21_inclass.pdf

the inverse should be 80(hex). While I was trying different values, I found that the values which are two steps or less in Extended Euclidean algorithm is correct means when it takes more than 2 steps I am getting different values of course I may be just mistaken here but this is what I know.

Ps:- I am trying to solve this mystery for 3 days now so any help is appreciated thank you

Answer 1

Let $g(x) = (x^8+x^4+x^3+x+1)$ and $p(x) = (x^7+x+1)$

The GCD is correct and it is $1$ as the last non zero remainders.

\begin{align} (x^8+x^4+x^3+x+1) &= (x^7+x+1)(x) + \color{blue}{(x^4+x^3+x^2+1)}\\ (x^7+x+1) &= (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)}\\ (x^4+x^3+x^2+1) &= (x^3+x^2+x)\color{red}{(x)} + 1\\ \end{align}

Now collect back to find to reach Bézout's identity $$a(x)g(x) + b(x)p(x) = d(x)$$ where $d(x)$ is the $\gcd(p(x),g(x))$

and we want to keep $g(x) $ and $p(x)$

---

begin from the last equation ( the last one that has non-zero remainder)

$$(x^4+x^3+x^2+1) = (x^3+x^2+x) \color{red}{(x)} + 1$$ change to (in $GF(2)$ we have $-1=1$)

$$1 = (x^4+x^3+x^2+1) + (x^3+x^2+x) \color{red}{(x)}$$

---

Now substitute $\color{red}{(x)}$ from the previous

$$(x^7+x+1) = (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)}$$

that is

$$\color{red}{(x)} = p(x) + (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)}$$

now substitute

\begin{align} 1 &= \color{blue}{(x^4+x^3+x^2+1)}) + (x^3+x^2+x)\big[(p(x) + (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)}\big]\\ 1 &= \color{blue}{(x^4+x^3+x^2+1)}) + (x^3+x^2+x)p(x) + (x^6 + x^2 + x)\color{blue}{(x^4+x^3+x^2+1)})\\ 1 &= (x^3+x^2+x)p(x) + (x^6 + x^2 + x +1)\color{blue}{(x^4+x^3+x^2+1)})\\ \end{align}

---

Now substitute $\color{blue}{(x^4+x^3+x^2+1)}$ from the first equation

$$g(x) = p(x)(x) + \color{blue}{(x^4+x^3+x^2+1)}$$

$$\color{blue}{(x^4+x^3+x^2+1)} = p(x)(x) + g(x)$$

\begin{align} 1 &= (x^3+x^2+x)p(x) + (x^6 + x^2 + x +1) \big[p(x)(x) + g(x)\big]\\ 1 &= (x^3+x^2+x)p(x) + (x^7 + x^3 + x^2 + x) p(x) + (x^6 + x^2 + x+1) g(x))\\ 1 &= (x^7 ) p(x) + (x^6 + x^2 + x) g(x))\\ \end{align}

Now that modulo $g(x)$ of both sides

$$1 = (x^7 ) p(x) $$ and this implies inverse of $p(x)^{-1} = x^7$

---

Note: for the field calculations I've used a Sagemath code as below, and this can be used for AES calculations.

#Base field
R.<y> = PolynomialRing(GF(2), 'y')

#Defining polynomial
G = y^8+y^4+y^3+y+1

#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()

#this is zero
X = x^8+x^4+x^3+x+1
print(X)

#GCD
print(X.gcd(x^7+x+1))
#to find and inverse use the 1/
1/(x^7+x+1)
#field calculations
(x^3+x^2+1)* (x^4+x^3+x^2+1) + (x)

Answer 2

The (full) extended Euclidean algorithm is best expressed as a single loop with 6 variables in addition to inputs

• Input: polynomials $a$ and $b$ with $a\ne 0$.
• Setup: $(r,\hat r,s,\hat s,t,\hat t)\gets(a,b,1,0,0,1)$
• Invariant: $a\,s+b\,t=r$ and $a\,\hat s+b\,\hat t=\hat r$
• Loop: while $\hat r$ is not $0$
  • $q\gets r/\hat r$
  • $(r,\hat r)\gets(\hat r,r−q\,\hat r)$
  • $(s,\hat s)\gets(\hat s,s−q\,\hat s)$
  • $(t,\hat t)\gets(\hat t,t−q\,\hat t)$
• Output: $(r,s,t)$ such that $a\,s+b\,t=r$ and $r$ is $\gcd(a,b)$

Proof of correctness:

• The Setup phase is such that the invariant is initially verified.
• Variables $r$ and $\hat r$ evolve just as the two variables in the standard Euclidean algorithm. In particular, at each loop iteration, $\hat r$ becomes the remainder of the division of the former $r$ by the former $\hat r$; hence the degree of $\hat r$ strictly decreases at each loop iteration (if any). Hence the loop will terminate, with $r=\gcd(a,b)$ as in the Euclidean algorithm.
• Each loop iteration does $(r,s,t)\gets(\hat r,\hat s,\hat t)$; hence $\hat s+b\,\hat t=\hat r$ which holds before the loop becomes $a\,s+b\,t=r$ after.
• Each loop iteration does $(\hat r,\hat s,\hat t)\gets(r−q\,\hat r,s−q\,\hat s,t−q\,\hat t)$; hence after the loop the new value of $a\,\hat s+b\,\hat t-\hat r$ is the value that $a\,(s−q\,\hat s)+b\,(t−q\,\hat t)-(r−q\,\hat r)$ has before. We can rewrite this quantity as $(a\,s+b\,t-r)-q\,(a\,\hat s+b\,\hat t-\hat r)$, and using the loop invariant that's $0$. Hence $a\,\hat s+b\,\hat t=\hat r$ after the loop.
• Hence the invariant holds. Thus $a\,s+b\,t=r$ on output.

When we want the modular inverse of $b$ modulo $a$, we check that the output $r$ is a constant polynomial other than $0$, and the desired inverse is $t/r$, that is $t$ when working in $GF(2^k)$. In a computer implementation where we do not want to check the invariant, we can do without the variables $s$ and $\hat s$.

This technique is easy to program, because it uses a fixed number of variables. Contrast with the method in the question, where we have to keep all the result of the first phase computing the $\gcd$, and reuse them afterwards in a backtracking phase computing $r$ and $s$.

This technique is also easy when doing the computations by hand.

Example with $a=x^8+x^4+x^3+x+1$ and $b=x^7+x+1$. $$\begin{array}{r|r|r|r} r&s&t\\ \hat r&\hat s&\hat r&q\gets r/\hat r\\ \hline x^8+x^4+x^3+x+1&1&0\\ x^7+x+1&0&1&x\\ x^4+x^3+x+1&1&x&x^3+x^2+1\\ x&x^3+x^2+1&x^4+x^3+x+1&x^3+x^2+x\\ 1&x^6+x^2+x+1&x^7&x\\ 0&\color{grey}{x^7+x+1}&\color{grey}{x^8+x^4+x^3+x+1}\\ \end{array}$$ This presentation avoids any duplication. We start by writing $a$ and $b$ in the top of the left column, and writing the constants $1,0$ and $0,1$ on their right.

On the right column, starting with the second line, $q$ is obtained by dividing the last two written terms on the left column.

New values are written on the first three columns by computing $r−q\,\hat r$, $s−q\,\hat s$, $t−q\,\hat t$ (where the variable with a $\hat\;$ is the most recently written one in the corresponding column, and the other is above).

We stop when a $0$ appears in he left column (and need not compute the two greyed terms on the right). The resulting $r$, $s$, $t$ are in the line above. When working with pen and paper, we can defer the computation of the second and third column until we have checked that this final $r$ is a constant polynomial, if that's desired.

If $a$ is irreducible and $b$ is not initially $0$, the final $r=\gcd(a,b)$ is always a constant polynomial, and always $1$ when working in $GF(2^k)$. This can be used to end the calculation and avoid the last line entirely.

When $b^{-1}\bmod a$ is thought, that is $t/r$, here $x^7$. The only use of the second column is checking that $a\,s+b\,t=r$ holds at each step.

---

An interesting variant of the algorithm does not compute $q$ exactly, instead keeping only it's high-order term. The number of steps tends to increase, but the computations are simpler.