The DES algorithm is rather unwieldy to use for examples, so in the present section we present an algorithm that has many of the same features, but is much smaller. Like DES, the present algorithm is a block cipher. Since the blocks are encrypted separately, we assume throughout the present discussion that the full message consists of only one block.

The message has 12 bits and is written in the form $L_0{R}_0$, where $L_0$ consists of the first six bits and $R_0$ consists of the last six bits. The key $K$ has nine bits. The $i$th round of the algorithm transforms an input $L_{i-1}{R}_{i-1}$ to the output $L_i{R}_i$ using an eight-bit key $K_i$ derived from $K$.

The main part of the encryption process is a function $f(R_{i-1}\text{,}{K}_i)$ that takes a six-bit input $R_{i-1}$ and an eight-bit input $K_i$ and produces a six-bit output. This will be described later.

The output for the $i$th round is defined as follows:

where $\oplus$ denotes XOR, namely bit-by-bit addition mod 2. This is depicted in Figure 7.1.

Figure 7.1 One Round of a Feistel System

This operation is performed for a certain number of rounds, say $n$, and produces the ciphertext $L_n{R}_n$.

How do we decrypt? Start with $L_n{R}_n$ and switch left and right to obtain $R_n{L}_n$. (Note: This switch is built into the DES encryption algorithm, so it is not needed when decrypting DES.) Now use the same procedure as before, but with the keys $K_i$ used in reverse order $K_n\text{,}\dots \text{,}{K}_1$. Let’s see how this works. The first step takes $R_n{L}_n$ and gives the output

We know from the encryption procedure that $L_n=R_{n-1}$ and $R_n=L_{n-1}\oplus f(R_{n-1}\text{,}{K}_n)$. Therefore,

The last equality again uses $L_n=R_{n-1}$, so that $f(R_{n-1}\text{,}{K}_n)\oplus f(L_n\text{,}{K}_n)$ is 0. Similarly, the second step of decryption sends $R_{n-1}{L}_{n-1}$ to $R_{n-2}{L}_{n-2}$. Continuing, we see that the decryption process leads us back to $R_0{L}_0$. Switching the left and right halves, we obtain the original plaintext $L_0{R}_0$, as desired.

Note that the decryption process is essentially the same as the encryption process. We simply need to switch left and right and use the keys $K_i$ in reverse order. Therefore, both the sender and receiver use a common key and they can use identical machines (though the receiver needs to reverse left and right inputs).

So far, we have said nothing about the function $f$. In fact, any $f$ would work in the above procedures. But some choices of $f$ yield much better security than others. The type of $f$ used in DES is similar to that which we describe next. It is built up from a few components.

The first function is an expander. It takes an input of six bits and outputs eight bits. The one we use is given in Figure 7.2.

Figure 7.2 The Expander Function

This means that the first input bit yields the first output bit, the third input bit yields both the fourth and the sixth output bits, etc. For example, 011001 is expanded to 01010101.

The main components are called S-boxes. We use two:

The input for an S-box has four bits. The first bit specifies which row will be used: 0 for the first row, 1 for the second. The other three bits represent a binary number that specifies the column: 000 for the first column, 001 for the second, ..., 111 for the last column. The output for the S-box consists of the three bits in the specified location. For example, an input of 1010 for ${\text{S}}_1$ means we look at the second row, third column, which yields the output 110.

The key $K$ consists of nine bits. The key $K_i$ for the $i$th round of encryption is obtained by using eight bits of $K$, starting with the $i$th bit. For example, if $K=010011001$, then $K_4=01100101$ (after five bits, we reached the end of $K$, so the last two bits were obtained from the beginning of $K$).

We can now describe $f(R_{i-1}\text{,}{K}_i)$. The input $R_{i-1}$ consists of six bits. The expander function is used to expand it to eight bits. The result is XORed with $K_i$ to produce another eight-bit number. The first four bits are sent to $S_1$, and the last four bits are sent to $S_2$. Each S-box outputs three bits, which are concatenated to form a six-bit number. This is $f(R_{i-1}\text{,}{K}_i)$. We present this in Figure 7.3.

Figure 7.3 The Function $f(R_{i-1}\text{,}{K}_i)$

For example, suppose $R_{i-1}=100110$ and $K_i=01100101$. We have

The first four bits are sent to $S_1$ and the last four bits are sent to $S_2$. The second row, fifth column of $S_1$ contains 000. The second row, last column of $S_2$ contains 100. Putting these outputs one after the other yields $f(R_{i-1}\text{,}{K}_i)=000100$.

We can now describe what happens in one round. Suppose the input is

and $K_i=01100101$, as previously. This means that $R_{i-1}=100110$, as in the example just discussed. Therefore, $f(R_{i-1}\text{,}{K}_i)=000100$. This is XORed with $L_{i-1}=011100$ to yield $R_i=011000$. Since $L_i=R_{i-1}$, we obtain

The output becomes the input for the next round.

For work on this and another simplified DES algorithm and how they behave under multiple encryption, see [Konikoff-Toplosky].