1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Welcome to cryptography.SE. I've edited your question that may still need to be checked by you. There is no mysterious thing there. First for better question you need to clarify your algorithm ( though they are clear) , second, did you check the intermediate results with a code or math software? $\endgroup$ – kelalaka Aug 25 at 15:10
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – fgrieu Aug 25 at 21:38
2
$\begingroup$

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)
| improve this answer | |
$\endgroup$
  • $\begingroup$ thanks, it was a calculation mistake from my end.i just can't believe it, it was so stupid but i guess i was frustrated and keep making that mistake $\endgroup$ – Jordan jarvis Aug 25 at 19:32
  • $\begingroup$ I can guess. polynomials are confusing during the computations yet it is $GF(2^x)$, consider $GF(p^m)$ $\endgroup$ – kelalaka Aug 25 at 19:34
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I was making a program for aes and got stuck with this inverse problem. so after spending a lot of time in frustration i chose to just add a look up table for s-box as it will be fast but i was frustrated none the less as i couldn't create a s-box. why i am telling you this? because i got my answer from the first post and i won't be using your method right now but i wanna thank you for your time and if in future i ever need to make a program that use Euclidean algorithm for inverse i will refer to this answer. again thanks, i can finally sleep tonight as i solved this problem. $\endgroup$ – Jordan jarvis Aug 25 at 20:09
  • 1
    $\begingroup$ @Jordan jarvis : the method you used is workable with pen and paper, but hard to program without recursion, because it needs to keep a number of variables that grows with the number of steps, thus the degree in the worst case. $\endgroup$ – fgrieu Aug 25 at 21:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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