# How to find the inverse of a 3x3 MDS matrix

I implemented a block cipher similar to AES. But the reason I can't decrypt is that I can't get the inverse MDS matrix. The MDS matrix I used is a 3x3 MDS matrix on $$GF(2^8) \implies GF(2^8)$$ like AES

$$\begin{bmatrix} 1 & 2 &2 \\ 2 & 2 & 1\\ 2 & 1 & 2\\ \end{bmatrix}$$

The encryption process is the same as that of AES mixcolumns, and the MDS matrix used is as above.

I need the MDS inverse matrix required for decryption. What is the inverse of this MDS matrix on $$GF(2^8)$$?

I searched for Euclid-Wallis Algorithm or extended euclidean algorithm but I did not understand it well.

• How can I find the inverse of a 3x3 MDS matrix?

Your matrix contains 2 which is not an element of $$\operatorname{GF}(2^8)$$ unless it means $$x$$. In this case, we can use SageMath to find the inverse as

R.<x> = PolynomialRing(GF(2), 'x')
S.<y> = QuotientRing(R, R.ideal(x^8+x^4+x^3+x+1))
S.is_field()
S.cardinality()
y^8 + y^4 + y^3 + y + 1

A = matrix(S,[[1,y,y],[y,y,1],[y,1,y],])
A.inverse()


That produces this output

True
256
0

[                                  1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1]
[y^7 + y^6 + y^5 + y^4 + y^2 + y + 1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1                                   1]
[y^7 + y^6 + y^5 + y^4 + y^2 + y + 1                                   1 y^7 + y^6 + y^5 + y^4 + y^2 + y + 1]


The matrix written in standard binary representation is:

$$\begin{bmatrix} 00000001 & 11110111 & 11110111 \\ 11110111 & 11110111 & 00000001 \\ 11110111 & 00000001 & 11110111 \end{bmatrix}$$

• I think $2$ in his matrix might mean $x$ since $2=(10)_2$ in binary (and the field $GF(2^8)$ can be constructed directly with R.<x> = GF(2^8, modulus=x^8+x^4+x^3+x+1)).
– user69015
Commented May 16, 2020 at 12:42
• @corpsfini yes, $2 = (10)_2$, my mistake. thanks. Corrected. Yes, that is the direct one hiding the details. Commented May 16, 2020 at 12:49
• That's not correct; multiplying the original matrix with the supposed inverse doesn't yield the identity matrix; look at the dot product of the original third row with the inverse's third column. Commented Sep 17, 2020 at 14:28
• Thanks to poncho for noticing the mistake. The matrix is not correctly transferred into sageMath. Now it should be correct. Commented Sep 17, 2020 at 16:47
• How does SageMath compute the result? Commented Oct 27, 2022 at 9:54

This is how I was able to compute this result.

I want to show the C++ code I was able to write with these two answers. With the code we can invert any N sized matrix in the $$GF(2^8)$$ field. The full code can be found here.

These are the galois operations as shown by Thomas Pornin:

#include <iostream>
#include <array>

namespace galois {
constexpr int add(int x, int y) {
return x ^ y;
}

constexpr int mul(int x, int y) {
int z = 0;
for (int i = 0; i < 8; ++i) {
z ^= x & -(y & 1);
y >>= 1;
x <<= 1;
x ^= (0x11B & -(x >> 8));
}
return z;
}

constexpr int inverse(int x) {
int z = x;
for (int i = 0; i < 6; ++i) {
z = galois::mul(z, z);
z = galois::mul(z, x);
}
return galois::mul(z, z);
}

constexpr int divide(int x, int y) {
return mul(x, inverse(y));
}
}


And this is the matrix_inverse as described by Jyrki Lahtonen, but with using the galois operations:

template<std::size_t N>
using matrix = std::array<std::array<int, N>, N>;

template<std::size_t N>
matrix<N> matrix_inverse(matrix<N> M) {

matrix<N> R{}; //fills R with 0s
for (unsigned i = 0; i < N; ++i) {
R[i][i] = 1; //makes the matrix the identity matrix
}
for (unsigned i = 0; i < N; ++i) {

//sets M[i][i] to 1, divide by row by inverse
auto diagonal = M[i][i];
auto inv = galois::inverse(diagonal);
for (unsigned row = 0; row < N; ++row) {
M[i][row] = galois::mul(inv, M[i][row]);
R[i][row] = galois::mul(inv, R[i][row]);
}

//pivots the column
for (unsigned col = 0; col < N; ++col) {
if (col == i) continue;

auto n = M[col][i];
for (unsigned row = 0; row < N; ++row) {
}
}
}
return R;
}


And this is how we can call matrix_inverse to test the result:

template<std::size_t N>
void print_matrix(matrix<N> m) {
for (auto& i : m) {
for (auto& i : i) {
std::cout << i << ' ';
}
std::cout << '\n';
}
}
int main() {
matrix<3> m =
{ {
{1, 2, 2},
{2, 2, 1},
{2, 1, 2},
} };

std::cout << "Input -\n";
print_matrix(m);

matrix<3> inverse = matrix_inverse(m);

std::cout << "\nInverse -\n";
print_matrix(inverse);
}


As can be seen in the output, we calculated the correct inverse of your matrix:

Input -
1 2 2
2 2 1
2 1 2

Inverse -
1 247 247
247 247 1
247 1 247


As a second test, we can replicate the correct AES decryption MixColumns matrix:

matrix<4> m =
{ {
{2, 3, 1, 1},
{1, 2, 3, 1},
{1, 1, 2, 3},
{3, 1, 1, 2},
} };

matrix<4> inverse = matrix_inverse(m);

std::cout << "Inverse -\n";
print_matrix(inverse);


Output:

Inverse -
14 11 13 9
9 14 11 13
13 9 14 11
11 13 9 14