Wednesday, May 11, 2016

field theory - Extended Euclidean Algorithm in $GF(2^8)$?



I'm trying to understand how the S-boxes are produced in the AES algorithm. I know it starts by calculating the multiplicative inverse of each polynomial entry in $GF(2^8)$ using the extended euclidean algorithm. However I am having some trouble understanding how to perform the euclidean algorithm with polynomials in a field. Could someone please explain how to do this with a step by step example?


Answer



Using Rijndael's finite field, the reducing polynomial is $x^8+x^4+x^3+x+1$.




Suppose we want to compute the inverse of $x^5+1$ in this field. We want to solve the equation
$$
a(x^5+1)+b(x^8+x^4+x^3+x+1)=1
$$
I like to use the Euclid-Wallis Algorithm. Since we are dealing with polynomials, I will write things rotated by $90^\circ$.



$$
\begin{array}{c|c}
x^8+x^4+x^3+x+1&0&1&\\\hline

x^5+1&1&0\\\hline
x^4+x+1&x^3&1&x^3\\\hline
x^2+x+1&x^4+1&x&x\\\hline
\color{#C00000}{1}&\color{#C00000}{x^6+x^5+x^3+x^2+x}&\color{#C00000}{x^3+x^2+1}&x^2+x\\\hline
0&x^8+x^4+x^3+x+1&x^5+1&x^2+x+1
\end{array}
$$
The fifth row tells us that in $\mathbb{Z}_2[x]$
$$
(x^5+1)(\color{#C00000}{x^6+x^5+x^3+x^2+x})+(x^8+x^4+x^3+x+1)(\color{#C00000}{x^3+x^2+1})=\color{#C00000}{1}

$$
Thus, $x^6+x^5+x^3+x^2+x$ is the inverse of $x^5+1$ in $\left.\mathbb{Z}_2[x]\middle/(x^8+x^4+x^3+x+1)\mathbb{Z}_2[x]\right.$.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...