Data Encryption Standard (DES)

Federal Information Processing Standards Publication 46-2, Dec. 30, 1993

Category: Computer Security

Subcategory: Cryptography

This publication describes a standard algorithm for encrypting binary coded information. The algorithm implements what is called symmetric key encryption. One key is used for both encrypting and decrypting. The DES algorithm uses a 64-bit key that consists of 56 bits of key data and 8 bits of parity error correction. The 8-bit parity check ensures that each 8-bit byte of the key has an odd number of 1s.

Many ways of implementing DES are mentioned (i.e. software, firmware, hardware) as well as different applications of the technology (i.e. to.protect theft of information stored on a vulnerable medium or information being transmitted between two points). The export control policies are of course mentioned.

There are four modes of operation of DES: Electronic Codebook (ECB) mode, Cipher Block Chaining (CBC) mode, Cipher Feedback (CFB) mode, and Output Feedback (OFB) mode. ECB operates like a standard block cipher, serially encrypting 64-bit blocks of data using the DES algorithm. CBC chains together blocks of cipher text. CFB uses previously generated ciphertext XORed with plaintext fed back into the DES algorithm. OFB is identical to CFB but uses the previous DES output rather than the previous cipher. These modes are described in more detail in FIPS PUB 81.

The DES algorithm.

To encrypt a 64-bit block of binary data D₁D₂D₃…D₆₄,

Using the following permutation table, rearrange the bits of the input data.

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

(e.g. rearrange to get D₅₈D₅₀D₄₂D₃₄D₂₆…D₂₃D₁₅D₇)

L ¬ D₅₈D₅₀D₄₃…D₁₆D₈ (the first 32 bits of the permuted input)
R ¬ D₅₇D₄₉D₄₁…D₁₅D₇ (the last 32 bits of the permuted input)
Using the following permutation table, rearrange the bits of R. Call this new 48-bit number R_new.

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

(e.g. rearrange to get D₇D₅₇D₄₉D₄₁…D₁₅D₇D₅₇ = R₃₂R₁R₂R₃…R₃₁R₃₂R₁)

Bitwise exclusive-or R_new with 48 unique bits of the 64-bit key K (by unique, we mean a set of 48 bits that has not been used before in the 16 iterations of this algorithm). Call this binary value R_xor.

(e.g. R_xor ¬ R_new Å K₁)

For 8 sets of 6 bits each of R_xor, convert each 6 bit set to 4 bits using a table similar to the following. Take the first and last bit from the 6 bits to get the row value (2 bits specifies a number in 0-3) and take the middle four bits to get the column value (4 bits specifies a range 0-15). The table value corresponding to this row and column is the decimal equivalent to the 4-bit binary output.

S₁

	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

Note: A different table is used for each of the eight 6-bit to 4-bit conversions, which when combined converts the 48-bit R_xor into a 32-bit value. We call these eight tables S₁,S₂,…,S₈

Using the following permutation table, rearrange the 32-bit output from S₁,S₂,…,S₈. Call this output P(L).

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

Take the bitwise exclusive-or of this 32-bit output with L. Move the original value of R to the variable L. Store the result of the exclusive-or in R.

(e.g.

TEMP ¬ L
L ¬ R
R ¬ TEMP Å P(L)

)

Goto d. unless we have reached this point 16 times.
Using the following permutation table, rearrange the bits of RL (32-bit R concatenated with 32-bit L). The output of this permutation is the 64-bit block of cyphertext.

IP^-1

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

To decrypt a 64-bit block of cyphertext, C₁C₂C₃…C₆₄.

Apply the exact same algorithm used for encryption, only in the reverse order. That is, do the 16 steps in reverse order, using the keys used at each step in reversed order, K₁₆, K₁₅, K₁₄, …, K₃, K₂, K₁.
The input would be C₁C₂C₃…C₆₄, which would first be subjected to the permutation table IP, then split into two 32-bit blocks. The right block would be permuted by E, then XORed with K₁₆. This would continue in exactly the same fashion as the encryption algorithm. The next key used would be K₁₅, then K₁₄, etc. At the end we would permute the 64-bit result with IP^-1, just like we did for encryption.

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

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

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

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

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

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

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

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

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