# LED (AES like) algorithm Decryption-Mixcolumn

I want to program decryption algorithm for the LED cipher. The lightweight block cipher LED(Jian Guo, Thomas Peyrin, Axel Poschmann, Matt Robshaw:CHES 2011). All the things is routine except the MixColumn component which is like the MixColumn of AES but with a different matrix. In fact we have 64 bit of plain text in structure of a state. In the MixColumn component each column of the state multiplies with the matrix M and the result will be replaced with the old column(in the encryption process) I wanna to have decryption so I need ReverseMixcolumn function.For that i need the inverted matrix M which I have no idea about calculating it. I know nothing about calculating matrix inverse in the field of operation. Even I dont know what is the field of operation in algorithm hence it is not pronounced in paper(eprint.iacr.org/2012/600.pdf)

This is code of MixColumn component:

const unsigned char MixColMatrix =
{
{ 4,  1, 2, 2 },
{ 8,  6, 5, 6 },
{ 11,14,10, 9 },
{ 2,  2,15,11 },
};
void MixColumn(unsigned char state)
{
int i, j, k;
unsigned char tmp;
for (j = 0; j < 4; j++) //j=0 soton 0
{
for (i = 0; i < 4; i++)
{
unsigned char sum = 0;
for (k = 0; k < 4; k++)
sum ^= FieldMult(MixColMatrix[i][k], state[k][j]);
tmp[i] = sum;
}
for (i = 0; i < 4; i++) //taaghir sotoon
state[i][j] = tmp[i];
}
}


The inverse of LED MDS matrix is :

$$\left[ \begin{array}{c c c c} 12 & 12 & 13 & 4 \\ 3 & 8 & 4 & 5\\ 7 & 6 & 2 & 14\\ 13 & 9 & 9 & 13\\ \end{array}\right]$$

you can verify it.

this is sage code that generates the inverse MDS matrix.

f=x^4+x^1+1  # irrudiciable polynomial
L.<z>= GF(2^4,modulus=f)
R=PolynomialRing(L,'x')
N=16
m=[(4,  1, 2, 2),(8,  6, 5, 6),(11,14,10, 9),(2,  2,15,11)]
T= matrix(m)
#print S.inverse()
print m
print T
P=matrix(L,4,4)
P_1=matrix(L,4,4)
for i in range(0,4):
for j in range(0,4):
P[i,j]= (T[i][j]) + z^1*(T[i][j]>>1) + z^2*(T[i][j]>>2) + z^3*(T[i][j]>>3)

print P
P_1=P.inverse()
print P_1
# print the matrix with clear distance
for i in range(0,4):
for j in range(0,4):
print P_1[i,j]
print ""


# The field

We're using a polynomial field here, where the nibbles (four-bit values) are coefficients to a 3th degree polynomial. As such, the $4$ in your matrix signifies $X^2$, the $B$ in your matrix signifies $X^3 + X + 1$. Operations are done over those polynomials. For example, $4+4 = X^2 + X^2 = 0$; note that addition can be trivially implemented using XOR (and thus subtraction and addition are equivalent).

Secondly, we note that we're actually working in a quotient ring, with modulus $P[X]=X^4+X+1$, which practically means that when we "overflow" beyond $X^4$ in our operation, we take the remainder modulo $P$. Since our modulus is irreducible, we have a field (with inversion). For example $4\times 4 = X^4 \pmod P = X+1 = 3$.

$z^{-1}$ is the inverse of $z$ if $z\cdot z^{-1} = 1 \mod P$. One way to compute this inverse is using the extended Euclidian algorithm.

# Matrix inversion

There are many ways to compute the matrix inverse, but the most "secondary school" way is probably Gauss-Jordan elimination. You start by writing $[M|I_n]$:

$$\left[\begin{array}{c c c c | c c c c} 4 & 1 & 2 & 2 & 1 & 0 & 0 & 0 \\ 8 & 6 & 5 & 6 & 0 & 1 & 0 & 0 \\ B & E & A & 9 & 0 & 0 & 1 & 0 \\ 2 & 2 & F & B & 0 & 0 & 0 & 1 \\ \end{array} \right]$$

And then you reduce this matrix to the form $[I_n|M^{-1}]$. There's one "but" in this story: you have to keep in mind that you are working with polynomials modulo $P$. Let us create a zero on the second row $r_2$. We note that we're lucky: $4\times 2 = X^2 \cdot X^1 = X^3 = 8$, so we can subtract $2\times r_1$ from row $r_2$. Subtraction is just a XOR operation, so we get

$$\left[\begin{array}{c c c c | c c c c} 4 & 1 & 2 & 2 & 1 & 0 & 0 & 0 \\ 0 & 4 & 1 & 2 & 2 & 1 & 0 & 0 \\ B & E & A & 9 & 0 & 0 & 1 & 0 \\ 2 & 2 & F & B & 0 & 0 & 0 & 1 \\ \end{array} \right]$$

Next up, you might want to get a 1 as first element of $r_1$, that's where you multiply the first row with the inverse of $4$. I inverted $4$ on paper, and I hope I didn't make any mistakes. $4\times 12 = x^2 \cdot (x^3 + x^2) \pmod P = 1$, so you would multiply $r_1$ with $12 \pmod P$.

Now, to do this by hand, it takes a while. That's where hardyrama's answer comes in: a computer can do this way faster. But at least now you know how you could do it!

P.S.: please be kind to any arithmetic errors. I used pen and paper, and I'm know for those mistakes :-)