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

-

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.

-
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