DES学习记录

DES在过去的大多时间里，是最主流的分组密码。但是，因为它的密钥空间太小，所以并不是那么安全。不过，作为对称算法的典型，是值得学习的。

混淆和扩散

首先，我们先给出两个操作的概念，混淆和扩散。

混淆(Confusion)：是一种使密钥与密文间关系尽可能模糊的加密操作。如今实现混淆常用的一个元素就是替换。
扩散(Diffusion)：是一种为了隐藏明文统计属性而将一个明文符号的影响扩散到多个密文符号的加密操作。最简单的扩散元素就是位置换，常用于DES中；而AES啧使用更高级的Mixcolumn操作。

DES算法

DES是一种使用了56位密钥，对64位长分组进行加密的算法，它是一种对称密码，即加密和解密过程使用相同的密钥。DES对明文的每个分组的加密过程都包含了16轮，且每轮操作完全相同。每轮使用不同的子密钥，子密钥是由主密钥推导而来。

下面是DES流程图

在明文经过初始置换后，被分为 $L_0,R_0$ 。每轮操作都会把右半部分 $R_i$ 送入函数 $f$ 中，得到的输出和 $L_i$ 异或，最后这两部分交换，后面每轮都重复这个过程。

Step1：IP置换

IP置换的目的是把明文按位重新组合，并把输出分为 $L_0$ 、 $R_0$ 两部分。置换如下表

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

表中的数字代表新数据中此位置的数据在原数据中的位置，即原数据块的第58位放到新数据的第1位，第50位放到第2位，……依此类推，第7位放到第64位。置换后的数据分为 $L_0$ 和 $R_0$ 两部分， $L_0$ 为新数据的左32位， $R_0$ 为新数据的右32位。

需要要注意一点，位数是从左边开始数的，即0x0001最左边的位为1，最右边的位为64。

Step2:密钥置换

不考虑每个字节的第8位，DES的密钥由64位减至56位，每个字节的第8位作为奇偶校验位。产生的56位密钥由下表生成（注意表中没有8,16,24,32,40,48,56和64这8位）：

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

在DES的每一轮中，从56位密钥产生出不同的48位子密钥，确定这些子密钥的方式如下：

将56位的密钥分成两部分，每部分28位。

根据轮数，这两部分分别循环左移1位或2位。每轮移动的位数如下表：

轮数	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
位数	1	1	2	2	2	2	2	2	1	2	2	2	2	2	2	1

移动后，从56位中选出48位。这个过程中，既置换了每位的顺序，又选择了子密钥，因此称为压缩置换。置换规则如下表（注意表中没有9，18，22，25，35，38，43和54这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

Step3: $f$ 函数

$f$ 函数包含了：E扩展置换、S盒、P置换

E扩展置换

扩展置置换目标：是把32位输入扩展为48位(分为4位×8组)输出。扩展置换目的有两个：生成与密钥相同长度的数据以进行异或运算；提供更长的结果，在后续的替代运算中可以进行压缩。

扩展置换原理如下表：

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

最左和最右一列，是扩展数据。可以看出，扩展的数据是从相邻两组分别取靠近的一位，4位变为6位。靠近32位的位为1，靠近1位的位为32。表中第二行的4取自上组中的末位，9取自下组中的首位。

扩展置换之后，右半部分数据R0变为48位，与密钥置换得到的轮密钥进行异或。

S盒代替

压缩后的密钥与扩展分组异或以后，得到48位的数据，将这个数据送入S盒，进行替代运算。替代由8个不同的S盒完成，每个S盒有6位输入4位输出。48位输入分为8个6位的分组，一个分组对应一个S盒，对应的S盒对各组进行代替操作。

一个S盒就是一个4行16列的表，盒中的每一项都是一个4位的数。S盒的6个输入确定了其对应的输出在哪一行哪一列。若记一个输入的二进制为0b abcdef，那么0b af 决定了用盒中的第几行，0b bcde 决定了用盒中的第几列。

S盒依次如下

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	19
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	5	8	3	15	13	0	14	9
14	11	2	12	4	7	13	1	5	0	15	13	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

例如，假设S盒8的输入为110011，第1位和第6位组合为11，对应于S盒8的第3行；第2位到第5位为1001，对应于S盒8的第9列。S盒8的第3行第9列的数字为12，因此用1100来代替110011。注意，S盒的行列计数都是从0开始。

代替过程产生8个4位的分组，组合在一起形成32位数据。

S盒代替是DES算法的关键步骤，所有的其他的运算都是线性的，易于分析，而S盒是非线性的，相比于其他步骤，提供了更好安全性。

P盒置换

S盒代替运算的32位输出按照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

最后，P盒置换的结果与最初的64位分组左半部分L0异或，然后左、右半部分交换，接着开始另一轮。

Step4:IP末置换

末置换是初始置换的逆过程，DES最后一轮后，左、右两半部分并未进行交换，而是两部分合并形成一个分组做为末置换的输入。置换规则如下表：

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

经过以上步骤就可以得到密文。

reference：

DES算法详解 - songoo - 博客园 (cnblogs.com)
《深入浅出密码学——常用加密技术原理与应用》

混淆和扩散