分组密码--DES详解

对称密码体制

对称密码体制：一种加密系统。其加密密钥和解密密钥是相同的，或者能够从其中之一推知另一个。对称密码体制根据对明文加密方式不同分为分组密码和流密码。

分组密码

分组密码按照一定长度（如64bit、128bit）对名文分组，然后以组为单位进行加、解密。

分组密码系统：对不同的组采用同样的密钥k来进行性加密、解密。
明文组：

密文：

分组密码设计就是找到一种算法，能在密钥的控制下，从一个足够大、足够好的置换子集中简单、迅速的选出一个置换、对当前输入的明文数字组进行加密变换。
算法要求：

• 分组长度足够大，使得不同明文分组的个数2^n足够大，以防止明文被穷举法攻击。
• 密钥空间应足够发，尽可能消除弱密钥，从而使所有密钥同等概率，以防穷举密钥攻击，同时密钥不能太长，以利于密钥管理。
• 由密钥确定的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抵抗各种已知的攻击，差分攻击、线性攻击等。
• 要尽量使用适合编程的子块和简单的运算
• 加密解密应具有像是性。

分组密码的一般结构

Feistel结构

• 明文P为64b的数据被平分为32b的L0和R0，如果明文数据不足64b就用一种特殊的方法填充到64b。
• +表示异或
• K表示种子密钥64位，ki表示子密钥，是48b的密钥。那这里就会有疑问了，密钥是48b的数据，每次加密的明文是32b的数据，怎么如何进行加密呢，这里就是F的作用了，
• F是轮函数，在轮函数里面会对数据进行处理，首先会对明文进行E拓展置换，然后明文就变换为48b的数据，让后与ki进行异或，在进行S盒替换目的是在压缩为32b数据，和P盒替换四个过程。
• 结果：Li=R(i-1) ； Ri=L(i-1)异或F(Ri-1,ki)

SP结构

F轮函数内容

F轮函数包括（E扩展置换-数据扩展为48b、数据与密钥异或、S盒压缩处理-数据变为32b、P盒置换）

E拓展置换

• E拓展置换简单来说就是把分组后的32b的数据拓展为48位数据，为了盒子密钥进行异或。我们假设32b的数据就是如下图排列，那么黄色标注的数据就是添加的数据，也就是把原本8行4列的数据拓展为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

• 拓展原理
  • 第一步：就是把32b的数据，变为8组4b的数据。
  • 第二步：然后再每组后面添加下一组的第一个数据.
  • 第三步：再每组数据前面添加上一组数据的最后一个数据。
  • 第四步：第一组和第八组分别没有前一组和后一组，那他们两组就是首尾相连。就是32位数据组成一个循环的圈，那每一组都会有前驱和后继了。

S盒压缩处理

经过拓展的48位明文和密钥进行异或运算后，再使用8个S盒压缩处理得到32位数据。

• 将48位数据分为8块，每6位压缩为4位数据。
• 每一组数据取头尾两个数组成一个二位二进制数作为列，中间4位数对应行，找相应s和该位置数据就是转换后的数据，如六位011001取第一位和第六位是01那就是第一行，中间四位是1100那就是第十二列，假设为第一组的数据那就去找S1盒的1行12列对应数据是9，那转换后的数据就是1001
• 注意点：行和列对应的范围是0-3和0-15.
• s盒对应表很容易在网上寻找，这里我也复制下来了。

• S1盒

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	14	4	13	1	2	15	11	8	3	10	6	12	5	9	0	7
1	0	15	7	4	14	2	13	1	10	6	12	11	9	5	3	8
2	4	1	14	8	13	6	2	11	15	12	9	7	3	10	5	0
3	15	12	8	2	4	9	1	7	5	11	3	14	10	0	6	13

• S2盒

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	15	1	8	14	6	11	3	4	9	7	2	13	12	0	5	10
1	3	13	4	7	15	2	8	14	12	0	1	10	6	9	11	5
2	0	14	7	11	10	4	13	1	5	8	12	6	9	3	2	15
3	13	8	10	1	3	15	4	2	11	6	7	12	0	5	14	9

• S3盒

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	10	0	9	14	6	3	15	5	1	13	12	7	11	4	2	8
1	13	7	0	9	3	4	6	10	2	8	5	14	12	11	15	1
2	13	6	4	9	8	15	3	0	11	1	2	12	5	10	14	7
3	1	10	13	0	6	9	8	7	4	15	14	3	11	5	2	12

• S4盒

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	7	13	14	3	0	6	9	10	1	2	8	5	11	12	4	15
1	13	8	11	5	6	15	0	3	4	7	2	12	1	10	14	9
2	10	6	9	0	12	11	7	13	15	1	3	14	5	2	8	4
3	3	15	0	6	10	1	13	8	9	4	5	11	12	7	2	14

• S5盒

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	2	12	4	1	7	10	11	6	8	5	3	15	13	0	14	9
1	14	11	2	12	4	7	13	1	5	0	15	10	3	9	8	6
2	4	2	1	11	10	13	7	8	15	9	12	5	6	3	0	14
3	11	8	12	7	1	14	2	13	6	15	0	9	10	4	5	3

• S6盒

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	12	1	10	15	9	2	6	8	0	13	3	4	14	7	5	11
1	10	15	4	2	7	12	9	5	6	1	13	14	0	11	3	8
2	9	14	15	5	2	8	12	3	7	0	4	10	1	13	11	6
3	4	3	2	12	9	5	15	10	11	14	1	7	6	0	8	13

• S7盒

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	4	11	2	14	15	0	8	13	3	12	9	7	5	10	6	1
1	13	0	11	7	4	9	1	10	14	3	5	12	2	15	8	6
2	1	4	11	13	12	3	7	14	10	15	6	8	0	5	9	2
3	6	11	13	8	1	4	10	7	9	5	0	15	14	2	3	12

• S8盒

	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
0	13	2	8	4	6	15	11	1	10	9	3	14	5	0	12	7
1	1	15	13	8	10	3	7	4	12	5	6	11	0	14	9	2
2	7	11	4	1	9	12	14	2	0	6	10	13	15	3	5	8
3	2	1	14	7	4	10	8	13	15	12	9	0	3	5	6	11

P盒转换

P盒转换和初始转换相似，原理是一样的，这里先不说转换过程，等到下面初始置换的时候再说，现在这里保存P盒置换表

DES

DES是分组长度为64b的分组密码算法。密钥长度也是64b，其中每8b有一个奇偶校验位，所以有效长度为56b。采用Feistel结构。

DES算法框图

初始置换IP和初始逆置换IP：将明文数据用初始置换IP置换，得到一个乱序的64b明文分组，然后分组，经过16轮完全类似的迭代运算后，将所得的左右数据合并，最后使用初始逆置换IO置换，产生密文数据组。

初始置换

我们拿到的64为数据首先要进行初始置换，那么我们拿到的应该是一组有含义的数据我们假设是64个0、1二进制流，那么初始置换就是这些数据根据下表从新排列一边，这一步是很简单的，如我们对应下表，应该把源数据的第58个数据提到第一个位置，把第50个数据提到第二的数据，就是根据下表进行对应位置的转换。

初始置换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

16轮迭代加密

上面基本已经讲了，在这里就说一下这个子密钥的生成。

子密钥的生成

密钥为64位的密钥，出去8位校验位，剩余的56位参与运算。
首先我们要用一个PC-1表把密钥的8位校验位去除，并且重新排序，这个和明文的初始置换是差不多的。
PC-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

然后我们把着56位的密钥，分为28位的两组数据，染后根据移位次数表分别左移，如我们要求第一次的子密钥，就把这两组28位密钥分别左移1位然后根据PC-2置换就是第一次的子密钥了，求第二次的子密钥就是在第一次的两组上在分别左移2位，在用PC-2置换回来，就是k2了。不知道有有没有写明白。

第i次迭代	1	2	3	4	5	6	7	8
循环左移次数	1	1	2	2	2	2	2	2
第i次迭代	9	10	11	12	13	14	15	16
循环左移次数	1	2	2	2	2	2	2	1

PC-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

IP-1置换

把得到的R16和L16组合数据根据逆置换表置换就完成了。

逆置换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

总结

我们得到64b的明文（不足64b的补足），我们首先使用IP置换处理一下明文，然后把他们分为两组32b的数据，然后两组数据进入16次迭代运算，16次迭代中每次有一组数据和一组子密钥（48b）进行异或运算，首先要把数据进行E扩展变为48b数据，然后进行异或，在经过S盒压缩处理，最后经过P置换，这就完成了F轮函数的过程，最后和另一组数据进行异或，完成一轮迭代，最后进行IP-1置换，完成加密，得到密文。