3
$\begingroup$

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?
$\endgroup$
4
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.