# Linear transformation proof

Ok, so I have this question and I honestly have no idea how to prove it. I know that the function is linear and I know it works for every possible combination, I just don't know how to prove it in an arbitrary manner. Here is the question:

Suppose that instead of using those S-boxes, DES would just substitute a 6-bit string with its first 4 bits, that is T(b1 b2 b3 b4 b5 b6 ) = b1 b2 b3 b4. We have called this transformation T. Show that T is a linear transformation (Note: you need to prove that T(x xor y) = T(x) xor T(y), for all 6-bit strings x and y, not just for a particular pair x and y; so write down a proof that works for arbitrary x and y).

I have no idea where to start since this class isn't about writing proofs.

We define $T$ as:

$T(B) = (b_0,b_1,b_2,b_3)$

We use $D$ to represent the difference of $X$ and $Y$:

$D = X \oplus Y$

Compute $T(D)$:

$T(D) = (d_0,d_1,d_2,d_3)$

$= (x_0 \oplus y_0, x_1 \oplus y_1, x_2 \oplus y_2, x_3 \oplus y_3)$

$=(x_0,x_1,x_2,x_3) \oplus (y_0,y_1,y_2,y_3)$

which is by definition of $T$:

$T(X) \oplus T(Y)$

• I didn't want to explain the whole proof. The original poster should still make some own thoughts.
– Nova
Commented Nov 6, 2014 at 18:44
• I think we should give complete answers to any questions asked. Commented Nov 6, 2014 at 19:48

Well, we start with a small definition of XOR for bit strings larger than zero bits. $x$ and $y$ are bit strings with the lenght $n$ and $x_{k}$ denoting the $k^{th}$ bit (from $0$ to $lenght - 1$). $||$ represents concatenation and $\oplus$ means XOR. So we get: $$x \oplus y = ((x_{0} \oplus y_{0}) || (x_{1} \oplus y_{1}) || ... || (x_{n-1} \oplus y_{n-1}))$$ Our function $T$ just returns the first 4 bits from a 6 bit string (or an arbitrarily large bit string longer or equal to 4 bits, it doesn't really matter), so we can write it as: $$T(b) = (b_{0} || b_{1} || b_{2} || b_{3})$$

Now we want to show that $T(x \oplus y) = T(x) \oplus T(y)$

How could we do that? Maybe we could insert the different definitions of our functions and see where it goes from there..?

(That's maybe not the most optimal way to answer this question, but (I think...) it works.)

• @JamesDoe: If you solved your own question, please post an answer to help anyone else if they ever have the same question. We can than vote on the answers and you can pick the best.
– Nova
Commented Oct 7, 2014 at 3:59
• I'm not necessarily saying I solved it haha Commented Oct 7, 2014 at 4:01
• @JamesDoe: Oh, okay. To be honest, I have no idea what you are talking about. I'm not familiar with higher math, despite studying informatic (with big globs of math).
– Nova
Commented Oct 7, 2014 at 4:05

This is what I have come up with:

Prove: T(x + y) = T(x) + T(y)
Suppose that f is a linear transformation from Rn to Rm with standard matrix T.
Then f(x) = T*x for every vector x in Rn. Therefore:
f(x + y) = T(x + y) = T(x) + T(y) (by a property of matrix operations) = f(x) + f(y).