Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|improve this question
@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
up vote 3 down vote accepted

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?

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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