I am trying to figure out why it is necessary S-box's to be nonlinear. I have been searching for some materials but was not able to find out clear proof why it means that if we use S-box in DES, it would also be linear. I was watching Coursera's course for Cryptography. I didn't understand where this matrix $B$ comes from. We want to map 64 bits to 64 bits.
First, remember that we can write each of the ciphertext bits $$c_i = f_i(m_0,\ldots,m_{63}, k_1,\ldots, k_{63})$$ as the output of a non-linear functions $f_i$, $f_i \neq f_j, i \neq j$. If we remove the non-linear part from DES than this $f_i$ will be linear functions $f^l_i$. Now, turn back to matrix $B$;
- How do we build $B$ matrix?
Once we constructed the linear $f^l_i$ 's than the construction of the matrix $B$ is easy. Write the $f^l_i$'s a row vector so that the inner product with $[m,k_1,k_2,\ldots,k_{16}]$ will give out $c_i$s. To construct them, we need the actual definition of the new linear S-boxes, then we can write a program over the linear-DES to find $f^l_i$'s and then the vectors.
- But why should we use $[m,k_1,k_2,\ldots,k_{16}]$ column?
The non-linear DES version is now represented by a matrix $B$. Each $c_i$ is nothing but linear combination of $\{m_0,\ldots,m_{63},k_1,k_2,\ldots,k_{16}\}$. If you multiply by the column vector, it will give the ciphertext.
- Where does 832 comes from
$832 = 16\cdot 48+64$, the 16 rounds of the DES, 48-bit key per round, and 64 is the plaintext size.
- Why we have round keys $[k_1,k_2,\ldots,k_{16}]$ not the key bits in the equation.
The key generation of DES is not linear. To keep the equation in linear form the author of your document, preferred the round keys for the equations to keep the linearity.
if we use linear S-Box in DES,? $\endgroup$