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 (reverse permutation, under construction) 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 (reverse permutation, under construction) 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-1 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 fK 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, K1 and K2. 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.