# A substitution based on a matrix vector product

I choose at random an invertible square matrix A of size 128 in GF(2). I want to use this matrix as a substitution box. Is this a non linear transformation ?

I've seen that substitution boxes are the non linear parts of a block cipher algorithm, but the product between A and x is linear ? Not ? There is something that I don't understand.

Thank you.

-
@user7078 Welcome to Cryptography Stack Exchange. It looks like you got several accounts here. If you want them to be merged, register one of them (with the same mail address as the other one) and use the "merge user profiles" option on the contact us page (on the lower end of the page). – Paŭlo Ebermann Jun 3 '13 at 17:21

We call an operation F linear if the following holds:

$F(X+Y) = F(X) + F(Y)$

for all $X, Y$ within the appropriate set, and for some group operator $+$.

Now, if we consider matrix multiplication by a fixed matrix $A$, we do have the identity:

$A \cdot (X+Y) = A \cdot X + A \cdot Y$

for arbitrary vectors $X$, $Y$, and where $+$ is vector addition. Hence, matrix multiplication by any fixed matrix $A$ is linear.

When you are designing a block cipher, it is critically important that, for any group operator $+$, there be some component that is nonlinear with respect to that operator. Hence, matrix multiplication is probably not an ideal selection.

You appear to have some understanding of this; so what are you confused about?

-