LED (AES like) algorithm Decryption-Mixcolumn

Question

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[4][4]. 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][4] =
{
    { 4,  1, 2, 2 },
    { 8,  6, 5, 6 },
    { 11,14,10, 9 },
    { 2,  2,15,11 },
};
void MixColumn(unsigned char state[4][4])
{
    int i, j, k;
    unsigned char tmp[4];
    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];
    }
}

Answer 1

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 ""

Answer 2

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 :-)