分组密码之DES算法

DES(Data Encryption Standard)算法于1977年得到美国政府的正式许可，是一种用56位密钥来加密64位数据的方法。

DES是一种分组密码，明文、密文和密钥的分组长度都是64位，并且都是面向二进制的密码算法。DES处理的明文分组长度为64位，密文分组长度也是64位，使用的密钥长度为56位（实现上函数要求一个64位的密钥作为输入，但其中用到的只有56位，另外8位可以用作奇偶校验位或者其他用途）。DES的解密过程和加密相似，解密时使用与加密同样的算法，不过子密钥的使用次序要反过来。DES的整个体制是公开的，系统的安全性完全靠密钥的保密。

DES加密算法的加密过程经过了三个阶段，整体结构如图：

2011092714051344

算法主要包括：

初始置换IP、16轮迭代的乘积变换、逆初始置换IP-1以及16个子密钥产生器。

初始置换IP、逆初始置换IP-1：

将64 bit明文的位置进行置换，得到一个乱序的64 bit明文组，而后分成左右两段，每段为32 bit，以L0和R0表示，IP中各列元素位置号数相差为8，相当于将原明文各字节按列写出，各列比特经过偶采样和奇采样置换后，再对各行进行逆序。将阵中元素按行读出构成置换输出。
逆初始置换IP-1。将16轮迭代后给出的64 bit组进行置换，得到输出的密文组。输出为阵中元素按行读得的结果。
IP和IP-1在密码意义上作用不大，它们的作用在于打乱原来输入x的ASCII码字划分的关系，并将原来明文的校验位x8, x16,, x64变成为IP输出的一个字节。

其置换规则见下表：image

初始置换表IP

即将输入的第58位换到第一位，第50位换到第2位，…，依此类推，最后一位是原来的第7位。L0、R0则是换位输出后的两部分，L0是输出的左 32位，R0 是右32位，例：设置换前的输入值为D1D2D3……D64，则经过初始置换后的结果为：L0=D58D50…D8；R0= D57D49…D7。

image

逆初始置换表IP-1

具体置换图示如下：

image乘积变换F：

它是DES算法的核心部分。将经过IP置换后的数据分成32 bit的左右两组，在迭代过程中彼此左右交换位置。
每次迭代时只对右边的32 bit进行一系列的加密变换，在此轮迭代即将结束时，把左边的32 bit与右边得到的32 bit逐位模2相加，作为下一轮迭代时右边的段，并将原来右边未经变换的段直接送到左边的寄存器中作为下一轮迭代时左边的段。
在每一轮迭代时，右边的段要经过选择扩展运算E、密钥加密运算、选择压缩运算S、置换运算P和左右混合运算。

image乘积变换框图

选择扩展运算E：

将输入的32 bit Ri-1扩展成48 bit的输出，令s表示E原输入数据比特的原下标，则E的输出是将原下标s0或1(mod 4)的各比特重复一次得到的，即对原第1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29，32各位都重复一次,实现数据扩展。将表中数据按行读出得到48 bit输出。

image选择压缩运算S:

将前面送来的48 bit数据自左至右分成8组，每组为6 bit。而后并行送入8个S一盒，每个S盒为一非线性代换网络，有4个输出。

imageS盒运算：

将前面送来的48比特数据从左至右分成8组，每组为6比特，然后并行送入8个S盒。8个S盒的工作原理都是一样，为一个非线性替换运算。每个S盒都是一个4行、16列的矩阵，每行都是0到15的数字，但每行的数字排列都不同。每个S盒有6位输入，4位输出，6位输入中的第1位和第6位数字组成的二进制数值决定置换矩阵的行数，其余4位数字所组成的二进制数值决定置换矩阵的列数，行数和列数交点的数字便是S盒的输出。

image

例：假设S1盒的输入110010, 因第1位和第6位数字组成的二进制数为10=(2)10，他对应S1行号为2的那一行，其余4位数字所组成的二进制数为1001=(9)10，对应S1列号为9的那一列，交点处的数是12，则S1的输出为1100。S盒的置换矩阵如上表所示。

置换运算P:

对S1至S8盒输出的32 bit数据进行坐标置换，置换P输出的32 bit数据与左边32 bit即Ri-1逐位模2相加，所得到的32 bit作为下一轮迭代用的右边的数字段。并将Ri-1并行送到左边的寄存器，作为下一轮迭代用的左边的数字段。

image子密钥的生产：

DES的乘积变换部分含有16轮非线性变换，每一轮变换都用一个48比特的子密钥，共需16个不同的48比特的子密钥。
一个64比特的外部密钥经过密钥产生器产生48比特的16个子密钥。

image置换1的作用是将56比特密钥K’各位上的数按规定方式进行换位。置换后的56比特分别存到两个28比特的寄存器中。

图片1

C0的各位依次为原密钥中的57,49,41,…,36位，D0的各位依次为原密钥中的63,55,…,4位。

循环左移寄存器：

每个循环左移寄存器都有28比特，加密时，循环寄存器对 C i+1 、D i+1的内容是将循环寄存器对Ci、 Di的内容分别左移1至2位得到的。各级寄存器移位的比特数如表所示。

image压缩置换：

是从56位内容中选出48位，产生16轮加密的16子密钥。压缩置换表如表：

image压缩置换表中的数字表示循环寄存器对(Ci、Di)的比特序号，他的读取顺序是从左到右，从上到下，即Ci的第14,17,11,…位分别置换成 Ki的第1,2,3,…位。

理论讲完了下面上代码：

main.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "des.h"
#include <iostream>
using namespace std;

void main(){
    char key[9] = {"program."};           //密钥
    char mw[9] = {"12345678"};            //明文
    cout<<"明文:"<<mw<<endl;
    cout<<"密钥:"<<key<<endl;
    DES des(key);
    des.encrypt(mw,mw);
    cout<<"加密后："<<mw<<endl;
    des.decrypt(mw,mw);
    cout<<"解密后："<<mw<<endl;
}

des.h

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
class DES{
public:
    DES(char key[8]);
    void encrypt(char in[8],char out[8]);                               //加密
    void decrypt(char in[8],char out[8]);                               //解密
protected:
    void crypt(char out[8],char in[8],bool type=en);                    //加密解密通用函数
private:
    enum  {en,de};

    void leftloop(bool * in,int len, int loop);                         //循环左移

    void bittobyte(char *out,const bool *in,int bitlen);                //bit转换成byte

    void bytetobit(bool *out,const char *in,int bitlen);                //byte转换成bit
   
    void xor(bool *ina,const bool *inb,int len);                        //异或操作
   
    void transt(bool *out,const bool *in,const int *table,int len);     //置换
   
    void initkey(const char key[8]);                                    //初始化密钥数组

    void f_func(bool in[32],const bool subkey[48]);                     //密码处理F函数

    void s_func(bool out[32],const bool in[48]);                        //S盒密码转换

    static bool subkey[16][48];                                         //16圈子密钥
   
    const static int IP_TABLE[64];                                      //置换IP表
   
    const static int IPR_TABLE[64];                                     //逆置换IP-1表

    const static int E_TABLE[48];                                       //E 位选择表

    const static int P_TABLE[32];                                       //P换位表

    const static int PC1_TABLE[56];                                     //pc1选位表

    const static int PC2_TABLE[48];                                     //pc2选位表

    const static int LOOP_TABLE[16];                                    //左移位数表
   
    const static char S_BOX[8][4][16];                                   //S盒
};

des.cpp

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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
#include "des.h"
#include <memory.h>

const int DES::IP_TABLE[] = {
    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
};
const int DES::IPR_TABLE[] = {
    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
};
const int DES::E_TABLE[] = {
    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
};
const int DES::P_TABLE[] = {
    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
};
const int DES::PC1_TABLE[] = {
    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
};
const int DES::PC2_TABLE[] = {
    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
};
const int DES::LOOP_TABLE[] = {
    1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1
};
const char DES::S_BOX[8][4][16] = {
    //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
};

bool DES::subkey[16][48] = {0};

//--------------byte转换bit---------------
void DES::bytetobit(bool *out,const char *in, int bitlen){
    for(int i = 0; i < bitlen; i++){
        out[i] = in[i/8]>>(i%8) & 0x1;
    }
}

//--------------bite转换byte---------------
void DES::bittobyte(char *out,const bool *in,int bitlen){
    memset(out,0,(bitlen+7)/8);
    for(int i = 0; i < bitlen; i++){
        out[i/8] |= in[i]<<(i%8);
    }
}

//--------------异或操作---------------
void DES::xor(bool *ina,const bool *inb,int len){
    for(int i=0;i<len;i++){
        ina[i]^=inb[i];
    }          
}

//--------------表置换---------------
void DES::transt(bool *out,const bool *in,const int *table,int len){
    static bool temp[256];
    for(int i = 0; i < len; i++){
        temp[i] = in[table[i]-1];
    }
    memcpy(out,temp,len);
}

//--------------循环左移---------------
void DES::leftloop(bool * in,int len, int loop){
    static bool temp[256];
    memcpy(temp,in,loop);
    memcpy(in,in+loop,len-loop);
    memcpy(in+len-loop,temp,loop);
}

//--------------密钥初始化---------------
void DES::initkey(const char key[8]){
    static bool kbit[64],*kl=&kbit[0],*kr=&kbit[28];
    //byte转二进制
    bytetobit(kbit,key,64);
    transt(kbit,kbit,PC1_TABLE,56);
    for(int i = 0; i < 16; i ++){
        leftloop(kl,28,LOOP_TABLE[i]);
        leftloop(kr,28,LOOP_TABLE[i]);
        transt(subkey[i],kbit,PC2_TABLE,48);
    }
}

//--------------密码处理F函数---------------
void DES::f_func(bool in[32],const bool subkey[48]){
    static bool mr[48];
    transt(mr,in,E_TABLE,48);
    xor(mr,subkey,48);
    s_func(in,mr);
    transt(in,in,P_TABLE,32);
}

//--------------S盒变换---------------
void DES::s_func(bool out[32],const bool in[48]){
    for(int i = 0,j,k;i<8;i++,in+=6,out+=4){
        j = (in[0]<<1)+in[5];
        k = (in[1]<<3)+(in[2]<<2)+(in[3]<<1)+in[4];
        bytetobit(out,&S_BOX[i][j][k],4);
    }
}

//--------------加密解密处理---------------
void DES::crypt(char out[8],char in[8],bool type/* =en */){
    static bool obit[64],temp[32],*li=&obit[0],*ri=&obit[32];
    bytetobit(obit,in,64);
    //初始置换IP
    transt(obit,obit,IP_TABLE,64);
    //16轮迭代
    if(type==en){
        for(int i = 0;i < 16; i++){
            memcpy(temp,ri,32);
            f_func(ri,subkey[i]);
            xor(ri,li,32);
            memcpy(li,temp,32);
        }
    }else{
        for(int i = 15; i>= 0; i--){
            memcpy(temp,li,32);
            f_func(li,subkey[i]);
            xor(li,ri,32);
            memcpy(ri,temp,32);
        }
    }
    //逆初始置换IP
    transt(obit,obit,IPR_TABLE,64);
    bittobyte(out,obit,64);
}

//--------------加密---------------
void DES::encrypt(char in[8],char out[8]){
    crypt(out,in,en);
}

//--------------解密---------------
void DES::decrypt(char in[8],char out[8]){
    crypt(out,in,de);
}

//构造函数，进行密钥初始化
DES::DES(char key[8]){
    initkey(key);
}

运行效果图：

image

本文链接：http://www.alonemonkey.com/data-encryption-standard.html