**Elements of S-DES (simplified Data
Encryption Standard)**

S-DES is a simplified version of the well-know DES (Data Encryption Standard) algorithm. It closely resembles the real thing, with smaller parameters, to facilitate operation by hand for pedagogical purposes. It is not intended as a real encryption tool, rather as a teaching tool. It was originated by Edward Schaefer, professor at Santa Clara University and a version ("Baby DES") is described in his online lecture notes.

All conventional encryption algorithms are based on two kinds of manipulation of the data: substitution and permutation.

**Substitution: **each element of the plaintext is mapped into another
element.

**Permutation:** the elements in the plaintext are rearranged. Permutation
is also called transposition.

**Substitution examples:**

Suppose that the 16 4-bit binary numbers are to be replaced by 2-bit values to which the following table corresponds them.

0000 01

0001 11

0010 00

0011 10

0100 11

0101 01

0110 10

0111 00

1000 00

1001 11

1010 10

1011 01

1100 01

1101 11

1110 11

1111 10

That constitutes a substitution cipher. Note it substitutes only 2 bits for 4. Many ciphers produce a ciphertext block of length equal to the plaintext block on which they operate. Those that do are called "block ciphers." Or, consider the Caesar cipher, wherein each letter of the alphabet is to be replaced by the letter that follows it 3 positions later in the alphabet. A replaced by D, B by E, C by F, and so on. Another substitution cipher.

**Permutation example:**

Suppose that the bits of a 4-bit binary number are to be re-ordered (or "transposed," or "permuted") such that the 2nd is promoted to 1st position, the 4th to 2nd. The 3rd is left alone, while the 1st is demoted to 4th. Then the 16 4-bit binary numbers, left column, get rearranged to the numbers shown, right column.

0000 0000

0001 0100

0010 0010

0011 0110

0100 1000

0101 1100

0110 1010

0111 1110

1000 0001

1001 0101

1010 0011

1011 0111

1100 1001

1101 1101

1110 1011

1111 1111

This permutation can be represented as "permutation P"

P |
|||

2 | 4 | 3 | 1 |

The numbers identify a bit from the input, and the table shows them as they are to be sequenced in the output. So given an input, pluck its second bit-- be it 1 or 0-- and write it down as the output's first bit. The input's 4th bit becomes the output's 2nd, and so on.

Most algorithms use both substitutions and permutations in combination, along with bitwise operations (e.g., XOR), and cascade them in a series of stages. Here is a diagram of the operational stages of S-DES.

**Fixed Permutations used in S-DES:**

S-DES involves several fixed operations involving particular permutations or other kinds of operators. It starts by using the following 8-bit permutation, its "initial permutation," hence dubbed IP:

IP |
|||||||

2 | 6 | 3 | 1 | 4 | 8 | 5 | 7 |

S-DES also needs to make use of its inverse. Writing an inverse can be a little tricky. The inverse of a permutation is the one that "puts the bits back" where they came from. Given the output of the above permutation, since its 1st bit was originally (in the input) the 2nd bit, we construct an inverse whose output's 2nd bit shall be its input's 1st.

IP |
|||||||

1 |

If we start with some input and subject it to IP, then take that result and
subject it to IP^{-1}, the original 2nd bit will have been
"dislodged" to 1st position, but then "relodged" back to 2nd
position.

Similarly, since the the IP output's 2nd bit used to be the input's 6th, we need an inverse permutation whose 6th bit will be its input's 2nd.

IP |
|||||||

1 | 2 |

The original input's 6th bit travels to 2nd position under IP. Then that 2nd
bit travels (back) to 6th position under IP^{-1}.

Proceeding this way for the rest of the bits, the entire inverse permutation becomes:

IP |
|||||||

4 | 1 | 3 | 5 | 7 | 2 | 8 | 6 |

S-DES uses an "expansion" permutation whereby 2 separate permutations are applied to a 4-bit number, and the 2 results pasted together to form an 8-bit final output.

E/P |
|||||||

4 | 1 | 2 | 3 | 2 | 3 | 4 | 1 |

It also employs a 4-bit permutation P4:

P4 |
|||

2 | 4 | 3 | 1 |

And it uses two so-called s-boxes, S0 and S1. Here is S0:

S0 = |
c0 | c1 | c2 | c3 | |

r0 |
1 | 0 | 3 | 2 | |

r1 |
3 | 2 | 1 | 0 | |

r2 |
0 | 2 | 1 | 3 | |

r3 |
3 | 1 | 3 | 2 |

And here is S1:

S1 = |
c0 | c1 | c2 | c3 | |

r0 |
0 | 1 | 2 | 3 | |

r1 |
2 | 0 | 1 | 3 | |

r2 |
3 | 0 | 1 | 0 | |

r3 |
2 | 1 | 0 | 3 |

Finally, it uses a swap operation called SW, wherein the right and left 4 bits of a byte are swapped. This is a permutation, and can be represented as such:

SW |
|||||||

5 | 6 | 7 | 8 | 1 | 2 | 3 | 4 |

These seven items, IP, IP^{-1}, E/P, P4, S0, S1, and SW are invariant
elements of S-DES. They are independent of its key and its input. Below is a diagram of S-DES's
operation when encrypting a byte of plaintext. It corresponds to the leftmost
column of the previous Figure 3.1, depicting the encryption process, with Figure
3.1's mysterious f_{K }opened up and revealed in the gray boxes. The
encircled plus sign symbolizes binary XOR. Notice the appearance at some stage
in the diagram of each of the seven elements.

Notice also the presence of two other inputs to the process, K_{1}
and K_{2}. They are "subkeys." S-DES has a particular, single
"main" key. Processing it by a set formula derives from it these two
subkeys. So they vary. They are both, always 8 bits but their value depends on
what value is chosen for the main key.

References:

Credit to __Cryptography and Network Security, Principles and Practice__,
William Stallings, Prentice Hall, 1999 for Figures 3.1 and 3.3, and precision of
explanation.

Rick Perry of Villanova University has a good explanatory page covering the operation of S-DES including excellent narration contrasting simplified DES with the real (much more complicated) thing.

John Holte, Gustavus Adolphus College, has S-DES instructions and an S-DES example on the website for his course.

William Stallings, prolific textbook author, short S-DES summary.