5 DATA ENCRYPTION STANDARD
EZAZUL ISLAM AND SAIFUL AZAD
Contents
5.1.1 Operations for Encryption/Decryption
5.1.2 Operations for Subkey Generation
5.5.3 Introducing the Member Variables of DES Class
5.5.4 Introducing the Member Functions of DES Class
5.5.6 The PermChoice1() Function
5.5.7 The Split_Key() Function
5.5.8 The PermChoice2() Function
5.5.9 The Encrypt(char *) Function
5.5.11 The Expansion() Function
5.5.12 The xor_oneE(int round) Function
5.5.13 The Substitution() Function
5.5.14 The Permutation() Function
5.5.16 The Decrypt(char *) Function
Keywords
Block cipher
Data Encryption Algorithm
Data Encryption Standard
The Data Encryption Standard (DES) was developed in the early 1970s at IBM, and later, in 1977, the algorithm was submitted to the National Bureau of Standards (NBS) to be approved as Federal Information Processing Standard 46 (FIPS 46). With the consultation of the National Security Agency (NSA), the NBS accepted a slightly changed version of DES as FIPS 46 in the same year to provide security for the unclassified electronic data of the U. S. government. The data are encrypted using DES in 64-bit blocks, which are encrypted using a 56-bit symmetric key to provide confidentiality and privacy.
Some experts refer to DES as an encryption standard and Data Encryption Algorithm (DEA) as the basic algorithm. In recent times, DEA and DES are used interchangeably. On the other hand, there is another extension of DEA that is named Triple DEA (TDEA). The Triple DEA and DEA are typically referred to as Triple DES and DES, respectively. For our readers’ convenience, we use DES and 3DES in this chapter to refer to these algorithms.
Like most of the symmetric block algorithms, DES is also based on a structure referred to as a Feistel cipher, which was alreadyintroduced to the reader in Chapter 4. The DES is comprised of16 rounds, where a separate key is utilized in each round. All 16 keys are generated from a 56-bit key. Before introducing DES to the reader in detail, it is necessary to know the primitive operations that DES utilizes. Consequently, in the following section, we discuss various primitive operations related to DES with relevant examples.
5.1 Primitive Operations
All the primitive operations utilized in DES can be separated into two groups: (1) operations for encryption/decryption and (2) operations for key generation. All these operations are discussed below.
5.1.1 Operations for Encryption/Decryption
DES encryption/decryption is based on the following primitive operations:
Exclusive disjunction/exclusive or (XOR). Exclusive disjunction or exclusive or is a logical operation that outputs true whenever both inputs differ from each other (e.g., one is true and the other is false) (Table 5.1). It is symbolized by the prefix operator J and by the infix operators XOR, EOR, EXOR, ⊻, ⊕, ↮, and ≢.
Initial permutation (IP). In initial permutation, the 64 bits of the data are rearranged to another 64 bits of data according to a given table (Table 5.2 in this example). Each entry in the table shows the new arrangement of a bit from its initial position. For instance, the 58th bit of data becomes the first bit of the output data after the permutation, and the 1st bit of data becomes the 40th bit of the output data after permutation. An example is given below to demonstrate the rearrangements of the bits after permutation.
INPUT
OUTPUT
0
0
0
0
1
1
1
0
1
1
1
1
Table 5.2 Table Utilized for Initial Permutation (IP)
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
Example
Actual bit sequence:
11001000001111111010100100100110101011101101101110100
11111100100After initial permutation:
10100001001000101101101001100110111101011101111000110
11101111010Inverse permutation (IP–1). Like initial permutation, a block of code again needs to be rearranged (according to Table 5.3). This is known as inverse permutation (IP–1). Using IP–1, the original ordering of the bits is rearranged.
Example
Actual bit sequence:
10100001001000101101101001100110111101011101111000110
11101111010After inverse permutation:
11001000001111111010100100100110101011101101101110100
11111100100From this example, we can observe that if no other operation is performed, we can get the actual bit sequence returns if we do inverse permutation immediately after initial permutation.
Table 5.3 Table Utilized for Inverse Permutation (IP–1)
INVERSE PERMUTATION (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
Expansion permutation. In every round of DES, a 64-bit block is divided into two halves of 32 bits each, namely, left and right blocks. Again, since each round utilizes a key of 48 bits, it is necessary to enlarge a block to be equivalent to the round key size. Generally, a right-side block has expanded to a 48-bit block, which is then XORed with the selected round key. A 32-bit block is expanded utilizing Table 5.4.
Example
Bits sequence in right block:
11001000001111111010100100100110
After expansion permutation:
011001010000000111111111110101010010100100001101
Substitution. The expanded 48-bit block is required to shrink into a 32-bit block again. For this purpose, a 48-bit block is broken into a 6-bit chunk that is then fed into a substitution box (also known as S-box), which produces a 4-bit output for each 6-bit output. There are eight S-boxes utilized in the substitution procedure, which are given in Table 5.5. Since there are 64 possible input values (6 bits) and only 16 possible output values (4 bits), the S-box could map several input values to a single output value. The leftmost 6-bit chunk is substituted by S1-box, the next 6-bit chunk is substituted by S2-box, and so on. Consequently, the rightmost chunk is substituted by S8-box. Again, among the 6 bits, the first and last bit form a 2-bit binary number that indicates the row number, and the middle four bits select one among the 16 columns. For instance, in S5, a 6-bit chunk 011101 is substituted with a 4-bit chunk 1000. Here, the first bit and last bit form 01, which means row number 1 is selected. Then, the middle four bits 1110 indicate the column number, i.e., 14. If we look at row 2 and column 14, the value is 8, whose binary equivalent is 1000.
Table 5.4 Table Utilized in Expansion Permutation
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
32
1
Table 5.5 All the S-Boxes Are Defined
PERMUTATION
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
Permutation. The 32-bit block generated after substitution is rearranged using a permutation operation where a 32-bit output comes from a 32-bit input by permuting the bits of the input block. The table that is utilized in this operation is shown in Table 5.6.
Example
Before permutation:
11001000001111111010100100100110
After permutation:
10010101110010101011010011100100
5.1.2 Operations for Subkey Generation
DES subkey generation is based on the following primitive operations:
Permuted choice 1 (PC-1). DES takes a 64-bit symmetric key from the user, which is then permuted according to Table 5.7. It could be observed from the table that the first entry is 57; this means that the 57th bit of the original key K becomes the first bit of the permuted key KP. Again, the 49th bit of the original key becomes the second bit of the permuted key.
Table 5.7 Table for Permuted Choice 1
PERMUTED CHOICE 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
Example
Before permutation:
K = 11001000001111111010100100100110101011101101101110
10011111100100After permutated choice 1:
KP = 1111010110100001110111100010011110101101101000110
1110010Left shifting. A permuted key is then separated into two blocks, left and right, where each of them is 28 bits long. After that, each block is shifted to the left to a fixed number of bits, which again depends on the round. For a different round, the bits to be left shifted are different, which are shown in Table 5.8. For instance, in the eighth round, 2-bit left shifting takes place, whereas, in the ninth round, it is only 1 bit. When a block is shifted to the left, each bit moves one place to the left, except for the first bit, which is cycled to the end of the block.
Example
Let us assume that the shifting operation is for generating a key of round 8. First, we can find out how many bits are to be shifted from Table 5.8, which is 2 bits in this example.
Before left shifting:
1111010110100001110111100010
After left shifting:
1101011010000111011110001011
Table 5.8 Schedule of Left Shifting
ROUND NUMBER
BITS ROTATED
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
Table 5.9 Table for Permuted Choice 2
PERMUTED CHOICE 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
Permuted choice 2 (PC-2). After the left shifting operation, both separated blocks are combined together, which form a block of 56 bits. Then, they are rearranged and shrunk to produce a round key of 48 bits. This permuted choice 2 is performed utilizing Table 5.9.
Example
Before permuted choice 2:
11001000001111111010100100100110101011101101101110100111
After permutated choice 2:
111111001010011000101011101111101111111100010000
5.2 Basic Structure
A basic structure of DES is portrayed in Figure 5.1. DES supports a 64-bit block that is subjected to go through an initial permutation. This permuted block is then passed through 16 rounds, where every round is comprised of various operations, depicted in Figure 5.2. The operations of 48-bit key generations for every round from a 64-bit key are also portrayed in both figures. After visiting the last round, a 32-bit swapping is performed on the 64-bit block. Finally, the ciphertext is generated after the inverse permutation operation.
Figure 5.1 A basic DES structure is depicted.
5.3 DES Encryption Algorithm
Following is the pseudocode for DES encryption in which the function named Encrypt takes the plaintext message as a parameter and performs the essential operations to produce the ciphertext.
Algorithm 5.1: Encrypt (M)
Begin
C ← IP(M)
for round ← 1 to 16
KEYi ← SubKey (K, round)
L(i-1) ← LEFT (C)
R(i-1) ← RIGHT (C)
Li ← R(i-1)
Ri ← L(i-1) xor (Permutation (Substitution
(KEYi xor Expansion(R(i-1)))))
end for
C ← swap(C)
C ← IP-1(C)
return C
End
5.4 DES Decryption Algorithm
For decryption, the steps are the same as for encryption, but the difference is in the order of using the keys for each of the rounds.
Algorithm 5.2: Decrypt (C)
Begin
M ← IP(C)
for round ← 16 to 1
KEYi ← SubKey (K, round)
Li ← LEFT (M)
Ri ← RIGHT (M)
R(i-1) ← Li
L(i-1) ← Ri xor (Permutation (Substitution
(KEYi xor Expansion(R(i-1)))))
end for
M← swap(M)
M← IP-1(M)
return M
End
5.5 Implementation
DES implementation using C++ is described below.
5.5.1 C++ Library Headers
The following built-in headers are utilized in the program:
cstring: Used for the purpose of string manipulation, string length measurement, and moving the contents of the message to work with and the ciphertext. When working with message encryption and decryption, there is a need for string handling. During the process of encryption and decryption, the functionalities are like string length calculation, string copy from one place to another, and the input-output of a string message or ciphertext.
iostream: The basic header file of the C++ library. It is the header that consists of the core library of C++. The core library is mostly focused on the input-output stream-related functions. I and O refer to input and output, respectively. On the other hand, stream refers to the flow of bits in the input and output buffers of the computer system.
cstdlib: Defines multiple general purpose functions, such as the functions related to random number generation, communication with the system, and arithmetic operations.
5.5.2 The DES Class
class DES{
public:
int keyi[16][48],
total[64],
left[32],
right[32],
ck[28],
dk[28],
expansion[48],
z[48],
xor1[48],
sub[32],
p[32],
xor2[32],
temp[64],
pc1[56],
ip[64],
inv[8][8];
char final[1000];
void keygen();
void PermChoice1();
void split_key();
//left circular shifts take place
void PermChoice2();
//16 keys of 56 bits keys are created
void IP();
//L0 and R0 are created using IP : 64 bit total
//32 bit R(n-1) is expanded into 48 bit
void Expansion();
//Expansion applied on the right half, R(n-1)
//32 bit R(n-1) becomes 48 bit R(n-1) now
void xor_oneE(int);
//xor the 48 bit key(n) with 48 bit R(n-1)
void substitution();
//48 bit resultant becomes 32 bit now using 16 S
boxes
void permutation();
//permutation operation takes place on 32 bit
message bit
void xor_two();
//now the resultant of 32 bit is xored with
L(n-1)
//xored resultant becomes R(n)
void inverse();
//inver permutation of R(n)L(n)
void xor_oneD(int);
//xor of 48 bit key and expanded message for
decryption
char *Encrypt(char *);
char *Decrypt(char *);
};
All the member variables and functions of the DES class are publicly accessible. For this reason, the members are declared in the public scope. No private or public differentiation is needed due to our basic target of this presentation being to provide a technical knowledge of how DES works, but not to provide the concept of object orientation.
5.5.3 Introducing the Member Variables of DES Class
Here, in the above class declaration, int keyi[16][48] is a two-dimensional array that holds all 16 keys that are made after applying permutation choice 2. Permutation choice 2 is applied with the help of the C++ function void PermChoice2(), defined in class DES.
5.5.4 Introducing the Member Functions of DES Class
The member function IP() is responsible for the initial permutation operation on the message text that is to be encrypted.
5.5.5 The Keygen() Function
1. void DES::keygen(){
2. PermChoice1();
3. split_key();
4. int noshift = 0,round;
5. for(round = 1; round< = 16; round++){
6. if(round = =1||round = =2||round =
=9||round = =16)
7. noshift = 1;
8. else
9. noshift = 2;
10.
11. while(noshift>0){
12. int t;
13. t = ck[0];
14. for(int i = 0; i<28; i++)
15. ck[i] = ck[i+1];
16. ck[27] = t;
17. t = dk[0];
18. for(int i = 0; i<28; i++)
19. dk[i] = dk[i+1];
20. dk[27] = t;
21. noshift— ;
22. }
23. cout << endl << "round " << round
<< endl;
24. PermChoice2();
25. for(int i = 0; i<48; i++) //stores
each of the subkeys
26. keyi[round-1][i] = z[i];
27. }
28. }
A key is utilized to create the 16 different subkeys. To make those subkeys, various operations have to be conducted so that the subkeys show proper variations that will help make those keys as strong as possible. Basic functionalities of the function keygen() are selecting a secret key, operating permutation choice 1 on that key, splitting that single key into two parts, conducting a left circular shift to produce 16 subkeys, and finally, generating 16 secret keys by applying permutation choice 2 on them.
PermChoice1() converts the actual 64-bit secret key into a 56- bitsecret key. The details of the PermChoice1() function are described in the next section of this chapter. Another function, named split_key(), splits the 56-bit permuted key into two parts so that each of the parts becomes 28 bits in length. In the fourth line of the above code, the variables to track the number of shift and round are declared. There are 16 rounds of processing steps, as the subkeys are 16 in number.
The sixth line shows the number of left circular shifts, which varies according to the round. All the rounds do not have the same number of left circular shifts. From lines 11 to 22 left circular shift operations take place. The shifting operations are applied on the arrays named ck and dk, as the split subkeys are stored in these arrays. Line 23 outputs the current round number. The scope of the for loop is from lines 5 to 27;the code inside this scope is repeated for each of the 16 rounds. Shifted bits are stored into ck and dk arrays in lines 15 and 19 respectively. Then in the 24th line, permutation choice 2 comes into action, actually permuting each of the 56-bit subkeys to convert all of them into 48-bit subkeys. After the execution of the PermChoice2() function, the array named z[] holds the permuted bits of the 48-bit subkey, and in line 26 the 48-bit subkey is stored in the keyi[][] array. Thus, each of the 16subkeys of 48 bits is created and stored into the keyi[][] array.
5.5.6 The PermChoice1() Function
1. void DES::PermChoice1(){//Permutation Choice-1
2. cout << "key: " << endl;
3. for (int i = 0; i < 64; i++) {
4. cout << key[i] << " ";
5. if (((i + 1)% 8) = = 0) cout << endl;
6. }
7. int k = 57,i;
8. for(i = 0; i<28; i++){
9. pc1[i] = key[k-1];
10. if(k-8>0) k = k-8;
11. else k = k+57;
12. }
13. k = 63;
14. for(i = 28; i<52; i++){
15. pc1[i] = key[k-1];
16. if(k-8>0) k = k-8;
17. else k = k+55;
18. }
19. k = 28;
20. for(i = 52; i<56; i++){
21. pc1[i] = key[k-1];
22. k = k-8;
23. }
24. cout << endl << "After permutation choice 1:"
<< endl;
25. for (i = 0; i < 56; i++){
26. cout << pc1[i] << " ";
27. if (((i + 1)% 7) = = 0) cout << endl;
28. }
29. }
In the above function definition, at first the PermChoice1() function was called to make the first permutation operation on the single secret key. After conducting the first permutation operations on the 64-bit secret key, the resultant key holds 56 bits. The rest of the bits are removed from the actual key. The final product of the above function is the 56-bit secret key. All of the cout keywords in the source code are to provide a proper output so that the user can get a proper idea of how the program is running and whether all the statements are giving the correct output or not.
For each of the blocks in a 64-bit key, the last bit of every octet is removed. There are eight blocks in a 64-bit key. If each of them loses 1 bit, the total number of bits becomes 56 bits. Thus, 56-bit key is produced and is stored in the array named pc1[].
5.5.7 The Split_Key() Function
1. void DES::split_key(){
2. int i,k = 0;
3. for(i = 0; i<28; i++){ //creates 56
bits key with Permutation by PC-1
4. ck[i] = pc1[i];
5. }
6. for(i = 28; i<56; i++){
7. dk[k] = pc1[i];
8. k++;
9. }
10. cout << endl << "Print C0 " << endl;
11. for(i = 0; i<28; i++){ //left 28
bits of permuted 56 bit key
12. cout << ck[i] << " ";
13. if (((i + 1)% 7) = = 0) cout
<< endl;
14. }
15. cout << endl << "Print D0 " << endl;
16. for(i = 28; i<56; i++){ //right 28
bits of permuted 56 bit key
17. cout << dk[i] << " ";
18. if (((i + 1)% 7) = = 0) cout
<< endl;
19. }
20. }
After executing the function split_key(), the 56-bit key stored in pc1[64] is divided into two parts. One is stored in ck[28] and another in dk[28]. Both of the arrays can hold 28 bits of values, so that lines 3 to 9 are executed to split the 56-bit key into two parts and store them in the ck[28] and dk[28] arrays. The rest of the lines, 10 to 19, are outputting the split key for test purposes, whether the split has taken place perfectly or not.
5.5.8 The PermChoice2() Function
1. void DES::PermChoice2(){
2. int per[56],i,k;
3. for(i = 0; i<28; i++) per[i] =
ck[i];
4. for(k = 0,i = 28; i<56; i++) per[i]
= dk[k++];
5. z[0] = per[13];
6. z[1] = per[16];
7. z[2] = per[10];
8. z[3] = per[23];
9. z[4] = per[0];
10. z[5] = per[4];
11. z[6] = per[2];
12. z[7] = per[27];
13. z[8] = per[14];
14. z[9] = per[5];
15. z[10] = per[20];
16. z[11] = per[9];
17. z[12] = per[22];
18. z[13] = per[18];
19. z[14] = per[11];
20. z[15] = per[3];
21. z[16] = per[25];
22. z[17] = per[7];
23. z[18] = per[15];
24. z[19] = per[6];
25. z[20] = per[26];
26. z[21] = per[19];
27. z[22] = per[12];
28. z[23] = per[1];
29. z[24] = per[40];
30. z[25] = per[51];
31. z[26] = per[30];
32. z[27] = per[36];
33. z[28] = per[46];
34. z[29] = per[54];
35. z[30] = per[29];
36. z[31] = per[39];
37. z[32] = per[50];
38. z[33] = per[46];
39. z[34] = per[32];
40. z[35] = per[47];
41. z[36] = per[43];
42. z[37] = per[48];
43. z[38] = per[38];
44. z[39] = per[55];
45. z[40] = per[33];
46. z[41] = per[52];
47. z[42] = per[45];
48. z[43] = per[41];
49. z[44] = per[49];
50. z[45] = per[35];
51. z[46] = per[28];
52. z[47] = per[31];
53. cout << endl << "After permutation
choice 2 " << endl;
54. for(int i = 0; i<48; i++){
//creates the 48 bits permutation
table(PC-2)
55. cout << z[i] << " ";
56. if (((i + 1)% 6) = = 0) cout
<< endl;
57. }//for ends here
58. } //PermChoice2 function ends here
The above function, PermChoice2(), is called separately for each of the 16 rounds. Hence, the function is called 16 times. The basic target of the function is to reduce the 56-bit key of the current round to a 48-bit key. After permuting the secret key into 48 bits, the result is stored in the array named z[48], which holds the 48-bit key. When the permuting operation is finished, the next step starts automatically to store the 48-bit permuted key into another array, declared keyi[16][48]. That holds all 16 keys, which are 48 bits in size individually.
5.5.9 The Encrypt(char *) Function
Here comes the part to do something with the plaintext that is the actual message to be encrypted. For this situation, the plaintext also has 64 bits; the whole message/plaintext is divided into blocks of 64 bits.
1. char* DES::Encrypt(char *Text1){
2. int i,a1,j,nB,m,iB,k,K,B[8],n,
t,d,round, mc = 0;
3. char *Text = new char[1000];
4. strcpy(Text,Text1);
5. i = strlen(Text);
6. a1 = i%8;
7.
8. if(a1 ! = 0)
9. for(j = 0; j<8-a1;
j++,i++) Text[i] = ' ';
//add padding bits with
space
10. Text[i] = ' ';
11. for(iB = 0,nB = 0,m = 0;
m<(strlen(Text)/8); m++){
12. //Repeat for TextLength/8
times.
13. for(iB = 0,i = 0; i<8;
i++,nB++){
14. n = (int)Text[nB];
15. cout << " n is " << n
<< endl;
16. for(K = 7; n> = 1; K— )
{
17. B[K] = n%2;
//Converting
8-Bytes to
64-bit Binary
Format
18. cout << "B[" <<
K << "] is " <<
B[K] << endl;
19. n/= 2;
20. }
21. for(; K> = 0; K— ) B[K]
= 0;
22. for(K = 0; K<8;
K++,iB++) total[iB] =
B[K];
23. //Now 'total' contains
the 64-Bit binary
format of Bytes
24. }
25. IP();
26. for(i = 0; i<64; i++)
total[i] = ip[i];
//Store values of ip[64] into
total[64]
27. for(i = 0; i<32; i++) left[i]
= total[i];
28. for(; i<64; i++) right[i-32]
= total[i];
29. for(round = 1; round< = 16;
round++){
30. Expansion(); //E bit
selection
31. //Performing expansion
on 'right[32]' to get
'expansion[48]'
32. xor_oneE(round);
33. //Performing XOR
operation on
expansion[48],z[48] to
get xor1[48]
34. substitution();
35. //Perform substitution
on xor1[48] to get
sub[32]
36. permutation();
37. //Performing
Permutation on sub[32]
to get p[32]
38. xor_two(); //xor with
32 bit L0 and f value
39. //Performing XOR
operation on
left[32],p[32] to get
xor2[32]
40. for(i = 0; i<32; i++)
left[i] = right[i];
41. //Dumping right[32]
into left[32]
42. for(i = 0; i<32; i++)
right[i] = xor2[i];
43. //Dumping xor2[32] into
right[32]
44. }
45. for(i = 0; i<32; i++) temp[i]
= right[i];//Dumping—
>[swap32bit]
46. for(; i<64; i++) temp[i] =
left[i-32];//
left[32],right[32] into
temp[64]
47. inverse();
48. //Inversing the bits of
temp[64] to get inv[8][8]
49. /* Obtaining the Cypher-Text
into final[1000]*/
50. k = 128;
51. d = 0;
52. for(i = 0; i<8; i++){
53. for(j = 0; j<8; j++){
54. d = d+inv[i]
[j]*k;
55. k = k/2;
56. }
57. final[mc++] = (char)d;
58. k = 128;
59. d = 0;
60. }
61. }//for loop ends here
62. final[mc] = ' ';
63. return(final);
64. }
Before executing the encryption process, the plaintext is padded with some space characters to make the plaintext string length divisible by 8; thus, the number of bits in the plaintext is always a multiple of 64. A character size is 1 byte, and 1 byte represents 8 bits. After padding the plaintext with an empty space character, the for loop in the 11th line rotates for each of the eight characters in the plaintext, because eight characters consist of 64 bits. In lines 13 to 23, each of the 8 bytes is converted into 64 bits and stored in the total[64] array. Thus, the for loop continues for each of the 64 bits in the plaintext bit stream.
The function Encrypt(char *) takes a parameter that will receive the plaintext message and continue its next steps. In lines 8 and 9, extra bits are added to make the size of the plaintext string a multiple of 8. In this way, it is ensured that each of the blocks has 8 bits. After the execution of lines 10 to 24, the array total[64] contains the 64-bit format of the plaintext message.
In line 25, the initial permutation operation is done over the 64-bit block of plaintext message. It actually reorganizes the bit stream into some predefined sequences. The operations of the function IP() will be discussed in the latter sections of this chapter. In lines 26, 27, and 28, three operations are done. In line 26, initial permuted bits are copied into total[64]. In line 27, half of the 64 bits of the total bit stream are copied into the left[32] array, and the second half of the same array is copied into right[32] array. Thus, the 64-bit plaintext message is divided into two parts and stored into two arrays, left[32] and right[32].
From lines 29 to 44, several rounds of the same operations have been conducted to continue the whole encryption process—16 rounds in the process. Now, before starting the for loop, assuming that the left[32] array holds the 32 bits of the plaintext message and the right[32] array contains the right bits of the plaintext message, the operations are briefly mentioned below.
Calling the function Expansion() actually expands the content of right[32] into 48 bits and stores the bit stream into the array named expansion[48]. So, next time, for the current round, it is possible to XOR with the content of expansion[48] with the content of keyi[round-1][i], where round denotes the current round and i is the index of the bit that ranges from the 1st to the 48th bit. Another function, defined as substitution(), converts the 48-bit content of the expansion[48] into 32 bits and stores the resulting bit stream in the sub[32] array. On the other hand, the function permutation() in line 36 makes the permutation of the 32-bit content in sub[32] and copies the result into the array that is declared p[32]. The xor_two() function works on left[32] content and p[32]; the result is copied into the xor2[32] array. Using the code of lines 40 and 42, the content of the right[32] array is dumped into the left[32] array, and the content of the xor2[32] array is dumped into the right[32] array.
In lines 45 and 46, two arrays, left[32] and right[32], swap their positions; the content of the left[32] array takes the rightmost side of the temp[64] array, and the content of right[32] takes the leftmost position of the temp[64] array. After that, in line 47, an inverse permutation operation is conducted over the bit stream of the temp[64] array.
5.5.10 The IP() Function
1. void DES::IP(){//Initial Permutation
2. int k = 58,i;
3. for(i = 0; i<32; i++){
4. ip[i] = total[k-1];
5. if(k-8>0) k = k-8;
6. else k = k+58;
7. }
8. k = 57;
9. for(i = 32; i<64; i++){
10. ip[i] = total[k-1];
11. if(k-8>0) k = k-8;
12. else k = k+58;
13. }
14. cout << "Actual bit sequence:"
<<endl;
15. for (int i = 0; i < 64; i++){
16. cout << total[i] << " ";
17. if (((i + 1)% 8) = = 0) cout
<<endl;
18. }
19. cout << endl;
20. cout << "After initial permutation:
" <<endl;
21. for (int i = 0; i < 64; i++){
22. cout << ip[i] << " ";
23. if (((i + 1)% 8) = = 0) cout
<<endl;
24. }
25. }
The initial permutation operation is conducted over the 64 bits contained in the total[64] array. Thus, the plaintext message is reorganized according to the initial permutation table, and finally, the result is stored in the ip[64] array. That holds the initial permuted bit stream.
5.5.11 The Expansion() Function
1. void DES::Expansion(){//Expansion Function
applied on 'right' half
2. int exp[8][6],i,j,k;
3. for(i = 0; i<8; i++){
4. for(j = 0; j<6; j++){
5. if((j! = 0)||(j! = 5)){
6. k = 4*i+j;
7. exp[i][j] =
right[k-1];
8. }
9. if(i ! = 0 && j = =0){
10. k = 4*i;
11. exp[i][j] =
right[k-1];
12. }
13. if(i ! = 7 && j = =5){
14. k = 4*i+j;
15. exp[i][j] =
right[k-1];
16. }
17. }
18. }
19. exp[0][0] = right[31];
20. exp[7][5] = right[0];
21. k = 0;
22. for(i = 0; i<8; i++){
23. for(j = 0; j<6; j++)
expansion[k++] = exp[i][j];
24. }
25. }
The function Expansion() is responsible for converting each of the 4 bits into 6 bits, so after the execution of the function, content of right[32] is converted into 48 bits. In line 23, the array named expansion[48] contains all 48 bits; thus, the bits of right[32] are expanded into a block of 48 bits. Now, it has become more convenient, so that the XOR operation between the expanded content and the 48-bit key is possible, because all of the bits are the same in length, which is 48.
5.5.12 The xor_oneE(int round) Function
1. void DES::xor_oneE(int round){
2. //for Encrypt
3. int i;
4. for(i = 0; i<48; i++)
5. xor1[i] = expansion[i]^keyi[round-1]
[i];
6. }
For each of the rounds out of 16, the function xor_oneE(int) is called. There is one array expansion, and another one is keyi[round][48]. The first array holds the previously expanded 48-bit content of the plaintext, and the second one holds the 48-bit secret key that is separate according to the round. There are 16 separate keys for each of the16 rounds. Now, after executing the xor_oneE(int), the XORed result is stored in the xor1[48] array.
5.5.13 The Substitution() Function
1. void DES::substitution(){
2. int s1[4][16] = {
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
3. };
4. int s2[4][16] = {
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
5. };
6. int s3[4][16] = {
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
7. };
8. int s4[4][16] = {
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
9. };
10. int s5[4][16] = {
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
11. };
12. int s6[4][16] = {
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
13. };
14. int s7[4][16] = {
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
15. };
16. int s8[4][16] = {
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
17. };
18. int a[8][6],k = 0,i,j,p,q,count = 0,g = 0,v;
19. for(i = 0; i<8; i++){
20. for(j = 0; j<6; j++){
21. a[i][j] = xor1[k++];
22. }
23. }
24. for(i = 0; i<8; i++){
25. p = 1;
26. q = 0;
27. k = (a[i][0]*2)+(a[i][5]*1);
28. j = 4;
29. while(j>0){
30. q = q+(a[i][j]*p);
31. p = p*2;
32. j− ;
33. }
34. count = i+1;
35. switch(count){
36. case 1:
37. v = s1[k][q];
38. break;
39. case 2:
40. v = s2[k][q];
41. break;
42. case 3:
43. v = s3[k][q];
44. break;
45. case 4:
46. v = s4[k][q];
47. break;
48. case 5:
49. v = s5[k][q];
50. break;
51. case 6:
52. v = s6[k][q];
53. break;
54. case 7:
55. v = s7[k][q];
56. break;
57. case 8:
58. v = s8[k][q];
59. break;
60. }
61. int d,i = 3,a[4];
62. while(v>0){
63. d = v%2;
64. a[i— ] = d;
65. v = v/2;
66. }
67. while(i> = 0){
68. a[i— ] = 0;
69. }
70. for(i = 0; i<4; i++)
71. sub[g++] = a[i];
72. }
73. }
The function substitution has eight S-boxes that are used for substituting the extra bits from the 48-bit XORed result. Now, the basic target of this function is to reduce the bit size of the 48-bit content that was XORed with the 48-bit key; the new size of that XORed content will be 32 after the execution of the function. For the 48-bit content there are eight blocks of bits in which each of the blocks has six bits. The first and the last bit together indicate the row number of the S-box, and the other four bits indicate the column number in the S-box array. Out of eight blocks, each of them indicates the respective S-boxes; for example, the first block of 6 bits refers to s1[4][16], the second block refers to s2[4][16], and so on up to s8[4][16]. After finishing the function call, the 48-bit content is converted into 32-bit content and stored in the sub[32] array. With this bit value the next function, permutation(), continues.
5.5.14 The Permutation() Function
void DES::permutation(){
p[0] = sub[15];
p[1] = sub[6];
p[2] = sub[19];
p[3] = sub[20];
p[4] = sub[28];
p[5] = sub[11];
p[6] = sub[27];
p[7] = sub[16];
p[8] = sub[0];
p[9] = sub[14];
p[10] = sub[22];
p[11] = sub[25];
p[12] = sub[4];
p[13] = sub[17];
p[14] = sub[30];
p[15] = sub[9];
p[16] = sub[1];
p[17] = sub[7];
p[18] = sub[23];
p[19] = sub[13];
p[20] = sub[31];
p[21] = sub[26];
p[22] = sub[2];
p[23] = sub[8];
p[24] = sub[18];
p[25] = sub[12];
p[26] = sub[29];
p[27] = sub[5];
p[28] = sub[21];
p[29] = sub[10];
p[30] = sub[3];
p[31] = sub[24];
}
The above function is utilized to permute the content of the sub[32] and stores all 32 bits in another array named p[32]. Finishing the function execution, the p[32] array holds the 32 permuted bits.
5.5.15 The xor_two() Function
1. void DES::xor_two(){
2. int i;
3. for(i = 0; i<32; i++){
4. xor2[i] = left[i]^p[i];
5. }
6. }
The above function actually makes an XOR operation between the content of the left[32] array and the immediately permuted 32 bits of p[32]. The result of 32 bits is saved in xor2[32]. After the function execution, the next operations continue from line 40 in the function named Encrypt(char *). Readers are requested to jumpinto that specific line of code to have a look at the next steps.
5.5.16 The Decrypt(char *) Function
1. char * DES::Decrypt(char *Text1){
2. int i,a1,j,nB,m,iB,k,K,B[8],n,t,d,round;
3. char *Text = new char[1000];
4. unsigned char ch;
5. strcpy(Text,Text1);
6. i = strlen(Text);
7. //keygen();
8. int mc = 0;
9. for(iB = 0,nB = 0,m = 0;
m<(strlen(Text)/8); m++){
10. /*Repeat for TextLength/8 times*/
11. for(iB = 0,i = 0; i<8; i++,nB++){
12. ch = Text[nB];
13. n = (int)ch;//(int)Text[nB];
14. for(K = 7; n> = 1; K— ){
15. B[K] = n%2; //
Converting 8-Bytes to
64-bit Binary Format
16. n/= 2;
17. }
18. for(; K> = 0; K— ) B[K] = 0;
19. for(K = 0; K<8; K++,iB++)
total[iB] = B[K];
20. /*Now 'total' contains the
64-Bit binary format of
8-Bytes*/
21. }
22. IP();
23. for(i = 0; i<64; i++) total[i] =
ip[i];
24. for(i = 0; i<32; i++) left[i] =
total[i];
25. for(; i<64; i++) right[i-32] =
total[i];
26. for(round = 1; round< = 16;
round++){
27. Expansion();
28. xor_oneD(round);
29. substitution();
30. permutation();
31. xor_two();
32. for(i = 0; i<32; i++) left[i]
= right[i];
33. for(i = 0; i<32; i++)
right[i] = xor2[i];
34. }//16 rounds end here
35. for(i = 0; i<32; i++) temp[i] =
right[i];
36. for(; i<64; i++) temp[i] =
left[i-32];
37. inverse();
38. /* Obtaining the Cypher-Text into
final[1000]*/
39. k = 128;
40. d = 0;
41. for(i = 0; i<8; i++){
42. for(j = 0; j<8; j++){
43. d = d+inv[i][j]*k;
44. k = k/2;
45. }
46. final[mc++] = (char)d;
47. k = 128;
48. d = 0;
49. }
50. } //for loop ends here
51. final[mc] = ' ';
52. char *final1 = new char[1000];
53. for(i = 0,j = strlen(Text);
i<strlen(Text); i++,j++)
54. final1[i] = final[j];
55. final1[i] = ' ';
56. return(final);
57. }
The function prototype of the function Decrypt(char *) indicates that it takes a character pointer as a parameter and returns another memory address so that the type is also a pointer. This is a function responsible for decrypting or deciphering the encrypted message. For the decryption process, all the steps are the same, but the way of choosing the keys is different. During decryption, the order of the key is reversed. That means when decrypting the ciphertext, the last key will be used first, then the second last, and so on. Both of the functions Encrypt(char *) and Decrypt(char *) are the same, but in the Decrypt(char *) function xor_oneD(round) is called instead of xor_ oneE(round). Among the previously selected 16 keys, xor_oneD(round) chooses the key in reverse order. That is the main difference between the encryption and decryption.
5.5.17 The Main() Function
1. int main(){
2. DES d1;
3. d1.keygen();
4. char *str = new char[1000];
5. cout<<"
Enter a string : ";
6. cin >> str;
7. char *str1 = new char[1000];
8. str1 = d1.Encrypt(str);
9. cout<<"
Encrypted Text: "<<str1<<endl;
10. cout<<"
o/p Text: "<<d1.
Decrypt(str1)<<endl;
11. }
The main() function is the supreme controller in most of the programming languages. In this chapter, C++ language is used to demonstrate the DES encryption-decryption, and there is also a main() function in this program, as usual. The function main() at first creates an object of the DES class; in this program DES is a user-defined class for demonstration purposes. The details of the DES class have been discussed in the prior sections of this chapter.
Now for creating an object of DES class, the function keygen() is called in the third line using the object created so far. Then, a string variable is declared to store the input string, which can store 1000 characters. After declaring the string variable, the string gets the input in the sixth line. In the eighth line, the function Encrypt(char *) is called to encrypt the plaintext and return the decrypted message into the string variable str1. A statement in line 9 shows the encrypted text that is already stored in str1. After all, the 10th line of the code calls the Decrypt(char *) function, and that function returns the decrypted plaintext so that users can see the decrypted text on the screen. Finally, a plaintext string is inputted through the keyboard, which is then encrypted and also decrypted to demonstrate that the program is working fine.