DES Encryption
Overview
In 1972, the National Institute of Standards and Technology (called the National Bureau of Standards at the time) decided that a strong cryptographic algorithm was needed to protect nonclassified information. The algorithm was required to be cheap, widely available, and very secure. NIST envisioned something that would be available to the general public and could be used in a wide variety of applications. So they asked for public proposals for such an algorithm. In 1974 IBM submitted the Lucifer algorithm, which appeared to meet most of NIST's design requirements.
NIST enlisted the help of the National Security Agency to evaluate the security of Lucifer. At the time many people distrusted the NSA due to their extremely secretive activities, so there was initially a certain degree of
skepticism regarding the analysis of Lucifer. One of the greatest worries was that the key length, originally 128 bits, was reduced to just 56 bits, weakening it significantly. The NSA was also accused of changing the algorithm to plant a "back door" in it that would allow agents to decrypt any information without having to know the encryption key. But these fears proved unjustified and no such back door has ever been found.
The modified Lucifer algorithm was adopted by NIST as a federal standard on November 23, 1976. Its name was changed to the Data Encryption Standard (DES). The algorithm specification was published in January 1977, and with the official backing of the government it became a very widely employed algorithm in a short amount of time.
Unfortunately, over time various shortcut attacks were found that could significantly reduce the amount of time needed to find a DES key by brute force. And as computers became progressively faster and more powerful, it was recognized that a 56bit key was simply not large enough for high security applications. As a result of these serious flaws, NIST abandoned their official endorsement of DES in 1997 and began work on a replacement, to be called the Advanced Encryption Standard (AES). Despite the growing concerns about its vulnerability, DES is still widely used by financial services and other industries worldwide to protect sensitive online applications.
To highlight the need for stronger security than a 56bit key can offer, RSA Data Security has been sponsoring a series of DES cracking contests since early 1997. In 1998 the Electronic Frontier Foundation won the RSA DES Challenge II2 contest by breaking DES in less than 3 days. EFF used a specially developed computer called the DES Cracker, which was developed for under $250,000. The encryption chip that powered the DES Cracker was capable of processing 88 billion keys per second. More recently, in early 1999,
Distributed. Net used the DES Cracker and a worldwide network of nearly 100,000 PCs to win the RSA DES Challenge III in a record breaking 22 hours and 15 minutes. The DES Cracker and PCs combined were testing 245 billion keys per second when the correct key was found. In addition, it has been shown that for a cost of one million dollars a dedicated hardware device can be built that can search all possible DES keys in about 3.5 hours. This just serves to illustrate that any organization with moderate resources can break through DES with very little effort these days.
In Depth
DES encrypts and decrypts data in 64bit blocks, using a 64bit key (although the effective key strength is only 56 bits, as explained below). It takes a 64bit block of plaintext as input and outputs a 64bit block of ciphertext. Since it always operates on blocks of equal size and it uses both permutations and substitutions in the algorithm, DES is both a block cipher and a product cipher.
DES has 16 rounds, meaning the main algorithm is repeated 16 times to produce the ciphertext. It has been found that the number of rounds is exponentially proportional to the amount of time required to find a key using a bruteforce attack. So as the number of rounds increases, the security of the algorithm increases exponentially.
Key Scheduling
Although the input key for DES is 64 bits long, the actual key used by DES is only 56 bits in length. The least significant (rightmost) bit in each byte is a parity bit, and should be set so that there are always an odd number of 1s in every byte. These parity bits are ignored, so only the seven most significant bits of each byte are used, resulting in a key length of 56 bits.
The first step is to pass the 64bit key through a permutation called Permuted Choice 1, or PC1 for short. The table for this is given below. Note that in all subsequent descriptions of bit numbers, 1 is the leftmost bit in the number, and n is the rightmost bit.
PC1: Permuted Choice 1
Bit 
0 
1 
2 
3 
4 
5 
6 
1 
57 
49 
41 
33 
25 
17 
9 
8 
1 
58 
50 
42 
34 
26 
18 
15 
10 
2 
59 
51 
43 
35 
27 
22 
19 
11 
3 
60 
52 
44 
36 
29 
63 
55 
47 
39 
31 
23 
15 
36 
7 
62 
54 
46 
38 
30 
22 
43 
14 
6 
61 
53 
45 
37 
29 
50 
21 
13 
5 
28 
20 
12 
4 
For example, we can use the PC1 table to figure out how bit 30 of the original 64bit key transforms to a bit in the new 56bit key. Find the number 30 in the table, and notice that it belongs to the column labeled 5 and the row labeled 36. Add up the value of the row and column to find the new position of the bit within the key. For bit 30, 36 + 5 = 41, so bit 30 becomes bit 41 of the new 56bit key. Note that bits 8, 16, 24, 32, 40, 48, 56 and 64 of the original key are not in the table. These are the unused parity bits that are discarded when the final 56bit key is created.
Now that we have the 56bit key, the next step is to use this key to generate 16 48bit subkeys, called K[1]K[16], which are used in the 16 rounds of DES for encryption and decryption. The procedure for generating the subkeys  known as key scheduling  is fairly simple:
1. Set the round number R to 1.
2. Split the current 56bit key, K, up into two 28bit blocks, L (the lefthand half) and R (the righthand half).
3. Rotate L left by the number of bits specified in the table below, and rotate R left by the same number of bits as well.
4. Join L and R together to get the new K.
5. Apply Permuted Choice 2 (PC2) to K to get the final K[R], where R is the round number we are on.
6. Increment R by 1 and repeat the procedure until we have all 16 subkeys K[1]K[16].
Here are the tables involved in these operations:
Subkey Rotation Table
Round Number 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
16 
Number of bits to rotate 
1 
1 
2 
2 
2 
2 
2 
2 
1 
2 
2 
2 
2 
2 
2 
1 
PC2: Permuted Choice 2
Bit 
0 
1 
2 
3 
4 
5 
1 
14 
17 
11 
24 
1 
5 
7 
3 
28 
15 
6 
21 
10 
13 
23 
19 
12 
4 
26 
8 
19 
16 
7 
27 
20 
13 
2 
25 
41 
52 
31 
37 
47 
55 
31 
30 
40 
51 
45 
33 
48 
37 
44 
49 
39 
56 
34 
53 
43 
46 
42 
50 
36 
29 
32 
Plaintext Preparation
Once the key scheduling has been performed, the next step is to prepare the plaintext for the actual encryption. This is done by passing the plaintext through a permutation called the Initial Permutation, or IP for short. This table also has an inverse, called the Inverse Initial Permutation, or IP^(1). Sometimes IP^(1) is also called the Final Permutation. Both of these tables are shown below.
IP: Initial Permutation
Bit 
0 
1 
2 
3 
4 
5 
6 
7 
1 
58 
50 
42 
34 
26 
18 
10 
2 
9 
60 
52 
44 
36 
28 
20 
12 
4 
17 
62 
54 
46 
38 
30 
22 
14 
6 
25 
64 
56 
48 
40 
32 
24 
16 
8 
33 
57 
49 
41 
33 
25 
17 
9 
1 
41 
59 
51 
43 
35 
27 
19 
11 
3 
49 
61 
53 
45 
37 
29 
21 
13 
5 
57 
63 
55 
47 
39 
31 
23 
15 
7 
IP^(1): Inverse Initial Permutation
Bit 
0 
1 
2 
3 
4 
5 
6 
7 
1 
40 
8 
48 
16 
56 
24 
64 
32 
9 
39 
7 
47 
15 
55 
23 
63 
31 
17 
38 
6 
46 
14 
54 
22 
62 
30 
25 
37 
5 
45 
13 
53 
21 
61 
29 
33 
36 
4 
44 
12 
52 
20 
60 
28 
41 
35 
3 
43 
11 
51 
19 
59 
27 
49 
34 
2 
42 
10 
50 
18 
58 
26 
57 
33 
1 
41 
9 
49 
17 
57 
25 
These tables are used just like PC1 and PC2 were for the key scheduling. By looking at the table is becomes apparent why one permutation is called the inverse of the other. For example, let's examine how bit 32 is transformed under IP. In the table, bit 32 is located at the intersection of the column labeled 4 and the row labeled 25. So this bit becomes bit 29 of the 64bit block after the permutation. Now let's apply IP^(1). In IP^(1), bit 29 is located at the intersection of the column labeled 7 and the row labeled 25. So this bit becomes bit 32 after the permutation. And this is the bit position that we started with before the first permutation. So IP^(1) really is the inverse of IP. It does the exact opposite of IP. If you run a block of plaintext through IP and then pass the resulting block through IP^(1), you'll end up with the original block.
DES Core Function
Once the key scheduling and plaintext preparation have been completed, the actual encryption or decryption is performed by the main DES algorithm. The 64bit block of input data is first split into two halves, L and R. L is the leftmost 32 bits, and R is the rightmost 32 bits. The following process is repeated 16 times, making up the 16 rounds of standard DES. We call the 16 sets of halves L[0]L[15] and R[0]R[15].
1. R[I1]  where I is the round number, starting at 1  is taken and fed into the EBit Selection Table, which is like a permutation, except that some of the bits are used more than once. This expands the number R[I1] from 32 to 48 bits to prepare for the next step.
2. The 48bit R[I1] is XORed with K[I] and stored in a temporary buffer so that R[I1] is not modified.
3. The result from the previous step is now split into 8 segments of 6 bits each. The leftmost 6 bits are B[1], and the rightmost 6 bits are B[8]. These blocks form the index into the Sboxes, which are used in the next step. The Substitution boxes, known as Sboxes, are a set of 8 twodimensional arrays, each with 4 rows and 16 columns. The numbers in the boxes are always 4 bits in length, so their values range from 015. The Sboxes are numbered S[1]S[8].
4. Starting with B[1], the first and last bits of the 6bit block are taken and used as an index into the row number of S[1], which can range from 0 to 3, and the middle four bits are used as an index into the column number, which can range from 0 to 15. The number from this position in the Sbox is retrieved and stored away. This is repeated with B[2] and S[2], B[3] and S[3], and the others up to B[8] and S[8]. At this point, you now have 8 4bit numbers, which when strung together one after the other in the order of retrieval, give a 32bit result.
5. The result from the previous stage is now passed into the P Permutation.
6. This number is now XORed with L[I1], and moved into R[I]. R[I1] is moved into L[I].
7. At this point we have a new L[I] and R[I]. Here, we increment I and repeat the core function until I = 17, which means that 16 rounds have been executed and keys K[1]K[16] have all been used.
When L[16] and R[16] have been obtained, they are joined back together in the same fashion they were split apart (L[16] is the lefthand half, R[16] is the righthand half),
then the two halves are swapped, R[16] becomes the leftmost 32 bits and L[16]
becomes the rightmost 32 bits of the preoutput block and the resultant 64bit number is called the preoutput.
Tables used in the DES Core Function
EBit Selection Table
Bit 
0 
1 
2 
3 
4 
5 
1 
32 
1 
2 
3 
4 
5 
7 
4 
5 
6 
7 
8 
9 
13 
8 
9 
10 
11 
12 
13 
19 
12 
13 
14 
15 
16 
17 
25 
16 
17 
18 
19 
20 
21 
31 
20 
21 
22 
23 
24 
25 
37 
24 
25 
26 
27 
28 
29 
43 
28 
29 
30 
31 
32 
1 
P Permutation
Bit 
0 
1 
2 
3 
1 
16 
7 
20 
21 
5 
29 
12 
28 
17 
9 
1 
15 
23 
26 
13 
5 
18 
31 
10 
17 
2 
8 
24 
14 
21 
32 
27 
3 
9 
25 
19 
13 
30 
6 
29 
22 
11 
4 
25 
SBox 1: Substitution Box 1
Row / Column 
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 
SBox 2: Substitution Box 2
Row / Column 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
0 
15 
1 
8 
14 
6 
11 
3 
4 
9 
7 
2 
13 
12 
0 
5 
10 
1 
3 
13 
4 
7 
15 
2 
8 
14 
12 
0 
1 
10 
6 
9 
11 
5 
2 
0 
14 
7 
11 
10 
4 
13 
1 
5 
8 
12 
6 
9 
3 
2 
15 
3 
13 
8 
10 
1 
3 
15 
4 
2 
11 
6 
7 
12 
0 
5 
14 
9 
SBox 3: Substitution Box 3
Row / Column 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
0 
10 
0 
9 
14 
6 
3 
15 
5 
1 
13 
12 
7 
11 
4 
2 
8 
1 
13 
7 
0 
9 
3 
4 
6 
10 
2 
8 
5 
14 
12 
11 
15 
1 
2 
13 
6 
4 
9 
8 
15 
3 
0 
11 
1 
2 
12 
5 
10 
14 
7 
3 
1 
10 
13 
0 
6 
9 
8 
7 
4 
15 
14 
3 
11 
5 
2 
12 
SBox 4: Substitution Box 4
Row / Column 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
0 
7 
13 
14 
3 
0 
6 
9 
10 
1 
2 
8 
5 
11 
12 
4 
15 
1 
13 
8 
11 
5 
6 
15 
0 
3 
4 
7 
2 
12 
1 
10 
14 
9 
2 
10 
6 
9 
0 
12 
11 
7 
13 
15 
1 
3 
14 
5 
2 
8 
4 
3 
3 
15 
0 
6 
10 
1 
13 
8 
9 
4 
5 
11 
12 
7 
2 
14 
SBox 5: Substitution Box 5
Row / Column 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
0 
2 
12 
4 
1 
7 
10 
11 
6 
8 
5 
3 
15 
13 
0 
14 
9 
1 
14 
11 
2 
12 
4 
7 
13 
1 
5 
0 
15 
10 
3 
9 
8 
6 
2 
4 
2 
1 
11 
10 
13 
7 
8 
15 
9 
12 
5 
6 
3 
0 
14 
3 
11 
8 
12 
7 
1 
14 
2 
13 
6 
15 
0 
9 
10 
4 
5 
3 
SBox 6: Substitution Box 6
Row / Column 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
0 
12 
1 
10 
15 
9 
2 
6 
8 
0 
13 
3 
4 
14 
7 
5 
11 
1 
10 
15 
4 
2 
7 
12 
9 
5 
6 
1 
13 
14 
0 
11 
3 
8 
2 
9 
14 
15 
5 
2 
8 
12 
3 
7 
0 
4 
10 
1 
13 
11 
6 
3 
4 
3 
2 
12 
9 
5 
15 
10 
11 
14 
1 
7 
6 
0 
8 
13 
SBox 7: Substitution Box 7
Row / Column 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
0 
4 
11 
2 
14 
15 
0 
8 
13 
3 
12 
9 
7 
5 
10 
6 
1 
1 
13 
0 
11 
7 
4 
9 
1 
10 
14 
3 
5 
12 
2 
15 
8 
6 
2 
1 
4 
11 
13 
12 
3 
7 
14 
10 
15 
6 
8 
0 
5 
9 
2 
3 
6 
11 
13 
8 
1 
4 
10 
7 
9 
5 
0 
15 
14 
2 
3 
12 
SBox 8: Substitution Box 8
Row / Column 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
10 
11 
12 
13 
14 
15 
0 
13 
2 
8 
4 
6 
15 
11 
1 
10 
9 
3 
14 
5 
0 
12 
7 
1 
1 
15 
13 
8 
10 
3 
7 
4 
12 
5 
6 
11 
0 
14 
9 
2 
2 
7 
11 
4 
1 
9 
12 
14 
2 
0 
6 
10 
13 
15 
3 
5 
8 
3 
2 
1 
14 
7 
4 
10 
8 
13 
15 
12 
9 
0 
3 
5 
6 
11 
How to use the SBoxes
The purpose of this example is to clarify how the Sboxes work. Suppose we have the following 48bit binary number:
011101000101110101000111101000011100101101011101
In order to pass this through steps 3 and 4 of the Core Function as outlined above, the number is split up into 8 6bit blocks, labeled B[1] to B[8] from left to right:
011101 000101 110101 000111 101000 011100 101101 011101
Now, eight numbers are extracted from the Sboxes  one from each box:
B[1] =
S[1](01, 1110) = S[1][1][14] = 3 = 0011 B[2] = S[2](01, 0010)
= S[2][1][2 ] = 4 = 0100 B[3] = S[3](11, 1010) = S[3][3][10] =
14 = 1110 B[4] = S[4](01, 0011) = S[4][1][3 ] = 5 =
0101 B[5] = S[5](10, 0100) = S[5][2][4 ] = 10 = 1010 B[6] =
S[6](00, 1110) = S[6][0][14] = 5 = 0101 B[7] = S[7](11, 0110)
= S[7][3][6 ] = 10 = 1010 B[8] = S[8](01, 1110) = S[8][1][14] =
9 = 1001
In each case of S[n][row][column], the first and last bits of the current B[n] are used as the row index, and the middle four bits as the column index.
The results are now joined together to form a 32bit number which serves as the input to stage 5 of the Core Function (the P Permutation):
00110100111001011010010110101001
Ciphertext Preparation
The final step is to apply the permutation IP^(1) to the preoutput. The result is the completely encrypted ciphertext.
Encryption and Decryption
The same algorithm can be used for encryption or decryption. The method described above will encrypt a block of plaintext and return a block of ciphertext. In order to decrypt the ciphertext and get the original plaintext again, the procedure is simply repeated but the subkeys are applied in reverse order, from K[16]K[1]. That is, stage 2 of the Core Function as outlined above changes from R[I1] XOR K[I] to R[I1] XOR K[17I]. Other than that, decryption is performed exactly the same as encryption.
Modes of Operation
ECB (Electronic Code Book)
This is the regular DES algorithm, exactly as described above. Data is divided into 64bit blocks and each block is encrypted one at a time. Separate encryptions with different blocks are totally independent of each other. This means that if data is transmitted over a network or phone line, transmission errors will only affect the block containing the error. It also means, however, that the blocks can be rearranged, thus scrambling a file beyond recognition, and this action would go undetected. ECB is the weakest of the various modes because no additional security measures are implemented besides the basic DES algorithm. However, ECB is the fastest and easiest to implement, making it the most common mode of DES seen in commercial applications. This is the mode of operation used by Private Encryptor.
CBC (Cipher Block Chaining)
In this mode of operation, each block of ECB encrypted ciphertext is XORed with the next plaintext block to be encrypted, thus making all the blocks dependent on all the previous blocks. This means that in order to find the plaintext of a particular block, you need to know the ciphertext, the key, and the ciphertext for the previous block. The first block to be encrypted has no previous ciphertext, so the plaintext is XORed with a 64bit number called the Initialization Vector, or IV for short. So if data is transmitted over a network or phone line and there is a transmission error
(adding or deleting bits), the error will be carried forward to all subsequent blocks since each block is dependent upon the last.
If the bits are just modified in transit (as is the more common case) the error
will only affect all of the bits in the changed block, and the corresponding
bits in the following block. The error doesn't propagate any further.
This mode of operation is more secure than ECB because the extra XOR step adds one more layer to the encryption process.
CFB (Cipher Feedback)
In this mode, blocks of plaintext that are less than 64 bits long can be encrypted. Normally, special processing has to be used to handle files whose size is not a perfect multiple of 8 bytes, but this mode removes that necessity (Private Encryptor handles this case by adding several dummy bytes to the end of a file before encrypting it). The plaintext itself is not actually passed through the DES algorithm, but merely XORed with an output block from it, in the following manner: A 64bit block called the Shift Register is used as the input plaintext to DES. This is initially set to some arbitrary value, and encrypted with the DES algorithm. The ciphertext is then passed through an extra component called the Mbox, which simply selects the leftmost M bits of the ciphertext, where M is the number of bits in the block we wish to encrypt. This value is XORed with the real plaintext, and the output of that is the final ciphertext. Finally, the ciphertext is fed back into the Shift Register, and used as the plaintext seed for the next block to be encrypted. As with CBC mode, an error in one block affects all subsequent blocks during data transmission. This mode of operation is similar to CBC and is very secure, but it is slower than ECB due to the added complexity.
OFB (Output Feedback)
This is similar to CFB mode, except that the ciphertext output of DES is fed back into the Shift Register, rather than the actual final ciphertext. The Shift Register is set to an arbitrary initial value, and passed through the DES algorithm. The output from DES is passed through the Mbox and then fed back into the Shift Register to prepare for the next block. This value is then XORed with the real plaintext (which may be less than 64 bits in length, like CFB mode), and the result is the final ciphertext. Note that unlike CFB and CBC, a transmission error in one block will not affect subsequent blocks because once the recipient has the initial Shift Register value, it will continue to generate new Shift Register plaintext inputs without any further data input. However, this mode of operation is less secure than CFB mode because only the real ciphertext and DES ciphertext output is needed to find the plaintext of the most recent block. Knowledge of the key is not required.
