1

I'm currently reading Introduction to Cryptography with Coding Theory by Wade Trappe. On Page 159, it talked about how to decrypt AES. Although the book is about Cryptography, this question is mathematical in nature. One step of AES requires the following operation: $$e_{i,j} = m_{i,j} * c_{i,j} \oplus k_{i,j}$$

where $e_{i,j}, m_{i,j}, c_{i,j}, and \space k_{i,j}$ are all $4 \times 4$ matrices. Each of the matrix's entry is in the form of 8 bits such as 0100 1010

To obtain $c_{i,j}$ in terms of $e_{i,j}$, the book, I believe, multiplies by $m_{i,j}^{-1}$ on both sides of the equation. The books states that $$c_{i,j} = m_{i,j} ^ {-1} e_{i,j} \oplus m_{i,j} ^ {-1} k_{i,j}$$

While the above statement would be true if we can somehow distribute over $\oplus$, I wonder whether the distributive law holds under $\oplus$. According to this post: Distributivity of XOR over Boolean matrix multiplication the distributivity law does not hold. I have thought about it, and I wonder whether the operations, in this case, are special. However, I can not identify a reason for that. So are the operations in the book legit and is it different from the case in the above post?

Thank you.

Matrix multiplication is done as normal. However, each byte is treated as a polynomial under the finite field $GF(2^8)$. XOR Operations between two matrices is equivalent to XORing every element in the same position of two matrices.

wsz_fantasy
  • 1,672
  • Can you elaborate on how the XOR operation between two matrices with vector entries is performed and also how the addition and multiplication in the matrix-matrix multiplication are defined? – Andreas Lenz Feb 03 '22 at 16:38
  • 1
    @AndreasLenz I have elaborated and edited the original question. Thank you for pointing this out. – wsz_fantasy Feb 03 '22 at 16:57

1 Answers1

1

The short answer to your question is: Yes, with the addition (XOR) and multiplication (polynomial multiplication) as defined in AES, the matrix multiplication is distributive.

The reason for this requires a little bit of abstract algebra and is explained below.

The matrix multiplication is distributive for matrices over arbitrary fields.

Suppose you have a (not necessarily finite) field $\mathbb{F}$. Then the multiplication of matrices over this field is distributive, i.e., for any matrices $A,B \in \mathbb{F}^{k\times m} $ and $ C \in \mathbb{F}^{m\times n}$, it holds that $$ (A+B)C = AC+BC $$ with the standard matrix-matrix multiplication. This fact directly follows from the distributivity of the underlying field, as outlined here.

What about the case of AES?

In AES, the underlying operations, i.e., the addition (XOR) and multiplication (polynomial multiplication) of $8$ bit vectors satisfy the field properties and thus the matrix-matrix multiplication is also distributive by the previous point - the operations are performed in the finite field $GF(2^8)$.

What goes wrong in the linked post (Boolean Matrix Multiplication)

Often (and also in the case of the linked post), the "addition" used inside the Boolean Matrix Multiplication (BMM) is defined as the standard "OR" operation (see here). Therefore the addition inside the BMM is defined differently as the addition between the two matrices, which is defined as an XOR operation. Since these two operations are not the same, this matrix-matrix multiplication is not distributive, as observed by the author in the linked post. Notice however that if we were to define the addition within the matrix-matrix multiplication also as an XOR, then we would also have matrix multiplication distributivity, as XOR and AND operations are nothing else than addition and multiplication over $\mathbb{F}_2$.

Andreas Lenz
  • 1,606