DES算法流程分析与实现_des算法硬件实现

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
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
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
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，0~3）定位S盒的行，B2B3B4B5（0000~1111,0~15）定位S盒的列，行和列的组合定位到S盒中的具体的元素（元素值均为0~15，即0000~1111四比特）。该值的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
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
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
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）。