Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I am reading about S-boxes.
By looking for the reason why the S-boxes are not linear, I found the following:
The mappings $B \mapsto S(B)$ are all non-linear, since it holds
$S(000000) \neq 0000$
We notice that at each of the 8 S-boxes $S_1, S_2, \dots, S_8$ , the number at the upper left-hand corner is not equal to zero and so $S$ cannot be linear.
Could you explain to me why at the S-boxes the number at the upper left-hand corner is not equal to zero ?
I don't believe you're really asking 'why did they select an SBox with 0 being mapped to something other than 0"; essentially, that's what the designers picked.
Instead, it is "why does $S(0) \ne 0$ prove that S is nonlinear".
And, the answer to that is, yes, it does, but only pedantically.
A function $S$ is linear if $S(a) + S(b) = S(a + b)$ for every $a, b$ (and some reasonable addition function "+", generally, we use bitwise xor). (And, this isn't quite sufficient if the range of $S$ is infinite, we never have to worry about that in crypto).
Now, if we select $a = b = 0$, this simplifies to $S(0) + S(0) = S(0+0) = S(0)$; or $S(0) = 0$.
Hence, if $S(0) \ne 0$, we know that the definition of linearity doesn't hold in all cases.
On the other hand, in crypto, when we talk about linear functions, we often really mean affine; the definition of this is $S(a) + S(b) = S(a + b) + c$, for all $a, b$ and some constant $c$ (which is independent of $a, b)$. The reason we're interested in this is that essentially all the mathematical tools an attacker can use against a linear function also work against an affine one, and so we tend not to make a strong distinction.
And, just looking at $S(0)$ won't tell you if a function is affine, as we have $S(0) = c$, and $c$ can be any value. If + is bitwise xor, you need to examine at least 4 values to prove that an Sbox is not affine.
