1. Preface
The difficulty of DES is concentrated in the 16-round iterative encryption algorithm of DES. This is also the fourth item that the teacher set as a must-take exam at the end of the cryptography semester when highlighting the key points.
2. The whole process of DES
The whole process of DES is divided into:
1. Initial replacement of plaintext M
2. Generate key set K={K1,K2,…,K16}
3. 16-round iteration round function
4. Inverse initial permutation and output ciphertext C
This article focuses on describing steps 2 and 3.
1. Initial replacement of plaintext M
Replace according to the initial replacement table IP of DES
char IP[8][8] =
{
{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}
};
2. Generate key set K={K1,K2,…,K16}
①Create initial key (64-bit)
The initial key is created by you during the encryption process, and all other substitution tables appearing below are fixed in the DES algorithm
② According to the replacement selection table 1, replace the key with 56-bit key0
Replacement selection table 1:
char PC_1[8][7] =
{
{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}
};
③ Divide key0 into left and right parts: C0, D0
PS: C0 and D0 are both 28 bits
④ According to the shift table, perform 16 rounds of shift calculations on C0 and D0, and record C:{C1,C2,…,C16}, D:{D1,D2,…,D16}
|
shift table |
|
|---|---|
| Number of rounds | Shift number left |
| 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 |
How to shift?
Assume key0 is “ABCDEFGH”
Then C0 corresponds to “ABCD”
D0 corresponds to “EFGH”
Comparing the shift table on the right, we can see that
C1 is “BCDA” obtained by shifting C0 by 1 bit.
D1 is “FGHE”
C2 is “CDAB”
D2 is “GHEF”
Of course, C0 D0 is a 28-bit bit stream. The “ABCDEFGH” here is just used to give an example of shifting.
⑤According to C:{C1,C2,…,C16}, D:{D1,D2,…,D16}, splice to get CD:{CD1,CD2,…,CD16}
⑥Compare CDn in CD:{CD1,CD2,…,CD16} with substitution selection table 2 to obtain K{K1,K2,…,K16}
K are all 48 bits
Select substitution table 2:
char PC_2[8][6] =
{
{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}
};
3. 16 rounds of iteration (round function)
Divide the 64-bit plaintext M into two 32-bit parts L0 R0
The 16 rounds of iteration are divided into two modes: the first 15 rounds and the 16th round.
First 15 rounds
① Find Rn
Rn-1′ is generated from Rn-1 and Kn through the f function (the f function is detailed in ③), and then Rn-1′ and Ln-1 are performed bitwise XOR to obtain Rn
② Find Ln
Ln = Rn-1
③f function
The f function is further divided into E-box permutation, S-box permutation and P-box permutation.
E-box replacement
According to the E box replacement table, extend Rn-1 from 32 bits to 48 bits E: {e1,e2,…,e48}
Then perform a bitwise XOR calculation on E and Kn to get E’:{e1,e2,…,e48}
char E[8][6] =
{
{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}
};
S-box replacement
Divide the E’:{e1,e2,…,e48} output from the E box into 8 equal parts, S={S1,S2,…,S8}
Take out the first and last digits of {e1,e2,e3,e4,e5,e6} in S1 and use e1e6 as the row number
Take out the remaining {e2,e3,e4,e5} and use e2e3e4e5 as the column number
Compare the S-box replacement table to find the number corresponding to the e1e6 row and the e2e3e4e5 column, and convert it into a binary sequence
Generate new S1′:{e1′,e2′,e3′,e4′}
For example, S1={110011}
e1e6 = 11 = 3
e2e3e4e5 = 1001 = 9
Therefore, in the S box replacement table 1, we find 3 rows of 9 bits, the value is 11, and the corresponding binary value is 1011.
So the output S1′ is {1011}
By analogy, we get S’:{S1′, S2′,…,S8′}
At this time S’ becomes 32 bits again
char S_Box[8][65] =
{
{
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
},
{
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
},
{
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,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
},
{
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
},
{
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
},
{
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
},
{
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
}
};
P box replacement
Replace S’ against the P box replacement table and output Rn-1′
char P[4][8] =
{
{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}
};
Round 16
The only difference from the first 15 rounds is that after calculating L16 and R16 according to the previous calculation rules, the two values are interchanged to obtain L16 and R16.
After 16 rounds, L16 and R16 are spliced to get Round16 (64 bits)
4. Inverse initial replacement
Perform permutation according to the inverse initial permutation table and output ciphertext C