DES算法流程分析与实现_s盒输入101011

DES（Data Encryption Standard，数据加密标准）作为一种基本结构为Feistel结构的加密算法，其加密核心在于F函数。而Feistel结构决定了其加密解密流程是相同的，无论是硬件实现还是软件实现都只需要一种结构，不需要分别实现。关于Feistel和DES在Feistel结构中的设计可以参考： Feistel网络结构与DES加密算法的框架简单分析 。今天我们重点来分析关于加密流程中用到的15张表的使用（初始置换表、
密钥置换表、子密钥移位表、子密钥压缩置换表、明文扩展置换表、S盒的8张压缩置换表、P盒置换表、末置换表），及其具体的实现方式。

1、DES基本结构：

我们采用CBC-DES的加密模式，即先用初始化向量iv和明文分组进行异或，得到的结果进行加密即是密文分组，从第二组开始iv就是上一组的密文。解密方式与加密方式相反：先解密密文分组，再与iv进行异或得到明文分组（关于CBC分组加密模式可参考：TEA加密算法与分组密码的ECB、CBC模式选定 ）。

文件读取与CBC分组加密的代码如下：

//此时初始向量和密钥已经随机生成（或者从密钥文件中读取出来）
FILE * fpin = fopen(infile, "r");	
assert(fpin != NULL);
FILE * fpout = fopen(outfile, "w");	
assert(fpout != NULL);
int len = 0;
while(!feof(fpin)){
	if((len = fread(data, 1, 8, fpin)) == 0){//没有读到内容则结束
		if(!feof(fpin))
			printf("文件读写出错!\n");
		break;
	}
	else{
	//enum OperType{ENCRYPT, DECRYPT};type是根据命令行传参-e还是-d来确定的
		if(type == ENCRYPT){
			//先异或，再加密，加密完成后更新向量为加密后的秘文
			xor_bit(iv, data, data, 64);
			des_AlgorithmDeal(data, key, type);
			memcpy(iv, data, 8);
		}
		else{
			memcpy(temp , data, 8);//因为data会改变，data改变后需要用其改变前的值，因此要保存
			//先解密，再异或，异或完成后更新向量为上一组秘文
			des_AlgorithmDeal(data, key, type);
			xor_bit(iv, data, data, 64);
			memcpy(iv, temp, 8);//秘文组复制非iv
		}
		fwrite(data, 1, 8, fpout);
	}
	memset(data, 0, 8);
}
fclose(fpin);
fclose(fpout);
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

其中DES模块的基本结构如下所示：

关于各个部分及细节，我们后面一一来详细分析。

2、子密钥产生：

首先由于DES是16轮循环，所以需要由64bit的随机密钥Key生成16个子密钥Ki（i从0~15），Key共64bit，但是其每个字节的最后一位都用不到（即第8、16、24、32、40、48、56、64位共8位），所以先通过初始置换将64bit的密钥转换为56bit。而转换是根据密钥转换表（编程时一系列表均用数组来存储）来操作的，如下所示：

该表共有56个元素（可以看到不包含8、16、24、32、40、48、56、64），代表了转换后的56bit的位置（即output的下标）。而对应位置的数字x，表示转换前64bit密钥的下标+1（即input的bit位置）。比如：第1位（下标为0，位置为1）的值为57，即**set_bit(output, 0, ge_bit(input, 56));**获取原来的第57位的bit值（0或1），作为置换后的第1位的bit值。依次类推（表的读取方式为从左到右，从上到下，如：第3行第5个为置换后的第2*14+5=33位）。

置换的函数如下所示（该函数后面会多次用到，所以需要考虑不同位数的置换，最多64个元素置换，temp[]的大小就选为8*8=64）：

//source为要置换的分组（可能大小8Byte、7B、6B、4B），index为置换表，len为置换的位数（即index表中的元素个数）
void permute(unsigned char * source, const int * index, int len)
{
	unsigned char temp[8] = {0};
	for(int i = 0; i < len; i++){
		set_bit(temp, i, get_bit(source, index[i]-1));//表中是从1开始，数组下表要减去1
	}
	memcpy(source, temp, len/8);
}
1
2
3
4
5
6
7
8
9

经过置换的key变为56bit，该56bit分为左右两半部分**：left_key和right_key**，各28bit，然后左右两部分分别循环左移一定位数n。n的大小根据子密钥Ki的下标决定（i从0~15），如下表所示（最多循环左移两位，最少一位）：

经过移位的左右两部分合并为56bit，然后经过压缩置换将56bit压缩为48bit，则产生一个子密钥Ki，经过16轮循环产生16个子密钥（对应DES结构图）。而压缩置换的压缩表如下：

子密钥的产生代码如下所示：

if(key != NULL){//子密钥生成，key为随机产生的64bit密钥	
	memcpy(temp, key, 8);//temp暂存key
	//密钥置换：64bit->56bit
	permute(temp, DesTransform, 56);//DesTransform为密钥置换表
	//密钥分为左右两部分各自28bit
	memset(lkey, 0, 4);
	memset(rkey, 0, 4);
	for(i = 0; i < 28; i++){
		set_bit(lkey, i, get_bit(temp, i));//temp的前28给left
		set_bit(rkey, i, get_bit(temp, i+28));//temp的后28给right
	}

	//进行16次循环，分别求出16个子密钥
	for(i = 0; i < 16; i++){
	//DesSubkey为循环移位表
		rol_bit(lkey, 28, DesSubkey[i]);//左边28位循环左移
		rol_bit(rkey, 28, DesSubkey[i]);//右边28位循环左移
		for(j = 0; j < 28; j++){//和并为56bit是子密钥
		//subKey[16][7]共16个（7*8=56）未压缩的子密钥
			set_bit(subKey[i], j, get_bit(lkey, j));	
			set_bit(subKey[i], j+28, get_bit(rkey, j));	
		}
		//子密钥压缩置换成48位子密钥
		permute(subKey[i], DesPermuted, 48);//DesPermuted为压缩置换表
	}
}
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

3、明文初始置换与扩展：

64bit的明文分组，首先经过明文初始置换表（64bit->64bit的置换），打乱原有明文bit顺序。类似于密钥初始置换表，但是密钥初始置换表是需要进行压缩的（64bit->56bit），明文初始置换表如下：

经过初始置换，将64bit明文分组分为左右两部分，各32bit。下一轮的左半部分是本轮的右半部分；下一轮的右半部分：是本轮的右半部分和子密钥Ki经过F函数运算的结果，再和本轮的左半部分进行异或得到的。

而F函数中第一步是进行扩展置换，将32bit的rdata扩展成为48bit的exp_data，扩展置换表为如下所示（扩展函数依旧是permute()只不过参数是rdata、扩展置换表、扩展置换表长度）：

经过扩展置换的明文rdata和经过压缩置换的子密钥Ki均为48bit，二者进行异或以后进入下一步操作：S盒置换。

4、S盒置换、P盒置换与末置换：

由于上一步的异或结果是48bit，我们要将异或结果重新压缩到32bit并经过P盒置换（32bit->32bit）后，与原有左半部分32bit异或得到下轮的右半部分。而48bit压缩到32bit不是用一张长度为32的置换表从48bit信息中选取32位进行置换。而是通过8个S盒进行8组6bit->4bit的置换（8*4=32bit）：即将48bit按顺序分为8组，每组6bit。然后将每一组的6bit信息输入对应的S盒，输出4bit的信息，8组输出合并为32bit的压缩结果。8个S盒的内容均不一样，但是使用方式都是一样的，S盒如下所示：

使用方式为输入6bit为B1B2B3B4B5B6，B1B6两比特（00_11，03）定位S盒的行，B2B3B4B5（0000_1111,015）定位S盒的列，行和列的组合定位到S盒中的具体的元素（元素值均为0_15，即00001111四比特）。该值的4bit 信息作为输出的4bit。如：S1盒的输入为101011，则行为11 = 3，列为0101 = 5，即（3,5）= 9 = 1001，则输出为1001。

经过8组6bit到4bit的转换之后，将合并的32bit经过P盒置换提高混乱度，P盒置换表如下所示：

明文置换、扩展置换、S盒置换、P盒置换的代码如下：

//明文初始置换
memcpy(temp, data, 8);
permute(temp, DesInitial, 64);//DesInitial为初始置换表

//明文分组分成左右两部分各自32bit
memcpy(ldata, &temp[0], 4);
memcpy(rdata, &temp[4], 4);
for(i = 0; i<16; i++){
	//32bit经过扩展后为48bit
	memcpy(exp_data, rdata, 4);
	permute(exp_data, DesExpansion, 48);//DesExpansion扩展置换表
	//压缩后的子密钥和扩展后的明文有半部分进行异或操作,结果放入xor_data[]中
	if(type == ENCRYPT){
		xor_bit(subKey[i], exp_data, exp_data, 48);//加密:K0~K15
	}
	else{	
		xor_bit(subKey[15-i], exp_data, exp_data, 48);//解密:K15~K0
	}
	//S盒代替压缩：(6*8)48bit->(4*8)32bit
	for(j = 0, p = 0; j < 8; j++){//p从0~32
		//根据6bit信息获取行和列
		row = (get_bit(exp_data, j*6+0) * 2) + (get_bit(exp_data, j*6+5) * 1); //b1b6
		col = (get_bit(exp_data, j*6+1) * 8) + (get_bit(exp_data, j*6+2) * 4) +
			  (get_bit(exp_data, j*6+3)) * 2 + (get_bit(exp_data, j*6+4) * 1); //b2b3b4b5
		//根据行和列获取Ｓ盒中对应值，计算4bit信息
		value = (unsigned char)DesSbox[j][row][col];//DesSbox为S盒置换表DesSbox[8][4][16],8个4行16列
		//value为0~15，从左到右取第4、5、6、7位（低四位）即可，即4bit
		for(k = 4; k < 8; k++){
			set_bit(exp_data, p, get_bit(&value, k));
			p++;
		}
	}
	//做Ｐ盒置换
	permute(exp_data, DesPbox, 32);
	//置换结果与最初左半部分异或得到右半部分
	xor_bit(exp_data, ldata, exp_data, 32);
	//右半部分32bit作为左半部分
	memcpy(ldata, rdata, 4);
	memcpy(rdata, exp_data, 4);
}
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

在十六轮运算完毕之后，需要进行左右两部分置换（其实是：最后一轮不用左右置换，但是16轮循环中为一种模式，即均置换。所以再左右置换一次相当于最后一轮没置换）。然后将结果做末置换（类似于初始置换），最终的结果就是明文分组的DES加密结果，末置换表如下：

末置换代码如下：

//最后一轮操作不需要左右调换，则复制回去时再将已经调换的调换一次，即没有调换
memcpy(data, rdata, 4);//data为输入的明文64bit，输出时（函数返回时）应为64bit密文
memcpy(data + 4, ldata, 4);
//末置换
permute(data, DesFinal, 64);//DesFinal末置换表
return;//data此时为密文
1
2
3
4
5
6

5、用到的bit操作函数：

#include "bit.h"
//获取指定地址指定位信息（0/1）
int get_bit(unsigned char * input, int pos)
{
	//单字节最高位为第0位，最低位为第7位
	unsigned char mask, i, bit;
	for(bit = pos % 8, mask = 0X80, i = 0; i < bit; i++){
		mask >>= 1;
	}
	return ( ( (mask & input[pos/8]) == mask ) ? 1 : 0 );
}
//设置指定地址指定位信息（value = 0/1）
void set_bit(unsigned char * input, int pos, int value)
{
	unsigned char mask, i, bit;
	for(bit = pos % 8, mask = 0X80, i = 0; i < bit; i++){
		mask >>= 1;
	}
	(value) ? (input[pos/8] |= mask) : (input[pos/8] &= (~mask));
}
//异或操作,output存储异或后的结果，size为需要异或的位数
void xor_bit(unsigned char * input1, unsigned char * input2, unsigned char * output, int size)
{
	int i;
	for(i = 0; i < size; i++){
		if(get_bit(input1, i) == get_bit(input2, i)){
			set_bit(output, i, 0);//相同为0
		}
		else{	
			set_bit(output, i, 1);//不同为1
		}
	}
}
//循环左移，size为总循环的长度，num为循环左移的位数
void rol_bit(unsigned char * input, int size, int num)
{
	//注意：低字节为左，高字节为右（与字符存储方式对应）
	int left_bit = 0, loop_bit = 0, i = 0, j = 0;

	if(size > 0){
		for(i = 0; i < num; i++){//循环左移一位，共num次
			for(j = 0; j <= (size-1)/8; j++){//多字节操作
				left_bit = get_bit(&input[j], 0);//获取最高位
				if(j == 0){
					//如果是低字节，则其第一位，是左边溢出的，需要保存并在最终放到高字节右边最后一位
					loop_bit = left_bit;
				}
				else{
					//不是则直接将本字节第一位，设置到上一字节（低字节也是左边的字节）最后一位
					set_bit(&input[j-1], 7, left_bit);
				}
				input[j] <<= 1;
			}
			//把左边移出的一位，移入最右边一位（即循环左移）
			set_bit(input, size-1, loop_bit);
		}
	}
}
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

测试1：
关于随机密钥的产生和随机初始向量的产生采用rand()随机数函数模拟，可以看到每次加密产的密钥和初始向量都不同（前半部分为密钥，后半部分为iv），我们在加密时产生key.txt并保存密钥和iv，将该DES加密密钥和初始向量通过双钥密钥的公钥密钥加密后（如RSA），与密文一块儿传递给通信对方即可：

测试2：
一首我最喜欢的《成功的花》用来测试，可以正常加密解密。需要注意的是：如果原明文文件大小LEN%8不为0，则加密后的文件是会增大的。因为最后一个分组可能有用信息只有mbit（m<8），则剩余8-mbit会被自动填充为0，而填充的0也是被加密了的。所以解密后文件末尾有一串’\0’，Windwos记事本、cat命令可能都看不见，但是用vim打开就可以观察到（但是：这对通信没有任何影响，只是一个现象而已，因为即使密文被截获，也知道了最后一组的名文中包含’\0’，但是由于是CBC加密模式，后一组加密收受前一组影响，是不能根据最后一组的明文破解出密钥和iv的。但如果是ECB模式就不好说了）。

测试代码：DES文件加密解密算法实现，需要免费获取的可邮箱联系索取（mailbox_krj@163.com）。关于代码邮件恢复不及时问题，可直接在密码算法专题汇总此专题博客中获取GITHUB链接（2021-09-26 10:27）