DES加密详细解析

标签（空格分隔）： DES

DES概述

64位明文明文分组进行16轮完全相同的变换（轮函数）

56位有效密钥长度（外加8位奇偶校验位，总输入为64位）。

分组长度：64位

加密核心流程

整体流程如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    64位明文
        |
        ↓
初始置换（IP）
        |
        ↓
将64位分为左半（L0）、右半（R0），各32位
        |
        |----------------------|
        |                      |
        ↓ (16轮迭代)           ↓
   L[i] = R[i-1]         R[i] = L[i-1] ⊕ F(R[i-1], K[i])
        |                      |
        |----------------------|
        |         (i从1到16)
        ↓
16轮后，交换左右（L16, R16）→（R16, L16）
        |
        ↓
末置换（IP⁻¹，即IP的逆置换）
        |
        ↓
    64位密文

首先密匙的处理

首先提供64位的密匙（通常是8字节的密匙），在每一个字节的编码为长度为8的2进制值，而此时每个字节的第8位是奇偶检验位。

对密匙进行PC-1置换

此时在PC-1置换的过程中每个字节的第8位（奇偶检验位舍去），PC-1表是一个标准且固定的表。下面以每个字节（1-64排序去除奇偶检验位）呈现

1
2
3
4
5
6
7
8
9
10
11
// 左半部分 C₀ 的来源位置（位的位置编号从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,
 
// 右半部分 D₀ 的来源位置
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

此时将前28个分为$C_{0}$和$D_{0}$

然后进行偏移生成所有的$C_{n}$和$D_{n}$

在DES的16轮加密的时候每一轮对C和D循环左移位数是预先定义好的。

轮数 (Round i) 左移位数 (Shift Amount)
1, 2, 9, 16 1位
其他所有轮 (3,4,5,6,7,8,10,11,12,13,14,15) 2位
记忆技巧：只有第1、2、9、16轮移1位，其他都移2位。 
1
2
3
4
5
左移的情况
原始Cᵢ： b₁ b₂ b₃ b₄ ... b₂₇ b₂₈
左移后： b₂ b₃ b₄ ... b₂₈ b₁
原始Cᵢ： b₁ b₂ b₃ b₄ b₅ ... b₂₇ b₂₈
左移后： b₃ b₄ b₅ ... b₂₈ b₁ b₂

K[i]的生成

此时会通过PC-2生成K[i]，PC-2是固定的，如下

1
2
3
4
5
6
7
8
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

现在以k[1]的生成为例

1
2
3
4
5
6
C1 = 1110000110011001010101011111
D1 = 1010101011001100111100011110
拼接：C1||D1 = 11100001100110010101010111111010101011001100111100011110 (56位)
通过PC-2选择48位得到：
K[1] = 000110 110000 001011 101111 111111 000111 000001 110010
       (二进制分组，每6位一组，方便后续S盒处理)

就可以生成k[i]了。由于进行了16轮对密匙的处理，我们得到了16个子密匙。然后通常我们把密匙写成16进制可以得到以下类似的子密匙

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
K[1] = 1B02EFFC7072
K[2] = 79AED9DBC39E
K[3] = 55FC8A42CF99
K[4] = 72ADD3CBC955
K[5] = 7CEDB5E2F509
K[6] = 6B27834AF0FA
K[7] = 5DA5DD2F4396
K[8] = 627119730C5D
K[9] = 5C4CF396F27C
K[10]= 4F6ADE9F04B1
K[11]= 2F08E7843FDA
K[12]= 43C9FE5C9DC9
K[13]= 6D27A3A4E8F9
K[14]= 5B42D3ECBCD7
K[15]= 28EF7D5B9FDA
K[16]= 4E5A7EC3DB8F

明文的处理

填充

先将明文利用ASCLL值换为二进制。但是由于DES加密每一次只能对8个长度的数据块进行加密。所以会将剩下的数据块进行填充。

比如剩下m长度数据块，则剩下8-m长度的数据块的值都为8-m。然后就可以填充成为一个长度为8的数据块

然后对明文进行初始置换IP

明文置换的IP表是一定的所以我们用原始明文顺序从1-64来表示

1
2
3
4
5
6
7
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

然后再分为L0和R0如下

1
2
3
4
5
IP(M) = 11001100 00000000 11001100 11111111
        11110000 10101010 11110000 10101010
分为：
L0 = 11001100 00000000 11001100 11111111  (0xCC00CCFF)
R0 = 11110000 10101010 11110000 10101010  (0xF0AAF0AA)

16轮Feistel迭代

假设当前是第i轮（i从1到16），我们有：

输入：Lᵢ₋₁（左32位），Rᵢ₋₁（右32位）

子密钥：Kᵢ（48位，由密钥调度算法生成）

由于迭代会有些复杂我将把每一步列出来

第一步

1
复制Rᵢ₋₁（32位）作为轮函数F的输入

第二步

1
Rᵢ₋₁ (32位) → [E盒扩展] → E(Rᵢ₋₁) (48位)

E盒拓展: 直观规律：每组的第1位来自前一组最后1位，第6位来自后一组第1位
具体数值变成这样

1
2
输入32位的位置： 1  2  3  4  5  6  7  8 ... 32
输出48位的位置：32, 1, 2, 3, 4, 5, 4, 5, 6, 7, 8, 9, ... 31, 32, 1

第三步

与子密匙异或

1
E(Rᵢ₋₁) ⊕ Kᵢ = 48位中间结果

第四步

将48位结果分成8个6位组，每组送入一个不同的S盒（S1-S8）

S盒的结构
数量： DES共有 8个不同的S盒，记为 S1, S2, …, S8。

输入： 每个S盒的输入是 6位 数据（b1 b2 b3 b4 b5 b6）。

输出： 每个S盒的输出是 4位 数据。

位置： 在F函数中，与子密钥异或后的48位数据被平均分成8组，每组6位，分别进入对应的S1到S8盒进行处理。

  1. S盒的工作机制（查找表方法）
    每个S盒本质上是一个4行16列的固定查找表。6位输入如何在这个表中定位到一个4位输出，是理解S盒的关键。

  2. 查找步骤：

    行列确定：

    将6位输入 b1 b2 b3 b4 b5 b6 中的 首位b1和末位b6 组合成一个2位二进制数 (b1
    b6)。这个数的十进制值决定了查找的行号（0, 1, 2, 3）。

    将中间4位 b2 b3 b4 b5 组合成一个4位二进制数。这个数的十进制值决定了查找的列号（0 到 15）。

    输出获取：

    在对应的S盒表中，找到(行， 列)交叉位置的数字（范围是0-15，即4位二进制数）。

    将此数字转换为4位二进制，即为该S盒的输出。

第五步

对S盒获取的输出进行一个P盒(32位)混淆，和IT类似

1
2
3
4
5
6
7
8
9
10
P盒
 
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

第六步

此时获得的$R_{i}$和$L_{i}$进行异或运算再得到一个新的$R_{i}$

最后的最后将$R_{i}$和$L_{i}$进行交换得到下一轮的$R_{i}$和$L_{i}$（第16轮就不进行交换了）

最终合并

合并规则：

将最后一轮的输出按 R16 || L16 的顺序合并（即右半部分在前，左半部分在后）。

最后的最后进行末置换
$IP^{-1}$表如下

1
2
3
4
5
6
7
8
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

随后得到真正的密文

额外信息:S表

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
S1
 
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
-----------------------------------------------------
 
S2
 
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
-----------------------------------------------------
 
S3
 
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
-----------------------------------------------------
 
S4
 
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
-----------------------------------------------------
 
S5
 
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
-----------------------------------------------------
 
S6
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
-----------------------------------------------------
 
S7
 
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
-----------------------------------------------------
 
S8
 
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

解密过程

解密与加密完全相同的算法 (从前到后的顺序一样)，只是子密钥使用顺序相反：

加密：K1, K2, …, K16

解密：K16, K15, …, K1