DES概述

DES(Data Encryption Standard)是一种对称密钥的分组加密算法.

DES使用同一个长为64位(实际只有56位)的密钥进行加密和解密.

其分组为64位(8个字节),如果加密的数据不是64位的倍数,则按照某种规则进行填充.

到目前为止,DES已经不是一种安全的加密方法,主要因为它使用的56位密钥过短,现在已经逐渐被AES所取代.


DES算法将明文进行一系列的排列和替换来实现加密,关键过程为使用原始密钥来生成16个密钥,然后分别使用这16个密钥对数据依次进行一系列的位操作,一共进行16次,最终得到密文.解密相同,只不过反向(密钥使用顺序颠倒)进行操作.

DES加密流程

加密流程图(来自维基百科):

image-20231213152749279

在核心加密之前需要执行一个密钥调度,即根据原始密钥生成16个48位的子密钥用于后续操作.

开始加密之前,先对明文进行一次置换,其中IP和FP为一对互逆的置换,即FP为IP的反函数.IP用于将明文Plaintext先进行一次换位处理,打乱原来的顺序,得到一个乱序的明文组,然后再进行核心的加密.

将64位明文组分成2部分,各为32位,并被交叉地分别处理,这种交叉结构被称为费斯妥结构,其保证了加密和解密过程足够相似,有利于电路/代码的实现.

接着就是F函数,这个函数即为DES的核心,使用生成好的48位子密钥对32位的数据进行操作,完成1次加密操作,一共有16次.

初始置换IP

IP根据一个IP置换表进行换位:

image-20231213011719278

也就是说,原来的64位明文为M0,置换后的明文为M1,

将M0的第58位换到M1的第1位,M0的第50位换到M1的第2位……以此类推.

置换完成后,将M1前后分成2块L0和R0,各为32位.

密钥调度

密钥调度即子密钥的生成.

DES根据初始的64位密钥来生成16个不同的子密钥,原来64位中有56位是有效位,其余8位(根据PC-1置换表)被用于奇偶校验,并最后被舍弃.

密钥调度流程图(来自维基百科):

image-20231213152722041

PC-1置换选取56位块

首先将64位原始密钥使用PC-1置换表进行换位,并分成2组,该表只指定了56位,剩下的第8,16,24,32,40,48,56,64位共8位被舍弃.

1
2
3
4
5
6
7
8
9
10
11
12
13
// PC-1置换表,因为无图所以用代码表示了
int pc1_l[28] = {
    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
};
int pc1_r[28] = {
    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
};

这样就将64位原始密钥拆分成了2个28位的部分C0和D0.

生成16个块Ci,Di(i=1-16)

接下来根据公式

Cn=rotate(C0,r[n])Dn=rotate(D0,r[n])C_n=rotate(C_0,r[n])\\ D_n=rotate(D_0,r[n])

进行循环左旋生成16个块Ci,Di(每个块都有一对Ci和Di)

其中左旋位数由r[]指定,r[]固定如下:

1
2
// 第0位无意义
int r[17]={-1,1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};

例如有

1
2
3
4
5
6
7
C0：1111000011001100101010101111
D0：0101010101100110011110001111

生成C1时,n=1,则r[1]==1,循环左移1位得:

C1：1110000110011001010101011111
D1：1010101011001100111100011110

生成16个子密钥K

然后根据公式

Kn=PC2(CnDn)K_n = PC_2(C_nD_n)

进行Ki(i=1->16)的生成,CnDn代表将Cn和Dn连接在一起.

其中PC2代表使用PC-2置换表进行换位,从CiDi中选取48位作为最终的密钥Ki.

1
2
3
4
5
6
7
8
9
10
11
// PC-2置换表,因为无图所以用代码表示了
int pc2[48] = {
            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
};

最终生成的16个48位比特串(块)Ki(i=1-16)即为16个子密钥,用于后续的加密.

轮函数加密

流程仍然是这个图:

说白了就是在每一轮中将2块数据交替地进行F()处理,然后将处理后的值与本轮中另一个块进行异或.

F函数

img

F函数将一个32bit的(半)块进行一次E置换,置换时进行了扩张,生成48bit的块,然后与48位的子密钥K进行异或,得到的48bit的结果再分成8组,每组为6bit,经过S盒,每组生成4bit的结果,组合起来一共为4*8==32bit的结果,然后再进行一次P置换,即为F函数的最终结果.

最终的结果仍然为32bit,与输入的32bit块大小一样,准备用于下一步加密.

E置换

image-20231213160234680

通过该表进行32bit -> 48bit的扩张.

异或

即将E置换后的48位扩张结果与子密钥K进行异或.

S盒代换

将异或结果分成6bit一组,共8组.经过S盒后,6位变为4位.

S盒代换有8个盒子(S-Box),分别对应8个组,通过查找表进行代换.

图片来源于这篇文章:

img img

每一组查找到的数转为4位二进制数即为输出的4bit结果.

P置换

P为固定置换,将经过S盒变换得到的32bit进行一个置换操作.

需要注意一点:这个P置换是精心设计的,使得这一轮同一个S盒输出的四个bit,在下一回合的扩张之后,交由四个不同的S盒去处理.

1
2
3
4
5
6
7
8
9
10
11
// P置换表,因为无图所以用代码表示了
int P[32]={
    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
};

反函数置换FP

FP和IP为反函数关系,轮函数后再进行一次FP置换得到最终结果.

image-20231213162039600

IP逆即为FP.


至此,即为整个加密,可以发现,使用同一个子密钥对一段数据进行两次轮函数(?)处理,得到的结果不变,这就体现出DES的加解密几乎一致.

DES解密

只需要将生成的16个子密钥逆转即可,即

1
reverse_keys(SubKeys,16); // 自定义的函数,将16个子密钥反序