Data Encryption Standard (DES)

DES is a block cipher which has a block size of 64 bits and an effective key size of 56 bits. DES is an example of a sixteen round Feistel cipher. One consequence of this is that encryption and decryption use the same procedure but with reversed round keys. We show encryption here. The DES standard numbers bits such that the most significant bit is numbered as bit 1 which means that a block's least significant bit is numbered as bit 64. This convention is adopted here.

Before the sixteen rounds there is an Initial Permutation (IP), and after the rounds there is another permutation which is the inverse of the Initial Permutation (IP^-1). Each of the sixteen rounds comprises a 32-to-48-bit expansion (E), the introduction of 48-bit key material with an XOR (exclusive-or) operation, eight 6-to-4-bit S-boxes (S), and then a 32-bit permutation (P). As it's a Feistel cipher, the input block of 64-bits is split into two 32-bit halves: left (bits 1 to 32) and right (bits 33 to 64). If we take Li to be the left-hand side of round i and Ri to be the right-hand side of the same round then, if given a round key Ki, the round function can be can be written as follows:

	
Li = Ri-1
Ri = Li-1⊕P(S(E(Ri-1)⊕Ki))
	
      

Following the last round the left and right halves are exchanged.

Initial and Final Permutation

IP

The 64-bit block input is fed into an initial permutation (IP). The table below shows this 64-bit permutation. The table is constructed so that the first row contains entries 1 (0+1) to 8 (0+8) and the second row entries 9 (8+1) to 16 (8+8), and so on. If the n^th table entry contains 'm' then input bit 'm' is wired to output bit 'n'. As an example, we see that input bit number 58 is wired to output bit 1. Note that most of the tables in this document will have this format with the exception of the S-boxes.

IP

	1	2	3	4	5	6	7	8
0	58	50	42	34	26	18	10	2
8	60	52	44	36	28	20	12	4
16	62	54	46	38	30	22	14	6
24	64	56	48	40	32	24	16	8
32	57	49	41	33	25	17	9	1
40	59	51	43	35	27	19	11	3
48	61	53	45	37	29	21	13	5
56	63	55	47	39	31	23	15	7

The table can also be represented by a wiring diagram as follows. Here the input is at the top of the diagram and the output is at the bottom, and the leftmost bit is bit 1.

Inverse Initial Permutation (IP^-1)

The final stage is the inversion of the initial permutation. Since the initial permutation was known as IP, the inverse is known as IP^-1 as IP-1(IP(x))=x. The table below defines this 64-bit permutation.

IP^-1

	1	2	3	4	5	6	7	8
0	40	8	48	16	56	24	64	32
8	39	7	47	15	55	23	63	31
16	38	6	46	14	54	22	62	30
24	37	5	45	13	53	21	61	29
32	36	4	44	12	52	20	60	28
40	35	3	43	11	51	19	59	27
48	34	2	42	10	50	18	58	26
56	33	1	41	9	49	17	57	25

The following diagram gives the same information as is found in the table but in the form of a wiring diagram.

Key Dependent Computation

Here we detail the round function. As described above, the computation is

	
Li = Ri-1
Ri = Li-1⊕P(S(E(Ri-1)⊕Ki))
	
      

What follows is a description of E, S, and P.

E

The block E is a 32-to-48-bit expansion. Of the 32 input bits, 16 are duplicated to give the 48-bit output. The expansion is designed to give any two neighbouring S-boxes two common input bits. The table below defines the expansion.

E

	1	2	3	4	5	6
0	32	1	2	3	4	5
6	4	5	6	7	8	9
12	8	9	10	11	12	13
18	12	13	14	15	16	17
24	16	17	18	19	20	21
30	20	21	22	23	24	25
36	24	25	26	27	28	29
42	28	29	30	31	32	1

The following diagram gives the same information as is found in the table but in the form of a wiring diagram.

S-Boxes

The eight 6-to-4-bit S-boxes are numbered S₁ to S₈. The 48-bit input is fed into the boxes and a 32-bit result is output. S-box S₁ is given input bits 1 to 8, and S-box S₈ is given input bits 41 to 48.

If we have an input of b1b2b3b4b5b6 then we take the binary code b1b6 and use it to chose the row, then we use the binary code b2b3b4b5 to choose the column. The selected entry gives the 4-bit output of the S-box. To give an example, an input of 101010 gives row 10(2) and column 0101(5). The definition of the S-boxes now follow.

S1

S1

	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

S2

S2

	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

S3

S3

	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

S4

S4

	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

S5

S5

	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

S6

S6

	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

S7

S7

	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

S8

S8

	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

P

The block P is a 32-bit permutation. The following table defines this permutation.

P

	1	2	3	4	5	6	7	8
0	16	7	20	21	29	12	28	17
8	1	15	23	26	5	18	31	10
16	2	8	24	14	32	27	3	9
24	19	13	30	6	22	11	4	25

The following diagram gives the same information as is found in the table but in the form of a wiring diagram.

Key Schedule

The input key is a 64-bit value. Contained within the 64 bits is a 56-bit key and eight parity bits. The parity bits are added to give an odd number of 1 bits. The parity bits are removed by Permuted Choice 1 (PC1) which also splits the 56-bit key data into the two 28-bit registers C and D. A new round key is generated by rotating C and D by one or two places to the left. Just how many places is determined by the round number. From the rotated C and D registers, 48-bits of key data are extracted by Permuted Choice 2 (PC2). These 48-bits are then combined with the block data that has been output by the round expansion (E) as seen in the round function definition where Ki is the round key for round i:

	
Li = Ri-1
Li = Li-1⊕P(S(E(Ri-1)⊕Ki))
	
	

PC1

The Permuted Choice 1 (PC1) function removes the 8 parity bits from the 64-bit input and splits the 56-bits of key data into the two 28-bit registers C and D. Tables are given for the registers C and D. Here C is output bits 1 to 28, and D is output bits 29 to 56.

PC1 C

	1	2	3	4	5	6	7
0	57	49	41	33	25	17	9
7	1	58	50	42	34	26	18
14	10	2	59	51	43	35	27
21	19	11	3	60	52	44	36

PC1 D

	1	2	3	4	5	6	7
0	63	55	47	39	31	23	15
7	7	62	54	46	38	30	22
14	14	6	61	53	45	37	29
21	21	13	5	28	20	12	4

The same information given in the tables is shown here in a wiring diagram. Here C is the most significant 28 bits and D the least significant 28 bits.

Rotate

After PC1 the C and D registers are rotated either one or two places to the left. The number of places is a function of the round number. The table below connects the round number and the number of places to rotate.

Rotate

	Round
	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
Place(s)	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

A rotation of one place gives the following wiring diagram:

A rotation of two places gives the following wiring diagram:

PC2

Permuted Choice 2 (PC2) extracts 48 bits of key data from the result of the rotation of registers C and D. The table below defines this operation.

PC2

	1	2	3	4	5	6
0	14	17	11	24	1	5
6	3	28	15	6	21	10
12	23	19	12	4	26	8
18	16	7	27	20	13	2
24	41	52	31	37	47	55
30	30	40	51	45	33	48
36	44	49	39	56	34	53
42	46	42	50	36	29	32

The same information as given in the table above is shown below in a wiring diagram.

References

L. R. Knudsen, M. J. B. Robshaw, The Block Cipher Companion. Springer, 2011.
Data Encryption Standard (DES). FIPS Publication 46-3, 1999.