Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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

Multipliying a 128-bit vector by a random square matrix of size 128 in $GF(2)$ yields a 128-bit vector. Output bit $j$ is the exclusive-OR of some of the input bits, as determined by the coefficients set in line $j$ of the matrix.

Each output bit is a linear combination of some of the input bits. The transformation qualifies as linear, for whatever definition of that. One definition often used in cryptanalysis is that a transformation $F$ is linear when $\forall X, \forall Y, F(X\oplus Y)=F(X)\oplus F(Y)\oplus F(0)$, where $0$ is the neutral element for $\oplus$, here the all-zero vector. Chaining linear transformations leads to a linear transformation, and this is bad for security in a block cipher. Further, here, we have $F(0)=0$, which might be an undesirable regularity.

Also, in the original statement, the transformation is was unlikely to be a bijection, which is undesirable for a block cipher algorithm of the permutation-substitution kind.

Update: in an AES round, the non-linearity comes from using an 8-bit substitution based on the multiplicative inverse in $GF(2^8)$, within the SubBytes step. Everything else is strictly linear.

share|improve this answer
Thank you for your answer. In this case, in AES, it's not the P-box alone (an affine transformation) that produces the non linearity but its combination with an inverse modulo a primitive polynomial ? Fgrieu, In fact I was speaking about invertible square matrix, so this is bijective. Thank you again. – user7060 Jun 3 '13 at 16:51

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.