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.

  • 2
    $\begingroup$ @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). $\endgroup$ Jun 3, 2013 at 17:21

1 Answer 1


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?


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.