文章

DES 加密以及 3DES

发表于 更新于
作者 b1ink
12 分钟阅读
DES 加密以及 3DES

DES

DES，数据加密标准，即 Data Encryption Standard 一种对称分组加密算法。 其算法被称为 DEA(Data Encryption Algorithm，数据加密算法)。

其算法核心分为两个部分：子密钥生成和数据加解密。

子密钥生成

  1. 初始密钥处理：
    • 将 64 位密钥通过 $PC_1$ 置换表，去掉 8 位校验位（直接舍弃），获得 56 位密钥表示为 $ K’ $。
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

     const PC1: [usize; 56] = [
     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
 ];

 fn permute_key_64_to_56(key: u64) -> u64 {
     let mut key_56 = 0;
     for i in 0..56 {
         if key & (1 << (PC1[i] - 1)) != 0 {
             key_56 |= 1 << i;
         }
     }
     key_56
 }
  2. 生成 16 轮子密钥：
    • 将 $ K’ $ 分成左右两部分，每部分 28 位，分别记为 $ C_0 $ 和 $ D_0 $ 。
    • 对于第 $ n $ 轮（$ 1 \leq n \leq 16 $），对 $ C_{n-1} $ 和 $ D_{n-1} $ 进行左旋移位后得到 $ C_n $ 和 $ D_n $ 。
    • 将 $ C_n $ 和 $ D_n $ 连接起来，形成一个 56 位的字符串，表示为 $ C_nD_n $ 。
    • 对 $ C_nD_n $ 进行 $PC_2$ 置换，选择其中的 48 位作为第 $ n $ 轮的子密钥 $ K_n $ 。
    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

     const PC2: [u8; 48] = [
     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
 ];
 fn subkey_permute(key_56: u64) -> u64 {
     let mut subkey = 0;
     for i in 0..48 {
         if key_56 & (1 << (PC2[i] - 1)) != 0 {
             subkey |= 1 << i;
         }
     }
     subkey
 }
 fn generate_subkeys(key: u64) -> [u64; 16] {
    let mut subkeys = [0; 16];
    let mut c0 = (key >> 28) & 0x0FFFFFFF; // 高28位
    let mut d0 = key & 0x0FFFFFFF; // 低28位
    for i in 0..16 {
        c0 = rotate_left(c0,LEFT_ROTATION_TABLE[i]);
        d0 = rotate_left(d0,LEFT_ROTATION_TABLE[i]);
        let subkey = (c0 << 28) | d0;
        subkeys[i] = subkey_permute(subkey);
    }
    subkeys

 }

数据加解密

  1. 初始置换 (IP)：
    • 将 64 位的明文通过初始置换表 $IP$ 进行置换，得到新的 64 位数据。
    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

     const IP: [u8; 64] = [
     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
 ];

 fn initial_permute(text: u64) -> u64 {
    let mut permuted_text = 0;
    for i in 0..64 {
        if text & (1 << (IP[i] - 1)) != 0 {
            permuted_text |= 1 << i;
        }
    }
    permuted_text
 }
  2. 16 轮加密：
    • 将初始置换后的数据分为左右两部分，每部分 32 位，分别记为 $ L_0 $ 和 $ R_0 $ 。
    • 对于第 $ n $ 轮加密 ($ 1 \leq n \leq 16 $) ，执行以下操作：
      1. 将 $ R_{n-1} $ 通过扩展置换 $E$ 扩展为48位，表示为 $ E(R_{n-1}) $ 。
      2. 将 $ E(R_{n-1}) $ 与第 $ n $ 轮的子密钥 $ K_n $ 进行异或操作，得到 48 位的结果。

      解密过程中，子密钥 $ K_n $ 的使用顺序与加密过程相反，即 $ K_{16} $ 到 $ K_1 $ 。

      1. 将异或结果通过 S 盒进行替换，得到 32 位的输出。
      2. 将S盒输出通过 P 盒进行置换，得到 32 位的 $ f(R_{n-1}, K_n) $ 。
      3. 计算 $ L_n = R_{n-1} $ 和 $ R_n = L_{n-1} \oplus f(R_{n-1}, K_n) $ 。
    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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131

     const EXPANSION: [u8; 48] = [
 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
 ];

 const S_BOXES: [[u8; 64]; 8] = [
     [
         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
     ]
 ];

 const  P_BOX: [u8; 32] = [
     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
 ];

 fn expansion_permute(r: u64) -> u64 {
 let mut expanded_r = 0;
 for i in 0..48 {
     if r & (1 << (EXPANSION[i] - 1)) != 0 {
         expanded_r |= 1 << i;
     }
 }
 expanded_r
 }

 fn s_box_permute(rint: u64) -> u64 {
     let mut result = 0;
     for j in (0..48).step_by(6) {
         let b = (rint >> j) & 0x3F; 

         let row = ((b & 0x20) >> 4) | ((b & 0x01) >> 0);

         let col = (b >> 1) & 0x0F;

         let s_box_output = S_BOXES[j / 6][((row as usize)*16) + (col as usize)];

         result |= (s_box_output as u64) << (j + 2);
     }
     result
 }

 fn p_box_permute(rint: u64) -> u64 {
     let mut permuted_rint = 0;
     for i in 0..32 {
         if rint & (1 << (P_BOX[i] - 1)) != 0 {
             permuted_rint |= 1 << i;
         }
     }
     permuted_rint
 }

 fn cipher(text:u64, subkeys: [u64; 16]) -> u64 {
 let first = initial_permute(text);
 let mut l = (first >> 32) & 0xFFFFFFFF;
 let mut r = first & 0xFFFFFFFF;
 for i in 0..16 {
     let mut tmp = expansion_permute(r) ^ subkeys[i];
     tmp = l ^ p_box_permute(s_box_permute(mp));
     l = r;
     r = tmp;
 } 
 let tmp = l;
 l = r;
 r = tmp;
 return final_permute((l << 32) | r);

 }
  3. 最终置换 (FP)：
    • 将第16轮的输出 $ L_{16} $ 和 $ R_{16} $ 合并，得到 64 位的数据。
    • 将合并后的数据通过最终置换表 FP 进行置换，得到 64 位的密文。

      若为解密则得到明文

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    const FP: [u8; 64] = [
 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
 ];

 fn final_permute(text: u64) -> u64 {
 let mut permuted_text = 0;
 for i in 0..64 {
     if text & (1 << (FP[i] - 1)) != 0 {
         permuted_text |= 1 << i;
     }
 }
 permuted_text
 }

3DES

3DES 即使用三次 DES 加(解)密，相当于用到 3 个密钥

\[\begin{aligned} C & = E_{K_3}(D_{K_2}(E_{K_1}(P))) \\ P & = D_{K_1}(E_{K_2}(D_{K_3}(C))) \end{aligned}\]

ENDING

春节将近，顺问冬安

参考资料
  1. DreamGo, (2018). 数据加密算法–详解DES加密算法原理与实现.
  2. 维基百科, (2024). 資料加密標準.
笔记
Encryption
本文由作者按照 CC BY 4.0 进行授权