1. Home
2. The DES cryptosystem
3. The protocol explained

The math and definitions explained

The Data Encryption Standard (DES) cryptosystem was developed by IBM in the early 1970s in association with the United States National Security Agency (NSA) as a modification of an earlier cryptosystem called Lucifer. In 1977 DES was adopted as a government standard and it was only expected that DES would be used as a standard for 10-15 years, however it was a standard until 1999 where developing of its replacement the Advanced Encryption Standard (AES) had begun.

DES is a special type of iterated cipher called a Feistel cipher because the encryption and decryption algorithm are almost the same. The only difference is that during decrypting are the round keys used in reverse order compared to encryption.

In DES uses Alice and Bob the same 56-bit key \( K \) (the key is actually 64-bit, but 8 bits are used to validate the key) for encrypting and decrypting where plaintexts and ciphertexts are 64-bit. Because Alice and Bob uses the same key is DES called a symmetric cryptosystem where e.g. Alice sends the key to Bob with an asymmetric cryptosystem such as RSA or ElGamal. The reason why symmetric key cryptosystems are used when they first have to use an asymmetric cryptosystem to exchange the key, is because they are much faster than asymmetric cryptosystems.

A big difference between the following description of DES and an asymmetric cryptosystem is that we will operate with bits and their bitwise operations instead of integers and their arithmetic operations. And hence, plaintexts and ciphertexts are sometimes referred to as blocks in symmetric cryptosystems because they are bitstrings.

As previously described is DES based on the iterated Feistel cipher where the block (the plaintext or ciphertext) in each round (iteration) is divided into two halves \( L^{i} \) and \( R^{i} \) of equal length. Then in each round are \( L^{i} \) and \( R^{i} \) computed as:

\( \eqalign{ L^{i} &= R^{i-1} \\ R^{i} &= L^{i-1} \oplus f(R^{i-1}, K^{i}) } \)

where \( f \) is called the round function and is given the right half of the previously block \( R^{i-1} \) and the current round key \( K^{i} \) as input.

The encryption and decryption algorithm in DES is the above round repeated 16 times as illustrated in Figure 1 (see below) where the bock \( x \) (the plaintext or ciphertext) is first permuted accordingly to the initial permutation \( IP \) where the output is the two halves \( L^{0} \) and \( R^{0} \) (each 32-bit) which is used in the first round, i.e. \( IP(x) = L^{0}R^{0} \). After the 16 rounds is the block again permuted accordingly to the inverse initial permutation \( IP^{-1} \) where the output \( y \) is either the ciphertext (encryption) or the plaintext (decryption), i.e. \( y = IP^{-1}(R^{16}L^{16}) \) (notice that the two halves \( L^{16} \) and \( R^{16} \) are swapped before the inverse permutation is applied). The two permutations \( IP \) and \( IP^{-1} \) are fixed and have no cryptographic influence.

As illustrated in Figure 1 uses each round a 48-bit round key \( K^{i} \), but as previously described agrees Alice and Bob only on a single 56-bit key \( K \). To solve this problem they use a key schedule which diverts from the 56-bit key \( K \) the 16 round keys \( K^{1}, K^{2}, \dots, K^{16} \) where \( K^{i} \) is a certain permuted selection of bits from \( K \).

The round function \( f \) is illustrated in Figure 2 and executes the following steps:

1. First is the right half \( R^{i-1} \) expanded from 32-bit to 48-bit with the expansion function \( E \) by repeating 16 of the bits.
2. \( E(R^{-1}) \) is then XORed with the round key \( K^{i} \) and the result is divided into eight blocks of 6-bit, i.e. \( B = E(R^{-1}) \oplus K^{i} \) where \( B=B_{1}B_{2} \dots B_{6} \).
3. Each of the 6-bit blocks \( B_{i} \) are then substituted with a 4-bit block \( C_{i} \) using a S-box \( S_{i} \), i.e. \( C_{i} = S_{i}(B_{i}) \). In DES are there eight S-boxes and each S-box is a look-up table with 4 rows and 16 columns where each row contains the numbers 0 to 15 permuted in a specific order (the permutations where chosen to prevent certain types of attacks, see below). Given the 6-bit string \( B_{i} = b_{1}b_{2}b_{3}b_{4}b_{5}b_{6} \) and the S-box \( S_{i} \) the result \( C_{i} \) is computed as follows: The two bits \( b_{1}b_{6} \) determines the binary representation of the row \( 0 \leq r_{i} \leq 3 \) in \( S_{i} \) and the four bits \( b_{2}b_{3}b_{4}b_{5} \) determines the binary representation of the column \( 0 \leq c_{i} \leq 15 \) in \( S_{i} \). The entry \( (r_{i},c_{i}) \) in \( S_{i} \), which is a number between 0 and 15, is then converted to a binary number and denoted \( C_{i} \).
4. Finally is the 32-bit string \( C = C_{1}C_{2} \dots C_{8}\) permuted according to the permutation \( P \) and \( P(C) \) is the output of the function \( f \).

To clarify the use of the S-boxes we show how to compute the output \( C_{1} \) when given the input \( B_{1} = 011011 \) and the S-box \( S_{1} \) (see below). The first and last bits are \( b_{1}b_{6} = 01 \), which is the binary representation of the integer 1, i.e. the row is \( r_{1} = 1\). The middle four bits are \( b_{2}b_{3}b_{4}b_{5} = 1101 \), which is the binary representation of the integer 13, i.e. the column is \( c_{1} = 13 \). Finally the result is the integer in entry \( (1, 13) \) (remember the first row and the first column in the table starts at index 0) which is \( 5 \) and in binary \( 0101 \), i.e. \( C_{1} = 0101 \).

The S-box \( S_{1} \)
	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

The S-boxes were designed to prevent certain types of attacks, especially a method called differential cryptanalysis which was discovered by IBM in the 1970s but kept secret in almost 20 years until it was rediscovered by Biham and Shamir in the early 1990s. Therefore, at the time DES was proposed some people suggested that the S-boxes might contain hidden trapdoors which would allow the NSA to decrypt messages while claiming that DES was secure. But when Biham and Shamir (re)discovered differential cryptanalysis it was clear that the S-boxes were designed to prevent this type of attack and not to make DES insecure.

Another property of the S-boxes that is vital to the security of DES is that the S-boxes are the only non-linear function in DES (the linear functions are the permutation \( P \) and the expanding function \( E \)). A cryptosystem that is only based on linear functions is easy to break with e.g. a known plaintext attack (given a plaintext and its corresponding ciphertext it's easy to compute the secret key). A function \( g \) is linear if it satisfies that \( g(A \oplus B) = g(A) \oplus g(B) \) for two bitstrings \( A \) and \( B \). E.g. let \( A = 101000 \) and \( A = 011011 \). We now want to show that the permutation \( P \) and the expanding function \( E \) are linear, but the S-boxes \( S_{i} \) are non-linear. Assume that the permutation is given as \( P(X) = x_{2}x_{4}x_{1}x_{3}x_{5}x_{6} \):

\( \eqalign{ P(A) \oplus P(B) &= P(101000) \oplus P(011011) = 001100 \oplus 100111 = 101011 \\ P(A \oplus B) &= P(101000 \oplus 011011) = P(110011) = 101011 } \)

i.e. \( P(A \oplus B) = P(A) \oplus P(B) \) and the permutation is a linear function. Now assume the expanding function is given by \( E(X) = x_{1}x_{2}x_{3}x_{4}x_{3}x_{4}x_{5}x_{6} \), i.e. it expands 6-bit to 8-bit:

\( \eqalign{ E(A) \oplus P(B) &= E(101000) \oplus E(011011) = 10101000 \oplus 01101011 = 11000011 \\ E(A \oplus B) &= E(101000 \oplus 011011) = E(110011) = 11000011} \)

i.e. \( E(A \oplus B) = E(A) \oplus E(B) \) and the expanding function is linear. FInally for the S-boxes we use the S-box \( S_{1} \):

\( \eqalign{ S_{1}(A) \oplus S_{1}(B) &= S_{1}(101000) \oplus S_{1}(011011) = 1101 \oplus 0101 = 1000 \\ S_{1}(A \oplus B) &= S_{1}(101000 \oplus 011011) = S_{1}(110011) = 1011 } \)

i.e. \( S_{1}(A \oplus B) \neq S_{1}(A) \oplus S_{1}(B) \) and the S-boxes are non-linear functions.

A serious flaw of DES is its short 56-bit keys and already in the 1990s it became feasible to break DES by a brute-force attack. I.e. given an input block \( x \) and an output block \( y \), we run the DES algorithm \( DES \) with difference keys until \( y = DES_{K}(x) \), and hence we have found the used key \( K \). One solution to this problem is to use DES multiple times. The most used method is called Triple DES and runs the DES algorithm three times using different keys:

\( y = TDES_{K_{1},K_{2},K_{3}}(x) = DES_{K_1}(DES_{K_2}(DES_{K_3}(x))) \)

Notice that \( K_{1} \), \( K_{2} \) and \( K_{3} \) are not the 48-bit round keys but 56-bit main keys.

A variant of Triple DES replace the middle DES encryption by a DES decryption, i.e. the middle DES algorithm runs with the round keys in reverse order. Now, if we chooses the keys in this version as \( K_{1} = K_{2} = K_{3}\) it's the same as running the DES algorithm once because we first encrypts and then decrypts the message which have no influence and finally we encrypts the message again. Another variant chooses the keys as \( K_{1} = K_{3} \), which reduces the key size. Finally, a variant called DES-X uses a single DES encryption combined with the input block \( x \) XORed with \( K_{1} \) and the output block \( y \) XORed with \( K_{3} \):

\( y = XDES_{K_{1},K_{2},K_{3}}(x) = DES_{K_2}(x \oplus K_{1}) \oplus K_{3} \)

The protocol

Key exchange
Alice and Bob agree on the 56-bit key \( K \).
Encryption
Alice: Uses the key \( K \) in the key schedule to generate the 16 48-bit round keys \(K^{1}, K^{2}, \dots, K^{16} \). Uses the round keys in the order \( K^{1}, K^{2}, \dots, K^{16} \) in the DES algorithm \( DES \) to encrypt the message \( m \) by \( c = DES_{K}(m) \).
Alice sends the 64-bit ciphertext \( c \) to Bob.
Decryption
	Bob: Uses the key \( K \) in the key schedule to generate the 16 48-bit round keys \( K^{1}, K^{2}, \dots, K^{16} \). Uses the round keys in the reverse order \( K^{16}, K^{15}, \dots, K^{1} \) in the DES algorithm \( DES \) to decrypt the ciphertext \( c \) by \( m = DES_{K}(c) \).

Try a demo of the encryption scheme here.

Example

Alice wants to send an encrypted message \( m \) to Bob. They first agree on a 56-bit key \( K = 10101001 \dots\) and both generates the 16 48-bit round keys with the key schedule:

\( \eqalign{ K^{1} &= \dots 10001000 \\ K^{2} &= \dots 11110001 \\ &\vdots \\ K^{16} &= \dots 00000000 } \)

Alice then encrypts the 64-bit message \( m = 10110011 \dots\) using the round keys in the order \( K^{1}, K^{2}, \dots K^{16} \) and sends the 64-bit ciphertext \( c = DES_{K}(m) = 10101011 \dots \) to Bob.

Bob decrypts the received ciphertext with the round keys in the reverse order \( K^{16}, K^{15}, \dots K^{1} \) by computing \( m = DES_{K}(c) = 10110011 \dots \).