Substitution Box or S-Box = 48 Bits
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
http://www.eventid.net/docs/desexample.htm#Example
A practical example of the DES algorithm encryption
By Adrian Grigorof - adrian@grigorof.com
December 2000
The sample 64-bit key:
ddd,bbbbbbbb
222,11011110
16,00010000
156,10011100
88,01011000
232,11101000
164,10100100
166,10100110
48,00110000
The 64-bit key is (hex): DE,10,9C,58,E8,A4,A6,30
The original 64-bit key with parity bits
1 1 0 1 1 1 1 0 bits 1-8
0 0 0 1 0 0 0 0 bits 9-16
1 0 0 1 1 1 0 0 bits 17-24
0 1 0 1 1 0 0 0 bits 25-32
1 1 1 0 1 0 0 0 bits 33-40
1 0 1 0 0 1 0 0 bits 41-48
1 0 1 0 0 1 1 0 bits 49-56
0 0 1 1 0 0 0 0 bits 57-64
The original bit positions:
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
The 56-bit key (parity bits stripped)
1 1 0 1 1 1 1
0 0 0 1 0 0 0
1 0 0 1 1 1 0
0 1 0 1 1 0 0
1 1 1 0 1 0 0
1 0 1 0 0 1 0
1 0 1 0 0 1 1
0 0 1 1 0 0 0
The original positions of the bits after the parity is stripped:
1 2 3 4 5 6 7
9 10 11 12 13 14 15
17 18 19 20 21 22 23
25 26 27 28 29 30 31
33 34 35 36 37 38 39
41 42 43 44 45 46 47
49 50 51 52 53 54 55
57 58 59 60 61 62 63
The positions of the remained 56 bits after Permuted Choice 1 (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
The permuted 56-bit key:
0 1 1 1 0 1 0
1 0 0 0 1 1 0
0 1 1 0 0 0 1
0 0 0 1 0 0 0
0 1 0 0 0 0 0
1 0 1 1 0 0 1
0 1 0 0 0 1 1
1 0 1 1 1 1 1
Split the permuted key into two halves. The first 28 bits are called C[0] and the last 28 bits are called D[0].
C[0]
0 1 1 1 0 1 0
1 0 0 0 1 1 0
0 1 1 0 0 0 1
0 0 0 1 0 0 0
D[0]
0 1 0 0 0 0 0
1 0 1 1 0 0 1
0 1 0 0 0 1 1
1 0 1 1 1 1 1
Calculate the 16 sub keys. Start with i = 1
Perform one or two circular left shifts on both C[i-1] and D[i-1] to get C[i] and D[i],
respectively. The number of shifts per iteration are given in the table below.
Iteration # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
Left Shifts 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1
C[0]
0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0
D[0]
0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1
C[1]
1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0
D[1]
1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0
C[2]
1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1
D[2]
0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1
C[3]
0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1
D[3]
0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0
C[4]
0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1
D[4]
0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0
C[5]
0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1
D[5]
0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1
C[6]
0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0
D[6]
1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1
C[7]
1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1
D[7]
0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0
C[8]
0 1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0
D[8]
0 1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1
C[9]
1 1 0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0
D[9]
1 0 0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0
C[10]
0 0 0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1
D[10]
0 0 1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0
C[11]
0 1 0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0
D[11]
1 1 1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0
C[12]
0 0 0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1
D[12]
1 0 1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1
C[13]
0 1 0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0
D[13]
1 1 1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0
C[14]
0 0 0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1
D[14]
1 1 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1
C[15]
0 0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0
D[15]
1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1
C[16]
0 1 1 1 0 1 0 1 0 0 0 1 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0
D[16]
0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 1 1
Permute the concatenation C[i]D[i] as indicated below. This will yield K[i], which is 48 bits long.
Permuted Choice 2 (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
C[0]D[0]
0 1 1 1 0 1 0 bits 1-7
1 0 0 0 1 1 0 bits 8-14
0 1 1 0 0 0 1 bits 15-21
0 0 0 1 0 0 0 bits 22-28
0 1 0 0 0 0 0 bits 29-35
1 0 1 1 0 0 1 bits 36-42
0 1 0 0 0 1 1 bits 43-49
1 0 1 1 1 1 1 bits 50-56
K[0]
0 1 0 0 0 0
1 0 0 1 1 0
0 0 1 1 0 1
1 0 0 0 1 1
0 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 0 1
0 1 1 1 0 0
Loop back until K[16] has been calculated (for this example, the calculation of the rest of the K[x] is skipped)
Process a 64-bit data block.
Get a 64-bit data block. If the block is shorter than 64 bits, it should be padded as appropriate for the application.
Sample 64 bit data:
86,01010110
233,11101001
158,10011110
172,10101100
222,11011110
95,01011111
244,11110100
177,10110001
The original bit positions:
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
Perform the following permutation on the data block.
Initial Permutation (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
Original data:
0 1 0 1 0 1 1 0 bits 1-8
1 1 1 0 1 0 0 1 bits 9-16
1 0 0 1 1 1 1 0 bits 17-24
1 0 1 0 1 1 0 0 bits 25-32
1 1 0 1 1 1 1 0 bits 33-40
0 1 0 1 1 1 1 1 bits 41-48
1 1 1 1 0 1 0 0 bits 49-56
1 0 1 1 0 0 0 1 bits 57-64
Permuted data:
0 1 1 1 0 0 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1
1 0 1 0 0 0 1 0
1 1 0 1 1 1 1 0
1 1 0 0 1 0 1 0
0 0 1 1 1 1 1 0
0 0 1 1 0 1 0 1
Split the block into two halves. The first 32 bits are called L[0], and the last 32 bits are called R[0].
L[0]
0 1 1 1 0 0 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1
1 0 1 0 0 0 1 0
R[0]
1 1 0 1 1 1 1 0
1 1 0 0 1 0 1 0
0 0 1 1 1 1 1 0
0 0 1 1 0 1 0 1
Apply the 16 sub keys to the data block. Start with i = 1. Expand the 32-bit R[i-1] into 48 bits according to the bit-selection function below.
Expansion (E)
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
R[0]
1 1 0 1 1 1 1 0 bites 1-8
1 1 0 0 1 0 1 0 bites 9-16
0 0 1 1 1 1 1 0 bites 17-24
0 0 1 1 0 1 0 1 bites 25-32
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
Expanded R[0] or E(R[0])
1 1 0 1 1 1
1 1 1 1 0 1
0 1 1 0 0 1
0 1 0 1 0 0
0 0 0 1 1 1
1 1 1 1 0 0
0 0 0 1 1 0
1 0 1 0 1 1
Exclusive-or E(R[i-1]) with K[i].
E(R[0])
1 1 0 1 1 1
1 1 1 1 0 1
0 1 1 0 0 1
0 1 0 1 0 0
0 0 0 1 1 1
1 1 1 1 0 0
0 0 0 1 1 0
1 0 1 0 1 1
K[0]
0 1 0 0 0 0 1 1 0 1 1 1
1 0 0 1 1 0 1 1 1 1 0 1
0 0 1 1 0 1 0 1 1 0 0 1
1 0 0 0 1 1 0 1 0 1 0 0
0 1 0 0 0 1 0 0 0 1 1 1
1 0 0 0 0 1 1 1 1 1 0 0
1 1 1 1 0 1 0 0 0 1 1 0
0 1 1 1 0 0 1 0 1 0 1 1
XOR: If one, and only one, of the expressions evaluates to True, result is True
Perform Exclusive-or E(R[i-1]) with K[i].
E(R[i-1]) xor K[i]
1 0 0 1 1 1
0 1 1 0 1 1
0 1 1 1 0 0
1 1 1 0 0 1
0 1 1 1 1 0
0 1 1 1 0 1
1 1 1 0 1 1
1 1 0 1 1 1
Break E(R[i-1]) xor K[i] into eight 6-bit blocks.
Bits 1-6 are B[1], bits 7-12 are B[2], and so on with bits 43-48 being B[8].
B[1]
1 0 0 1 1 1
B[2]
0 1 1 0 1 1
B[3]
0 1 1 1 0 0
B[4]
1 1 1 0 0 1
B[5]
0 1 1 1 1 0
B[6]
0 1 1 1 0 1
B[7]
1 1 1 0 1 1
B[8]
1 1 0 1 1 1
Substitute the values found in the S-boxes for all B[j]. Start with j = 1.
All values in the S-boxes should be considered 4 bits wide.
Take the 1st and 6th bits of B[j] together as a 2-bit value (call it m)
indicating the row in S[j] to look in for the substitution.
Take the 2nd through 5th bits of B[j] together as a 4-bit value (call it n)
indicating the column in S[j] to find the substitution.
B[1]
1 0 0 1 1 1
1 2 3 4 5 6 bit order
m = 11 = 3
n = 0011 = 3
Replace B[j] with S[j][m][n].
Substitution Box 1 (S[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[1][3][3] = 2
B[2]
0 1 1 0 1 1
m = 01 = 1
n = 1101 = 13
S[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[2][1][13] = 9
B[3]
0 1 1 1 0 0
m = 00 = 0
n = 1110 = 14
S[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[3][0][14] = 2
B[4]
1 1 1 0 0 1
m = 11 = 3
n = 1100 = 12
S[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[4][3][12]=12
B[5]
0 1 1 1 1 0
m = 00 = 0
n = 1111 = 15
S[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[5][0][15] = 9
B[6]
0 1 1 1 0 1
m = 01 = 1
n = 1110 = 14
S[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[6][1][14]=3
B[7]
1 1 1 0 1 1
m = 11 = 3
n = 1101 = 13
S[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[7][3][13] = 2
B[8]
1 1 0 1 1 1
m = 11 = 3
n = 1011 = 11
S[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
S[8][3][11] = 0
Permute the concatenation of B[1] through B[8] as indicated below.
B[1] = S[1][3][3] = 2 = 0010
B[2] = S[2][1][13] = 9 = 1001
B[3] = S[3][0][14] = 2 = 0010
B[4] = S[4][3][12] = 12 = 1100
B[5] = S[5][0][15] = 9 = 1001
B[6] = S[6][1][14] = 3 = 0011
B[7] = S[7][3][13] = 2 = 0010
B[8] = S[8][3][11] = 0 = 0000
B[1-8]
0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Permutation 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
P(S[1](B[1])...S[8](B[8]))
0 0 1 0
0 0 0 1
0 0 1 0
1 0 0 0
0 1 1 1
0 1 1 0
0 1 0 0
0 1 0 0
Exclusive-or the resulting value with L[i-1].
Thus, all together, your R[i] = L[i-1] xor P(S[1](B[1])...S[8](B[8])),
where B[j] is a 6-bit block of E(R[i-1]) xor K[i].
(The function for R[i] is more concisely written as, R[i] = L[i-1] xor f(R[i-1], K[i]).)
L[0] xor P(S[1](B[1])...S[8](B[8]))
L[0] (see above)
0 1 1 1 0 0 1 1
1 1 1 1 0 1 0 1
0 1 1 1 1 1 0 1
1 0 1 0 0 0 1 0
L[0]
0 1 1 1
0 0 1 1
1 1 1 1
0 1 0 1
0 1 1 1
1 1 0 1
1 0 1 0
0 0 1 0
xor with
P(S[1](B[1])...S[8](B[8]))
0 0 1 0
0 0 0 1
0 0 1 0
1 0 0 0
0 1 1 1
0 1 1 0
0 1 0 0
0 1 0 0
R[1]
0 1 0 1
0 0 1 0
1 1 0 1
1 1 0 1
0 0 0 0
1 0 1 1
1 1 1 0
0 1 0 0
