Symmetric-Key Cryptography - Codes: The Guide to Secrecy from Ancient to Modern Times - page 118

can be analyzed in such a fashion that ultimately an inverse matrix m − 1 can be
found, so that

e = m − 1 c

and the key is recovered.
The only non -linear aspect of DES are the S-Boxes. Hence, an inherent
design of DES stipulates that no output bit of an S-Box can be a linear function
of the input bits. If they were, then the entire cryptosystem would be linear
and could be broken with a known-plaintext attack.
Now we list the principles that were revealed by Coppersmith in his article,
which concentrated upon the S-Boxes and their output. Thus, ensuring non-
linearity was the key to ensuring that the cryptosystem could not easily be
broken.

1. Linearity in the S-Box construction must be avoided. In other words, no
bit output by an S-Box is allowed to be anywhere near a linear function
of the input bits.

2. Each row of an S-Box should include all possible output bit combinations.

3. If two inputs to an S-Box differ in precisely one bit, or by exactly two middle
bits, then the outputs must differ in a minimum of two bits.

4. If two inputs to an S-Box differ in their first two bits, but have identical
last two bits, the two outputs must be distinct.

5. There are other criteria such as 2-4, which were designed to thwart differ-
ential cryptanalysis, and pertain primarily to the permutations that take
the outputs of the S-Boxes. Since these criteria are very technical, we do
not go into the details for the sake of e 0 ciency. The reader may consult
Coppersmith's paper [60] directly for the specifics, if necessary.

Now, we are ready for a detailed description of S-DES. First, recall our dis-
cussion and notation for permutations given on page 8, and the follow-up given
in the preceding section. The enciphering and deciphering in S-DES requires
several basic components. We begin with two of them that are permutations.

Initial Permutation
Let m =( m 1 m 2 m 3 m 4 m 5 m 6 m 7 m 8 ) be the byte of plaintext input. Then the
initial permutation IP acts according to the following transposition of places
where the plaintext sits, namely, IP retains all the plaintext bits, but merely
permutes them according to the rule given below.

IP
j 12345678
IP ( j ) 26314857