# 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?

• You don't have to use exactly that way to find the multiplicative inverses. Any way to find them is valid, including just drawing up the 65536-element multiplication table and searching for products that happen to be $1$. – hmakholm left over Monica Oct 17 '13 at 0:15
• @Islands I haven't seen that notation before (very new to this). Can you explain the difference? – ConditionRacer Oct 17 '13 at 0:41
• @Justin984: are you talking about this version of $\mathrm{GF}(2^8)$, where the elements are viewed as polynomials? – robjohn Oct 17 '13 at 0:58
• @robjohn Yes, that's it. – ConditionRacer Oct 17 '13 at 1:01

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

• Took me a while to wrap my head around around your explanation of Euclid-Wallis, but that is a really great algorithm. Thanks! – ConditionRacer Oct 17 '13 at 3:41
• @Justin984: thanks for the comment. I have added some arrows to the explanation of the algorithm. Perhaps this might make it easier to understand. – robjohn Oct 17 '13 at 10:22
• I guess the first 2 steps are always the same, however further more steps are a little bit unclear. Can You give me a hint or a step by step explanation how is a round calculated according to this table? – ampika May 17 '17 at 15:32
• @ampika: All the steps, are pretty much as given in the Euclid-Wallis Algorithm. We just use polynomials and polynomial division. – robjohn May 17 '17 at 15:49
• Using the method above, I get the inverse of $x^4+1$ to be $x^7+x^5+x^4+x^2$. – robjohn May 18 '17 at 14:48

Here is the java code for EEAP for polynomials . There are two Polynomials f(x) and G(x) over the finite field M(x) and primeNumber.

package polynomial;

class PolyFunction { private int degree; private int coeff[];

PolyFunction(int deg, int coef) {
this.coeff = new int [deg+1];
this.coeff[deg] = coef;
this.degree  = deg;
}
int getDegree() {
int d = 0;
for (int i = 0; i < coeff.length; i++)
if (coeff[i] != 0) d = i;
return d;
}
for (int i = 0; i <= getDegree(); i++) {
if (coeff[i] < 0)
}

}

PolyFunction fx = this;
PolyFunction fPlusG = new PolyFunction(Math.max(fx.degree, gx.degree),0);
for (int i = 0; i <= fx.degree; i++) {
fPlusG.coeff[i] += fx.coeff[i];
}
for (int i = 0; i <= gx.degree; i++) {
fPlusG.coeff[i] += gx.coeff[i];
}
return fPlusG;
}

PolyFunction minus(PolyFunction gx, int primeNumber) {
PolyFunction fx = this;
PolyFunction fMinusg = new PolyFunction(Math.max(fx.degree, gx.degree), 0);
for (int i = 0; i <= fx.degree; i++) {
fMinusg.coeff[i] += fx.coeff[i];
}
for (int i = 0; i <= gx.degree; i++) {
fMinusg.coeff[i] -= gx.coeff[i];
}
//fMinusg.degree = fMinusg.getDegree();
return fMinusg;
}

PolyFunction multiple(PolyFunction gx) {
PolyFunction fx = this;
PolyFunction fMulg = new PolyFunction(fx.degree + gx.degree, 0);
for (int i = 0; i <= fx.degree; i++)
for (int j = 0; j <= gx.degree; j++)
fMulg.coeff[i+j] += (fx.coeff[i] * gx.coeff[j]);

return fMulg;
}

PolyFunction[] PLDA(PolyFunction gx, int primeNumber) {
PolyFunction fx  = this;

PolyFunction []qr = new PolyFunction[2];
qr[1] = fx;
qr[0] = new PolyFunction(0,0);

int degofQ = fx.getDegree() - gx.getDegree() ;

if (degofQ == 0 && gx.getDegree() == 0) {
//System.out.println("deg is zero");
int temp [] = EEA(primeNumber, gx.coeff[0]);
int divResult = (qr[1].coeff[qr[1].getDegree()] * temp[1]);

if ( divResult < 0)
qr[0] = new PolyFunction((qr[1].getDegree()-gx.getDegree()), divResult);
qr[1] = new PolyFunction(0, 0);
return qr;
}

if (degofQ < 0) {

qr[1] = gx;
qr[0] = fx;
return qr;
}

while((qr[1].getDegree() >= gx.getDegree()) && (qr[1].getDegree()!=0 && qr[1].coeff[0]!=0)) {

int divResult = (qr[1].coeff[qr[1].getDegree()] * temp[1]);

if ( divResult < 0)
PolyFunction tx = new PolyFunction((qr[1].getDegree()-gx.getDegree()), divResult);

PolyFunction txgx = tx.multiple(gx);

}
return qr;
}

PolyFunction fx = this;
PolyFunction []qr = new PolyFunction[2];

if ((gx.getDegree() == 0) && gx.coeff[0] == 0) {

int divResult = (1 * temp[1]);
if ( divResult < 0)

qr[0] = new PolyFunction(0, divResult);
qr[1] = new PolyFunction(0, 0);
return qr;
}
else {
PolyFunction []R = new PolyFunction[2];
PolyFunction q = qr[0];
PolyFunction r = qr[1];

PolyFunction ux = R[1];

return new PolyFunction[]{ux,vx};
}
}

public int[] EEA(int a, int b){
if(b == 0){
return new int[]{1,0};
} else {
int q = a/b;
int r = a%b;
int[] R = EEA(b,r);
return new int[]{R[1], R[0]-q*R[1]};
}
}
public String toString() {
if (degree ==  0) return "" + coeff[0];
if (degree ==  1) return coeff[1] + "x + " + coeff[0];

String ret = coeff[getDegree()] + "x^" + getDegree();

for (int i = getDegree()-1; i >= 0; i--) {
if      (coeff[i] == 0) continue;
else if (coeff[i]  > 0) ret = ret + " + " + ( coeff[i]);
else if (coeff[i]  < 0) ret = ret + " - " + (-coeff[i]);
if      (i == 1) ret = ret + "x";
else if (i >  1) ret = ret + "x^" + i;
}
return ret;
}


}

public class GF2 { private PolyFunction fx; private PolyFunction gx; private PolyFunction mx; private int primeNumber;

GF2(String file) {
fx = gx = mx = null;
return;
System.out.println("mx is " + mx);
System.out.println("fx is " + fx);
System.out.println("gx is " + gx);
}
int mxDeg = 0, fxDeg = 0, gxDeg = 0;
try {
int counter = 1;
String data = null;

switch(counter) {
case 1:
break;
case 2:
mxDeg = Integer.parseInt(data);
break;
case 3:
String [] mxToken = data.split("\\s+");
PolyFunction []p = new PolyFunction[mxToken.length+1];
for(int i=0; i < mxToken.length; i++) {
p[i] = new PolyFunction(mxDeg-i, Integer.parseInt(mxToken[i]));
}
mx = p[0];
for(int i=1; i < mxToken.length; i++)
break;
case 4:
fxDeg = Integer.parseInt(data);;
break;
case 5:
String [] fxToken = data.split("\\s+");
PolyFunction []pf = new PolyFunction[fxToken.length+1];
for(int i=0; i < fxToken.length; i++) {
pf[i] = new PolyFunction(fxDeg-i, Integer.parseInt(fxToken[i]));
}
fx = pf[0];
for(int i=1; i < fxToken.length; i++)
break;
case 6:
gxDeg = Integer.parseInt(data);
case 7:
String [] gxToken = data.split("\\s+");
PolyFunction []pg = new PolyFunction[gxToken.length+1];
for(int i=0; i < gxToken.length; i++) {
pg[i] = new PolyFunction(gxDeg-i, Integer.parseInt(gxToken[i]));
}
gx = pg[0];
for(int i=1; i < gxToken.length; i++)
break;
}
counter++;
}
} catch (FileNotFoundException e) {
System.out.println("Input file is not able to open");
return -1;
} catch (IOException e) {
e.printStackTrace();
return -1;
}
return 0;
}
void dmas() {
System.out.println("Subtraction is : " + fx.minus(gx, primeNumber));
PolyFunction fMulg = fx.multiple(gx);
if (fMulg.getDegree() >= mx.getDegree()) {
}
System.out.println("Multiplication is : " + fMulg.toString());

fDivg = fx.multiple(fDivg);
if (fDivg.getDegree() >= mx.getDegree()) {
}

System.out.println("Division is : " + fDivg);

}
public static void main(String[] args) {
String file = "src\\polynomial\\myinput.txt";
GF2 obj = new GF2(file);
obj.dmas();
}


}

// In “input.txt”: 1. First line is the prime number p. 2. Second line is the degree n of the irreducible polynomial m(x) over Zp. 3. Third line is the coefficients of m(x), from the leading coefficient to the constant, separated by one blank space. 4. Fourth line is the degree of f(x) over Zp. 5. Fifth line is the coefficients of f(x), from the leading coefficient to the constant, separated by one blank space. 6. Sixth line is the degree of g(x) over Zp. 7. Seventh line is the coefficients of g(x), from the leading coefficient to the constant, separated by one blank space. // Suppose we have data in input is 1> 7 2> 3 3> 1 0 0 3 4> 2 5> 2 0 1 6> 1

## 7> 3 2

output is 1> PrimeNumber is 7 2> mx is 1x^3 + 3 3> fx is 2x^2 + 1 4> gx is 3x + 2 5> Addition is : 2x^2 + 3x + 3 6> Subtraction is : 2x^2 + 4x + 6 7> Multiplication is : 4x^2 + 3x + 5

## 8> Division is : 6x^2 + 6x + 3

• Are you sure that this is an answer to the question ? – Claude Leibovici Mar 23 '16 at 11:49