密码学之DES算法
《现代密码学基础》又在讲解经典DES
算法了,我打算用 C++ 写了一个。本文介绍了 DES
算法加密的大致步骤和整体流程。
一、DES 算法介绍
1.介绍
DES 算法为密码体制中的对称密码体制,⼜被称为美国数据加密标准。DES 是⼀个分组加密算法,典型的DES
以64
位为分组对数据加密,加密和解密⽤的是同⼀个算法。
DES 使用 56 位的密钥和 64 位的明文块进行加密。DES 算法的分组大小是 64 位,因此,如果需要加密的明文长度不足 64 位,需要进行填充;如果明文长度超过 64 位,则需要使用分组模式进行分组加密。
2.流程
-
1.初始置换(IP 置换):将输入的 64 位明文块进行置换和重新排列,生成新的 64 位数据块。
-
2.加密轮次:DES 加密算法共有 16 个轮次,每个轮次都包括四个步骤:
-
2.1. 将 64 位数据块分为左右两个 32 位块。
-
2.2. 右侧 32 位块作为输入,经过扩展、异或、置换等操作生成一个 48 位的数据块。这个 48 位的数据块被称为“轮密钥”,它是根据加密算法的主密钥生成的子密钥。
-
2.3. 将左侧 32 位块和轮密钥进行异或运算,结果作为新的右侧 32 位块。
-
2.4. 将右侧 32 位块与原来的左侧 32 位块进行连接,生成一个新的 64 位数据块,作为下一轮的输入。
-
-
3.末置换(FP 置换):在最后一个轮次完成后,将经过加密的数据块进行置换和重新排列,得到加密后的 64 位密文。
-
4.逆置换:在经过 16 轮次计算后,DES 会对最后的结果进行最后一次置换。即为最后的输出结果
总的来说,DES 加密的过程就是通过一系列置换、异或、扩展等运算,将明文分成若干个小块,然后根据主密钥生成一系列的轮密钥,利用轮密钥对每个小块进行加密,最终将加密结果重新组合成一个整体,得到密文。
二、DES 算法详解
注意这里的 DES 用的许多函数都是固定的,公开的函数(因此并没有密码含义),即已知条件,没有密码含义,下面会加粗提心!!!
1.初始置换(Initial Permutation,IP 置换)
IP 置换是将输入的 64 位明文块进行置换和重新排列,生成新的 64 位数据块。
目的:增加加密的混乱程度,使明文中的每一位都能够对后面的加密过程产生影响,提高加密强度。
我们将把 64 位的顺序按下表中规定的顺序放置,图中的数字是在 64 位明文中每个比特的索引位置。注意,在 DES 中,这个置放规则是固定的。
1 | // 初始置换 |
即将原来位于第 58 个位置的数据放在第 1 个位置,原来位于第 50 个位置的元素放在第 2 个位置,第 42 个放在第 3 个,34->4 以此类推…
初始置换的逆置换(Final Permutation,FP 置换)是将加密后的数据块进行置换和重新排列,得到最终的加密结果,与初始置换相对应。
1 | // 逆置换表 |
2.加密轮次
初始置换完成后,明文被划分成了相同长度(32 位)的左右两部分,记作 L0,R0。接下来就会进行 16 个轮次的加密了。
我们从单独一个轮次来看。首先把目光聚焦在 R0 这里。
右半部分 R0 会作为下一轮次的左半部分 L1 的输入。以此类推,重复 16 轮运算。所以,上面描述的过程可以用以下公式表述。
因为 R0 只有 32 位,R0 会补位到 48 位和本轮次生成的 48 位 K0(马上讲 K0 的生成)输入到 F 轮函数中去。F 函数的输出结果为 32 位,结果 F(R0,K0)会和 L0 进行异或运算作为下一轮次右半部分 R1 的输入。
$$
R_i = F_i(R_{i-1}) ⊕ L_{i-1}
$$
$$
L_i = R_{i-1}
$$
3.f 函数详细过程(R0)
密码函数 f(R, K)接受两个输入:32 位的数据和 48 位的子密钥。然后:
-
通过表 E 进行扩展置换,将输入的 32 位数据扩展为 48 位;
-
将扩展后的 48 位数据与 48 位的子密钥(ki)进行异或运算;
-
将异或得到的 48 位数据分成 8 个 6 位的块,每一个块通过对应的一个 S 表产生一个 4 位的输出。其中,每个 S 表都是 4 行 16 列。具体的置换过程如下:把 6 位输入中的第 1 位和第 6 位取出来行成一个两位的二进制数 x ,作为 Si 表中的行数(0~3);把 6 位输入的中间 4 位构成另外一个二进制数 y,作为 Si 表的列数(0~15);查出 Si 表中 x 行 y 列所对应的整数,将该整数转换为一个 4 位的二进制数。
-
把通过 S 表置换得到的 8 个 4 位连在一起,形成一个 32 位的数据。然后将该 32 位数据通过表 P 进行置换(称为 P-置换),置换后得到一个仍然是 32 位的结果数据,这就是 f(R, K)函数的输出。
3.1 拓展 R 到 48 位
将 32 位的 R0 右半部分进行扩展,得到一个 48 位的数据块。同样的,数据拓展也是根据一个固定的置换表。红框中就是我们要补位的数据。
由此可见,扩展过程的每一位都是根据上述的置换表从输入的 32 位数据块中提取出来的。原始数据的第 32 位被补充到了新增列的第一个,第 5 位被补充到了第二个新增列的第一个,以此类推…
1 | // 扩展置换表,将 32位 扩展至 48位 |
3.2 子密钥 K 的生成
DES 算法采用了每轮子密钥生成的方式来增加密钥的复杂性和安全性。每轮子密钥都是由主密钥(64 位)通过密钥调度算法(Key Schedule Algorithm)生成的。DES 算法的密钥调度算法可以将 64 位的主密钥分成 16 个子密钥,每个子密钥 48 位,用于每轮加密中与输入数据进行异或运算。
通过子密钥生成的流程图来看下整个过程。
- 1、将 64 位主密钥经过置换选择 1(Permuted Choice 1 简写为 PC-1)后输出了 56 位,将其分为左右两个 28 位的数据块,分别记为 C0 和 D0。同上面我们讲过的置换规则一样,PC-1 置换函数也是一个固定的置换表,即下图左上角
从 PC-1 的置换表中可以看到,舍弃掉的 8 位数据是原始数据中每 8 位数据的最后一位,也就是我们所熟知的奇偶检验位。这 8 位被丢弃是因为它们对于密钥的安全性没有贡献,而且能够使 DES 算法的计算速度更快。 - 2、对 C0 和 D0 进行循环左移操作。循环左移完成后生成 C1 和 D1。因此,在 16 个轮次的计算当中会得到 16 个 32 位的数据块 C1-C16 和 D1-D16。在 DES 中循环左移也有固定的规则。
对于 Ci 和 Di,若 i 为 1,2,9 或 16,则循环左移一位,否则循环左移两位。
-
3、 对于 C1,D1,将它们经过置换选择 2(Permuted Choice 2 简写位 PC-2)后,得到 48 位的子密钥 K1,用于每轮加密中与输入数据进行异或运算。PC-2 置换的输入是由 PC-1 置换生成的 56 位的密钥,而它的输出是 48 位的子密钥。PC-2 置换将 56 位的密钥重新排列,丢弃了 8 位并选取了其中的 48 位作为子密钥。PC-2 的置换规则如下:
即 PC-2 置换表的第一行表示选择了输入密钥中的第 14、17、11、24、1 和 5 位,并将它们作为输出子密钥的前 6 位。以此类推 -
4、至此,经过 PC-2 后的结果就是我们当前轮次的子密钥 K1 了。在整个 DES 加密过程中会生成 16 个 48 位子密钥 K1-K16,分别用于 DES 算法中的 16 轮加密过程,从而保证每轮加密所使用的密钥都是不同的,增加了破解的难度。
1 | // 密钥置换表,将64位密钥变成56位 |
3.3 当前轮次的子密钥与拓展的 48 位 R 进行异或运算
当前轮次的子密钥 Ki 与拓展的 48 位 Ri 进行异或运算。运算结果会作为接下来 S 盒替换的输入
3.4 S 盒替换(Substitution Box substitution)
S 盒替换(Substitution Box substitution)是一种在密码学中广泛使用的加密技术。它是将明文中的一组比特映射到密文中的一组比特的过程,用于增强密码的安全性。DES 中 S 盒替换用于将上一轮异或运算的 48 位结果映射到 32 位输出中去。
同样的,S 盒也是一种置换表。在 DES 的每一轮计算中 S 盒都是不一样的。这里我以第一轮计算中的 S 盒为例。从上图中我们看到,S 盒内部有 8 个 S 块,记作 S1-S8。每个 S 块都会接收 6 位字符作为输入并输出四位字符。这里我们以第一个 S 盒 S1 为例。他是一个 4*16 的置换表。
例如输入101010
到S1
中。S1
会将这六位的第一位和第六位拿出来10
作为S1
的行,中间四位0101
拿出来作为S1
的列。我们转换成十进制,此时映射到这个 S 盒的位置就是(2,5)
对应 S 盒的第3
行第6
列(索引都从0
开始数)。
所以这个输入的结果是 6,将 6 转化为二进制 110,S 盒的输出是 4 位,所以得S(101010)
=0110
因此,可以看到 S 盒其实是一种非线性的加密技术,它能够抵御许多传统的密码分析攻击,如差分攻击和线性攻击。
3.5 P 盒替换
P 盒替换将 S 盒替换的 32 位输出作为输入,经过上述固定的替换表进行替换后即为最后 F 轮函数的结果。
该结果 F(R0,K0)与 L0 进行异或运算得到下一轮的右半部分 R1
1 | // S盒,每个S盒是4x16的置换表,6位 -> 4位 |
4 逆置换(Inverse Permutation)
合并 L16 和 R16 得到一个 64 位的数据,再经过尾置换后得到的就是 64 位的密文。注意:要将 L16 和 R16 合并成 R16L16(即左右互换)。尾置换表 IP-1 如下:
1 | // 尾置换表 |
三、C++代码实现
1、加密
1 |
|
2.解密
那么,在对 64 位的数据加解密成功以后,对文件的加解密就很简单了!只需要每次读 64 位,加密以后,将 64 位的密文写入另外一个文件……如此循环,直到文件尾。下面是对一张图片进行加密和解密的测试代码:
1 | int main() { |
加强版:
1 |
|
四、总结
5、DES 的优缺点
优点:
安全性高:DES 算法使用密钥进行加密和解密,相同的明文使用不同的密钥加密后得到的密文是不同的。密钥越长,加密的安全性就越高。
算法简单:DES 算法的加密和解密过程非简单,基于对称加密,使用相同的 key 进行加解密。
适用广泛:DES 算法是最早也是最广泛使用的加密算法之一,被广泛应用于电子商务、电子邮件、虚拟私人网络等领域,具有广泛的适用性和可移植性。
缺点:
密钥长度较短:DES 算法使用 56 位密钥,虽然在当时足够安全,但在当前计算机的处理能力下,已经不足以保证加密的安全性,易受到暴力破解攻击。
无法抵抗差分密码分析攻击:DES 算法无法抵抗差分密码分析攻击,这种攻击可以通过比较相同明文的密文,分析加密算法的行为并推断出密钥。
比较慢:由于 DES 算法是一种分组密码算法,需要对 64 位的明文进行加密,加密速度比较慢,不适用于对大量数据进行实时加密和解密。