DES算法详解

发表于 | 分类于

基本概念

对称加密

对称加密指的是在加密和解密过程中都使用同一个秘钥，相对于非对称加密(加解密使用不同的秘钥)，加解密速度更快。

分组加密

由于DES等算法的秘钥长度是定长的，并且单次加解密的明文(密文)只能等于秘钥长度，因此会对明文(密文)先做分块处理，然后逐块加解密。具体的分组加密实现中，不一定会对每个组采用相同的秘钥，细节详见后文。

安全原则：混乱与扩散

混乱：使得密文与其对应的明文和密钥的关系足够复杂， 以致于密码分析者无法利用这种关系。

扩散：使得每个明文比特和密钥比特影响尽可能多的密文比特， 以隐藏明文的统计特性和结构规律。

DES在具体实现中的每一步都是按照这两个原则实现的，以尽最大可能达到安全性。

费斯妥（Feistel）密码

是用于分组加密实现中的迭代步骤，特点是加解密操作非常相似，易于基于硬件操作实现。具体流程图见后文。

DES

数据加密标准（英语：Data Encryption Standard，缩写为 DES）是一种对称密钥加密块密码算法，1976年被美国联邦政府的国家标准局确定为联邦资料处理标准（FIPS），随后在国际上广泛流传开来。它基于使用56位密钥的对称算法。DES现在已经不是一种安全的加密方法。

整体加解密流程

下图是一个分组明文加密的整体流程：

图片注解

m1m2…m64表示一个分组的明文。

初始置换指的是对明文根据一定规律做乱序操作，打乱明文序列。

Round指的是执行一轮Feistel操作。其中的L代表输入的左半边(32字节)，R代表右半边(32字节)，f表示轮函数，K代表子秘钥，该秘钥由加密密钥生成。

逆初始置换指的是初始置换的逆变换。

c1c2…c64表示最终输出的密文。

加密过程中的基本参数配置

分组长度：64位

秘钥长度：64位，其中8位为奇偶校验位，真正用于加密的有效位数只有56位。

迭代轮数：16轮。实际上根据Feistel的设计是可以迭代任意轮次的，但是综合考虑性能与安全性，最终设定为16轮。

子秘钥长度：48位。

初始置换与逆初始置换

上图中的58表示将明文中的第58位放在现在的第一位，以此类推，50表示将明文中的第50位放在现在的第二位。

代码实现：

1
2
for i in range(0, 64):
	ip_text += plaintext[self.__ip[i] - 1]

逆初始置换的原理也是相同的，不再赘述。

这一步主要保证了混乱原则，使得最终明文与密文的关系更加复杂。

Feistel

一轮Feistel操作

Feistel操作是DES加密中最重要的一环，直接决定了加密强度。

该过程用数学公式直观的表示一轮操作的话，如下

其中需要注意的是1-15轮L和R的位置会交换，也就是上一轮产生的L会作为下一轮的R。但是最后一轮的L和R的位置是不会做交换的，因此最后一轮的公式应该为

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
left = ip_text[0:32]
right = ip_text[32:64]
for round_index in range(0, self.__round):
    subkey = self.__private_subkey(round_index)
    key = self.__private_f(right, subkey)
    if (round_index < self.__round - 1):
        temp = right
        right = self.__private_xor(left, key)
        left = temp
    else: # 最后一轮左右不交换
        left = self.__private_xor(left, key)
mergetext = left + right
子密钥生成算法

上述公式中用到的16个K就是子秘钥，子秘钥通过特定的算法生成，并作为f函数的输入，最终生成的输出将与待加密的数据直接做异或运算。

具体的算法描述这里不再赘述，参考文章 对称加密算法 DES 子密钥（subkey）的生成算法

代码实现：

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
# 左移位数
shift = 0
# round代表当前轮次，从0开始
for i in range(0, round + 1):
    # self.__d 为子秘钥移位表
	shift = shift + self.__d[i]

    # self.__pc1为子秘钥置换选择1
    left_shift = ""
    for i in range(shift, 28):
        left_shift += str(self.__key[self.__pc1[i] - 1])
    for i in range(0, shift):
        left_shift += str(self.__key[self.__pc1[i] - 1])

    right_shift = ""
    for i in range(28 + shift, 56):
        right_shift += str(self.__key[self.__pc1[i] - 1])
    for i in range(28, 28 + shift):
        right_shift += str(self.__key[self.__pc1[i] - 1])

    left_and_right = left_shift + right_shift

    # self.__pc2为子秘钥置换选择2
    sub_key = ""
    for i in range(0, 48):
        sub_key += left_and_right[self.__pc2[i] - 1]
f函数
  • f函数的作用是以明文(密文)的右半部分以及子密钥生成与最终左半部分进行异或操作的字符串。用数学公式表示为：
  • f函数的主要过程包括，通过E盒扩展将32位的右半部分R扩展为48位，然后与28位的子密钥取异或，再使用S盒替代将48位的异或结果再缩减到32位，最终根据P盒进行置换运算。具体过程如下图

  • 1代表E盒扩展：将输入的32位比特数据扩展为48位
  • 2代表S盒替换：将输入的48位比特数据压缩为32位
  • 3代表P盒置换：对32位比特数据进行位置移动的操作
  • 代码实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# E盒扩展
e_right = ""
for i in range(0, 8):
    e_right += (right[4 * i - 1 if i > 0 else 31]
    + right[4 * i:4 * (i + 1)]
    + right[4 * (i + 1) if i < 7 else 0])

# 与subkey取异或
xor_key = self.__private_xor(e_right, subkey)

# S盒替代
s_key = ""
for i in range(0, 8):
    col = int(xor_key[6 * i + 1: 6 * (i + 1) - 1], 2)
    row = int(xor_key[6 * i] + xor_key[6 * (i + 1) - 1], 2)
    s_key += self.__private_int2bin((self.__s[i])[row][col], 4)

# P盒置换
p_key = ""
for i in range(0, 32):
    p_key += str(s_key[self.__p[i] - 1])

分组密码的模式

上述的过程是一组明文通过DES加密的过程，而不同的分组模式算法则决定了各组如何迭代加密的细节。

ECB模式

  • 在该模式下，将明文分组加密后的结果直接保存为密文分组。当最后一个明文的分组的内容小于分组的长度时，需要用指定的数据进行填充。

  • 加密过程：

  • 缺点：如果攻击者拦截到了密文通信过程，则可以通过交换密文的顺序来改变原本要传达的意思。比如原来的明文可能是A Attack B,如果这三个关键元素刚好是在不同分组中被独立加密的，则可以通过改变密文顺序将明文改为B Attack A。关键的问题在于明文与密文存在唯一的映射关系，与明文在文本中所处的位置无关。

CBC模式

  • CBC模式将前一个密文分组与当前明文分组的内容混合起来进行加密，这样就使得明文分组的加密结果与其所处的位置相关，保证同一明文分组的输出结果不一定每次都相同，避免了ECB的缺点。

  • 加密过程：

    image-20180505211452091

  • 初始化向量IV：由于第一个分组未加密的时候，没有密文分组可以与其加密，所以需要自己定义一个初始化向量和明文做异或运算。该向量最好使用随机数生成。

  • padding填充：因为加密过程要求输入的数据块长度固定，因此如果最后一个明文分组不足数据块长度，则需要补足，补足的常用算法为PKCS#5，即最后一块明文缺少N个字节，就用N这个数填充到完整的块。

  • 缺点：由于在明文分组与密文分组的映射关系中引入了前一个密文分组，所以如果有一个密文分组的信息出现损坏，则会导致与之直接相关的两个明文分组都无法解密。

    同时由于在解密的最后一步，会将解密结果和初始化向量做异或运算然后得到最终的明文分组，因此如果攻击者可以通过反转IV的比特值，使得第一个明文分组的对应比特位也反转。之所以这样的攻击能奏效是因为IV的每一位与明文的每一位是一一对应的，如果用这种方式去修改密文来攻击明文则是做不到的，因为加密过程做了大量混淆操作，导致修改一个密文会引发多个明文的改变。

    会被Padding Oracle攻击。细节参考Padding Oracle攻击实例分析

CFB模式

相比于CBC模式，它的明文分组不需要经过加密算法加密，因此也就不需要使用padding。具体过程如下：

image-20180507223256845

OFB模式

类似于CFB模式，明文都不通过加密算法加密，但是区别是CFB的密文会通过加密算法加密，而CFB则是将IV加密后的结果反复加密得到中间产物，再与明文异或，具体过程如下：

image-20180507223911361

通过对比CBC与OFB还可以发现，有一个最大的不同，即OFB密钥流的产生与密文分组的生成无关，因此可以提前生成各个密钥，然后对明文进行加密。而CBC由于中间密钥的生成依赖于上一个密文分组，因此不能做到提前生成密钥。

CTR模式

CTR模式是一种通过将逐次累加的计数器进行加密来生成密钥流的流密码，在CTR模式中，每个分组对应一个逐次累加的计数器，并通过对计数器进行加密来生成密钥流。最终的密文分组是通过将计数器加密得到的比特序列与明文分组进行XOR而得到的，如下图所示：

image-20180507224704430

可以发现CTR模式最大的优势在于可以并行的进行加密操作，每个分组的加密过程都是独立的。

其他

  • 算法实现中一些参数的选定，如轮函数轮次是16轮，密钥长度是56位等，都是经过实践，在保证加密安全性的前提下，考虑到加密性能的最大化，选定的最合适的参数。
  • 算法实现中的一些常量，如S盒、P盒等，也都是设计者经过测试，选用的安全性最高的实现，因此没有必要再自己去另外设计S盒等。
  • DES算法目前已经不再安全，推荐使用AES系列算法。
  • 上述的分组密码的模式不仅仅可以用在DES上，也可以用在其他分组加密算法中，如AES。
  • 其他分块加密技术：Block Cipher Techniques

参考资料

图解密码技术

对称加密算法 DES 子密钥（subkey）的生成算法

【国家级精品课】——密码学（ 解放军信息工程大学）(11)

Padding Oracle攻击实例分析