How does DES work?
DES takes as input a secret message that will be encrypted:
And a 64bit Key, that will be used to both encrypt and decrypt:
Resulting in a Ciphertext:
First Step: Compute 16 subkeys, 48-bits long each
In general, a 64-bit key is used as input for DES, of which only 56-bits are used. 16 subkeys, with 48-bit each, will then be created from this 56-bits.
The first step is to permute the key using the PC-1 table above. This is, the first bit of our 56-bit permutation key will be the 57th bit of our original key, and so on.
PC-1
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
For example, our input key: Would become:
Next we divide the key in two parts, left C0 and right D0. C0: D0:
With C0 and D0 defined, we now create sixteen blocks. Each pair of blocks Cn and Dn is formed from the previous pair Cn-1 and Dn-1, respectively, for n between 1 and 16, using a left shift scheme as follows:
Iteration Number of
Number Left Shifts
1 1
2 1
3 2
4 2
5 2
6 2
7 2
8 2
9 1
10 2
11 2
12 2
13 2
14 2
15 2
16 1
To do a left shift we move each bit one place to the left, except for the first bit which goes to the end of the block.
In our example, we would have the following 16 keys: C0: D0: Would originate: C1: D1: C2: D2: C3: D3: C4: D4: C5: D5: C6: D6: C7: D7: C8: D8: C9: D9: C10: D10: C11: D11: C12: D12: C13: D13: C14: D14: C15: D15: C16: D16:
We will now form the final 16 keys by applying another permutation (PC-2 table) to each of the the 16 CnDn keys we obtained from the previous step.
PC-2
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
For example, our key C1D1: will become: K1 = The other keys are: K2 = K3 = K4 = K5 = K6 = K7 = K8 = K9 = K10 = K11 = K12 = K13 = K14 = K15 = K16 =
Now that we have our keys, it's time to encode our message.
Second Step: Encode each 64-bit block of the message
The first thing we need to do is to apply an initial permutation IP to each block of 64 bits, according to the table:
IP
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
For example, the first 64-bit block from our message Would become:
We now divide the permuted block in left and right: L0 = R0 =
We will now iterate through 16 cycles, each using one of the 16 48-bit keys we computed previously. We will use a function f which operates over a data block of 32 bits and a key Kn of 48 bits to produce a 32 bits block. For n from 1 to 16 we compute:
Ln = Rn-1
Rn = Ln-1 ⊕ f(Rn-1,Kn)
This is, in each iteration, we take the right 32 bits of the previous result and make them the left 32 bits of the current step. The right 32 bits in the current step are computed XORing the left 32 bits of the previous step with the result of the f function. This will result in a final block L16R16.
So, how does the function f works?
To calculate f, we first expand each block Rn-1 from 32 bits to 48 bits. This is done by using a selection table that repeats some of the bits in Rn-1. This selection table E has a 32 bit input block (Rn-1) and a 48 bit output block.
Let E be such that the 48 bits of its output, written as 8 blocks of 6 bits each, are obtained by selecting the bits in its inputs in order according to the following table:
E BIT-SELECTION TABLE
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
In our example we can get E(R0) from R0 as follows:
R0 =
E(R0) =
The next step in f calculation is to XOR the output E(Rn-1) with the key Kn:
Kn ⊕ E(Rn-1)
In our example we have:
K1 = E(R0) = K1⊕E(R0) =
We have not yet finished calculating the function f . To this point we have expanded Rn-1 from 32 bits to 48 bits, using the selection table, and XORed the result with the key Kn. We now have 48 bits, that will be used as addresses for the "S boxes". An S box takes as input 6 bits and gives 4 bits output that will replace the 6 bits input. We have 8 groups of 6 bits Bi, which will then be transformed in 8 groups of 4 bits, for a total of 32 bits.
Kn⊕E(Rn-1) = B1B2B3B4B5B6B7B8,
where each Bi is a group of six bits. We now compute:
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8)
The S1 box works as follows:
S1
Column Number
Row
No. 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 first and last bits of B represent in base 2 a number in the decimal range 0 to 3 (binary 00 to 11). Let that number be i. The 4 bits in the middle of B represent in base 2 a number in the decimal range 0 to 15 (binary 0000 to 1111). Let that number be j. Look up in the table the number in the i-th row and j-th column. It is a number in the range 0 to 15 and is uniquely represented by a 4 bit block. That block is the output S1(B) of S1 for the input B. For example, for input block B = 011011 the first bit is "0" and the last bit "1" giving 01 as the row. This is row 1. The middle four bits are "1101". This is the binary equivalent of decimal 13, so the column is column number 13. In row 1, column 13 appears 5. This determines the output; 5 is binary 0101, so that the output is 0101. Hence S1(011011) = 0101.
The tables defining the functions S1,...,S8 are the following:
S1
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
S2
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
S3
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
S4
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
S5
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
S6
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
S7
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
S8
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
In our example we obtain as the output of the eight S boxes:
K1⊕E(R0) =
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) =
The final stage in the calculation of f is to do a permutation P of the S-box output to obtain the final value of f:
P
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
From our example we get that:
S1(B1)S2(B2)S3(B3)S4(B4)S5(B5)S6(B6)S7(B7)S8(B8) =
f =
R1 = L0⊕f(R0,K1)
=
⊕
=
In the next round, we will have L2 = R1, which is the block we just calculated, and then we must calculate R2 =L1 ⊕ f(R1, K2), and so on for 16 rounds. At the end of the sixteenth round we have the blocks L16 and R16. We then reverse the order of the two blocks into the 64-bit block
R16L16
and apply a final permutation IP-1 as defined by the following table:
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
That is, the output of the algorithm has bit 40 of the preoutput block as its first bit, bit 8 as its second bit, and so on, until bit 25 of the preoutput block is the last bit of the output.
Example: If we process all 16 blocks using the method defined previously, we get, on the 16th round,
L16 =
R16 =
We reverse the order of these two blocks and apply the final permutation to
R16L16 =
IP-1 =
And that's it. If we apply the same steps to every 64-bit chunk of our message we obtain the final cipher:
Decryption is simply the inverse of encryption, follwing the same steps as above, but reversing the order in which the subkeys are applied.