# 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
May 16 '20 at 12:42
• @corpsfini yes, $2 = (10)_2$, my mistake. thanks. Corrected. Yes, that is the direct one hiding the details. May 16 '20 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. Sep 17 '20 at 14:28
• Thanks to poncho for noticing the mistake. The matrix is not correctly transferred into sageMath. Now it should be correct. Sep 17 '20 at 16:47