|
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 1s. 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)
-
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
|
-
Compute
E (R) Å
Ki, which has 48 bits, and write as B1B2
B8,
where each Bj has 6 bits.
-
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, C2
C8.
-
The
String C1C2
C8
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
|
|