4
$\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$

2 Answers 2

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

$\endgroup$
9
  • 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$
    – user69015
    May 16, 2020 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, 2020 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, 2020 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, 2020 at 16:47
  • $\begingroup$ How does SageMath compute the result? $\endgroup$ Oct 27, 2022 at 9:54
0
$\begingroup$

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) {
                M[col][row] = galois::add(galois::mul(n, M[i][row]), M[col][row]);
                R[col][row] = galois::add(galois::mul(n, R[i][row]), R[col][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
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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