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 8^{th},
16^{th}, 24^{th}, ….. , 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 m_{0}
= IP (m). Now let m_{0} = L_{0}R_{0},
where L_{0} is the first 32 bits of m_{0}
and R_{0} is the last 32 bits.
2.
For 1 ≤ I ≤ 16, do the following:
L_{i}
= R_{i1
}
R_{i}
= L_{i1} Å
f (R_{i1}, K_{i}),
Where
K_{i} 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 R_{16}L_{16}, then apply the inverse
of the initial permutation to get the cipher test
c = IP^{1}(R_{16}L_{16}).
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 58^{th} bit of m
becomes the 1^{st} bit of m_{0}, the 50^{th}
bit of m becomes the 2^{nd} bit of m_{0},
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 C_{0}D_{0}, where C_{0}
and D_{0} have 28 bits.
2.
For 1 ≤ I ≤ 16, let C_{i} = LS_{i}(C_{i1})
and D_{i} = LS_{i}(D_{i1}). Here LS_{i}
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 56bit string C_{i}D_{i}
according to the following table. The output is K_{i}
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(R_{i1},K_{i}): The function f(R_{i1},K_{i}),
depicted in the Figure below, is described in several steps.
The
DES Function f(R_{i1},K_{i})

First,
R is expanded to E (R) by the following table. This
means that the first bit of E (R) is the 32^{nd} 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) Å
K_{i}, which has 48 bits, and write as B_{1}B_{2}…B_{8},
where each B_{j} has 6 bits.

There
are 8 Sboxes S_{1},…,S_{8}. Bj is the
input for S_{j}. Write B_{j} = b_{1}b_{2}…..b_{6}.
The row of the Sbox is specified by b_{1}b_{6}
while b_{2}b_{3}b_{4}b_{5}
determines the column.
Example.
If B_{4} = 001001, then look at the row 01 (2^{nd}
row) and column 0100 (5^{th} column).
Output
from this step will be 4 bits for every S box and we obtain eight 4bit
outputs C_{1}, C_{2}…C_{8}.

The
String C_{1}C_{2}…C_{8}
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 32bit string is f (R,
K_{i})
SBox
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

SBox
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

SBox
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

SBox
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

SBox
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

SBox
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

SBox
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

SBox
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

