DES加密算法 | 安全沉思录

type

status

date

slug

summary

参数

Key: 8 个字节共 64 位的工作密钥 Data：8 个字节共 64 位的需要被加密或者被解密的数据 Mode：DES 工作方式，加密或者解密 (CBC 模式和 ECB 模式)

算法描述

(1)输入 64 位明文数据，并进行初始置换 IP；

(2)在初始置换 IP 后，明文数据再被分为左右两部分，每部分 32 位，以 L0，R0 表示；

(3)在秘钥的控制下，经过 16 轮运算 (f)；（包括子密钥生成、扩展置换、s 盒代换、p 盒代换）

(4)16 轮后，左、右两部分交换，并连接再一起，再进行逆置换；

(5) 输出 64 位密文。

算法演示

1.0初始置换

DES 算法使用 64 位的密钥 key 将 64 位的明文输入块变成 64 位的密文输出块，并将输出块分为 L0 和 R0 两部分，每部分均为 32 位。

初始置换规则如下：这里是初始化的数据后经过置换转换后的数据所在的位置

意思就是说将输入的 64 位明文的第 1 位置换到第 40 位置，第 2 位置换到第 8 位置，第 3 位置换到第 48 位置。

以此类推，最后一位是原来的第 7 位置。

其实最后我们可以发现，置换完的数据位置看成是 2 组 2 维等差数列，其中横向递减 8，纵向递增 2 排列，这个置换的规则是规定的，

L0 表示置换后的数据的前 32 位 R0 表示置换后数据的后 32 位

2.0加密处理-迭代过程

这一步在初始置换后，进行 16 位网关相同的运算，在运算过程中与数据与密钥结合

运算过程是什么呢？

可以看一下上面的算法描述，主要是通过 f 函数运算

在函数 f 输出经过一个异或运算

和左半部分结合形成新的右半部分，原来的右半部分变成新的左半部分。用公式表示如下：

Ln = R (n - 1)；

Rn = L (n - 1)^f (Rn-1, kn-1)

2.1 函数 f

函数 f 由四步运算构成：

密钥置换 (Kn 的生成，n=0-16)；

扩展置换

S-盒代替

P-盒置换

2.1.1密钥置换–子密钥生成

DES 算法由 64 位密钥产生 16 轮的 48 位子秘钥。在每一轮的迭代过程中，使用不用的子秘钥。(如何产生？)

a、把密钥的奇偶校验位忽略不参与计算，即每个字节的第八位，将 64 位密钥降至 56 位，然后根据选择置换 PC-1 将这 56 位分为两块 C0 (28 位) 和 D0 (28 位)

b、将 C0 和 D0 进行循环左移变化 (注: 每轮循环左移的位数由轮数决定)，变换后生成 C1 和 D1，然后 C1 和 D1 合并，并通过选择置换 PC-2 生成子密钥 K1 (48 位)

c、C1 和 D1 在经过循环左移变换，生成 C2 和 D2，然后 C2 和 D2 合并，通过选择置换 PC-2 生成密钥 K2 (48 位)；

d、以此类推，得到 K16 (48 位)。但是最后一轮的左右两部分不交换，而是直接合并在一起 R16L16，作为逆置换的输入块。其中循环左移的位数一共是循环左移 16 次，其中第一次，第二次，第九次，第十六次是循环左移一位，其他都是左移 2 位。

2.1.2 密钥置换选择 1—-PC-1 (子秘钥的生成)

此时的操作对象是 64 位密钥 key

64 位密钥降至 56 位密钥不是说将每个字节的第八位删除，而是通过缩小选择换位表 1 (置换选择表 1) 的变换变成 56 位，如下：

注意 8, 16, 24, 32, 40, 48, 56, 64 处的数据都被剔除了，所以变成了 56 位。

再将 56 位的密钥分成 C0 和 D0

C0=K57K49K…... K36

D0=K63K55K…...K4

根据轮数将 Cn 和 Dn 分别循环左移 1 位或 2 位下面是移动的位数表:

第一轮是循环左移 1 位，C0 循环左移 1 位后得到 C1 如下：

D0 循环左移 1 位后得到 D1 如下：

C1 和 D1 合并之后，再经过置换选择表 2 生成 48 位的子秘钥 K1。

去掉第 9、18、22、25、35、38、43、54 位，从 56 位变成 48 位，再按新表的位置置换。

C1 和 D1 再次经过循环左移变换，生成 C2 和 D2，C2 和 D2 合并，通过 PC-2 生成子秘钥 K2。以此类推，得到子秘钥 K1~K16。需要注意其中循环左移的位数，根据轮数来定的。

2.1.2 扩展置换 E (E 位选择表)

通过扩展置换 E，数据的右半部分 Rn 从 32 位扩展到 48 位。扩展置换改变了位的次序，重复了某些位。

扩展置换的目的：

产生与密钥相同长度的数据以进行异或运算，R0 是 32 位，子秘钥是 48 位，所以 R0 要先进行扩展置换之后与子秘钥进行异或运算

提供更长的结果，使得在替代运算时能够进行压缩。

扩展置换 E 规则如下：

2.1.3 S-盒代替 (功能表 S 盒)

Rn 扩展置换之后与子秘钥 Kn 异或以后的结果作为输入块进行 S 盒代替运算功能是把 48 位数据变为 32 位数据代替运算由 8 个不同的代替盒 (S 盒) 完成。每个 S-盒有 6 位输入，4 位输出。所以 48 位的输入块被分成 8 个 6 位的分组，每一个分组对应一个 S-盒代替操作。经过 S-盒代替，形成 8 个 4 位分组结果。每个 S-盒是 4 行 16 列的格式，因为二进制 4 位是 0~15。8 个 S-盒的值如下：

S-盒计算过程

假设输入是 110011，将收尾合并作为行坐标，中间的作为纵坐标，得到 (11, 1001)，二进制转成 10 进制得到下标为 (3, 9)，得到数值 12，转成二进制：1100，因此一个 6 位的输入作为下标就会得到相应值 4 位的输出，以此类推。

2.1.4 P-盒置换

S-盒代替运算，每一盒得到 4 位，8 盒得到共 32 位输出。这 32 位的输出又作为 P 盒置换的输入块。

P 盒置换将每一位输入位映射到输出位。任何一位都不能被映射 2 次，也不能被略去。

经过了 P 盒置换的结果与最初 64 位分组的左半部分异或，然后左右两部分交换，开始下一轮迭代。

P-盒置换表 (表示数据的位置) 共 32 位

将 32 位的输入的第 16 位放在第一位，第七位放在第二位，第二十位放在第三位，以此类推，相当于换了位置。然后变成新的 32 位输出。

3.0 逆置换

将初始置换进行16次的迭代，即进行16层的加密变换，这个运算过程我们暂时称为函数f。得到L16和R16，将此作为输入块，进行逆置换得到最终的密文输出块。逆置换是初始置换的逆运算。从初始置换规则中可以看到，原始数据的第1位置换到了第40位，第2位置换到了第8位。则逆置换就是将第40位置换到第1位，第8位置换到第2位。以此类推，逆置换规则如下：

然后就可以得到最终的输出密文了

加密完毕然后我们回顾一下加密流程

4.0 DES 解密

加密和解密可以使用相同的算法。加密和解密唯一不同的是秘钥的次序是相反的。就是说如果每一轮的加密秘钥分别是 K1、K2、K3…K16 那么解密秘钥就是 K16、K15、K14…K1。每一轮产生秘钥的算法也是循环的。加密是秘钥循环左移，解密是秘钥循环右移。解密秘钥每次移动的位数是：0、1、2、2、2、2、2、2、1、2、2、2、2、2、2、1。