Data Encryption Standard

DES Algorithm

The original paper is published in Federal Information Processing Standard (FIPS) Publication 46 (January 15, 1977) and available at NIST web site. An explanation of the algorithm can also be found at various sources such as [4], which is used  to understand the algorithm and present it below

Block Size: In DES, encryption/decryption is done on blocks of 64 bits. The plaintext/ciphertext is divided into blocks of 64 bits and the algorithm is applied to each block.

Key: The key has 56 bits, but is expressed as a string of 64 bits. The 8th, 16th, 24th, ….. , bits are parity bits, arranged so that each block of 8 bits has an odd number of 1’s. This is for error detection in the key.

Algorithm:  Starts with a plaintext m of 64 bits and consists if 3 stages.

1.       The bits of m are permuted by a fixed initial permutation to obtain m0 = IP (m). Now let m0 = L0R0, where L0 is the first 32 bits of m0 and R0 is the last 32 bits.

2.      For 1 ≤ I ≤ 16, do the following:

Li = Ri-1

Ri = Li-1 Å f (Ri-1, Ki),

Where Ki is a string of 48 bits obtained from the key K and f is a function described later.

3.      Switch left and right halves to obtain R16L16, then apply the inverse of the initial permutation to get the cipher test

c = IP-1(R16L16).

The DES Algorithm

Initial Permutation (IP): -The initial permutation, which seems to have no cryptographic significance, but which perhaps designed to make the algorithm load more efficiently into the chips that were available in 1970s, can be described by the Initial Permutation Table. This means that the 58th bit of m becomes the 1st bit of m0, the 50th bit of m becomes the 2nd bit of m0, etc.

Initial Permutation Table

 58 50 42 34 26 18 19 2 60 52 44 36 26 28 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

Key Permutation:

1. The parity bits are discarded and the remaining bits are permuted by the following table.

Key Permutation Table

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

Write the results as C0D0, where C0 and D0 have 28 bits.

2. For 1 ≤ I ≤ 16, let Ci = LSi(Ci-1) and Di = LSi(Di-1). Here LSi means shift the input one or two places to the left, according to the following table.

Number of Key Bits Shifted per Round

 ROUND 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 SHIFT 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1

3. 48 bits are chosen from the 56-bit string CiDi according to the following table. The output is Ki

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

Function f(Ri-1,Ki):  The function f(Ri-1,Ki), depicted in the Figure below, is described in several steps.

The DES Function  f(Ri-1,Ki)

1. First, R is expanded to E (R) by the following table. This means that the first bit of E (R) is the 32nd bit of R, etc. Note E (R) has 48 bits.

Expansion Permutation

 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 31 1
2. Compute E (R) Å Ki, which has 48 bits, and write as B1B2B8, where each Bj has 6 bits.

3. There are 8 S-boxes S1,…,S8. Bj is the input for Sj. Write Bj = b1b2…..b6. The row of the S-box is specified by b1b6 while b2b3b4b5 determines the column.

Example. If B4 = 001001, then look at the row 01 (2nd row) and column 0100 (5th column).

Output from this step will be 4 bits for every S box and we obtain eight 4-bit outputs C1, C2C8.

1. The String C1C2C8 is permuted according the following table.

 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

The resulting 32-bit string is f (R, Ki)

 S-Box 1 14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0 15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13

 S-Box 2 15 1 8 14 6 11 3 4 9 7 2 13 12 0 5 10 3 13 4 7 15 2 8 14 12 0 1 10 6 9 11 5 0 14 7 11 10 4 13 1 5 8 12 6 9 3 2 15 13 8 10 1 3 15 4 2 11 6 7 12 0 5 14 9

 S-Box 3 10 0 9 14 6 3 15 5 1 13 12 7 11 4 2 8 13 7 0 9 3 4 6 10 2 8 5 14 12 11 15 1 13 6 4 9 8 15 3 0 11 1 2 12 5 10 14 7 1 10 13 0 6 9 8 7 4 15 14 3 11 5 2 12

 S-Box 4 7 13 14 3 0 6 9 10 1 2 8 5 11 12 4 15 13 8 11 5 6 15 0 3 4 7 2 12 1 10 14 9 10 6 9 0 12 11 7 13 15 1 3 14 5 2 8 4 3 15 0 6 10 1 13 8 9 4 5 11 12 7 2 14

 S-Box 5 2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 9 14 11 2 12 4 7 13 1 5 0 15 10 3 9 8 6 4 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14 11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3

 S-Box 6 12 1 10 15 9 2 6 8 0 13 3 4 14 7 5 11 10 15 4 2 7 12 9 5 6 1 13 14 0 11 3 8 9 14 15 5 2 8 12 3 7 0 4 10 1 13 11 6 4 3 2 12 9 5 15 10 11 14 1 7 6 0 8 13

 S-Box 7 4 11 2 14 15 0 8 13 3 12 9 7 5 10 6 1 13 0 11 7 4 9 1 10 14 3 5 12 2 15 8 6 1 4 11 13 12 3 7 14 10 15 6 8 0 5 9 2 6 11 13 8 1 4 10 7 9 5 0 15 14 2 3 12

 S-Box 8 13 2 8 4 6 15 11 1 10 9 3 14 5 0 12 7 1 15 13 8 10 3 7 4 12 5 6 11 0 14 9 2 7 11 4 1 9 12 14 2 0 6 10 13 15 3 5 8 2 1 14 7 4 10 8 13 15 12 9 0 3 5 6 11