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.
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?
