现代密码学——DES

本文整理了关于现代密码学入门之作——DES（数据加密标准）的一些相关资料。

DES的工作原理

DES（数据加密标准）是一种对称密钥加密算法，它的工作原理如下：

DES的总体结构：DES使用 Feistel 网络结构，总共有 16 轮迭代。每轮迭代都包含了置换、代换和异或等操作。
初始置换（IP）和逆初始置换（IP-1）：在DES加密的开始，64位的明文会经过一个初始置换IP，这个置换是固定的。然后在16轮迭代结束后，会进行逆初始置换IP-1，得到最终的密文。
F函数：F函数是DES中最重要的部分，它包括扩展置换、S盒代换和P盒置换三个步骤。扩展置换将32位的输入扩展到48位，然后与子密钥进行异或操作。S盒代换将48位的输入转换为32位的输出，这个过程包含了非线性变换。最后，P盒置换是一个简单的线性置换。
密钥调度算法：DES使用了一个56位的密钥，但是在每轮迭代中，都会生成一个48位的子密钥。这个过程被称为密钥调度。密钥调度包括了置换选择1（PC-1）、循环左移和置换选择2（PC-2）三个步骤。

DES算法中置换表的使用顺序如下：
PC-1置换：在密钥调度算法中，首先使用PC-1置换来选择56位的密钥材料。
PC-2置换：在密钥调度算法中，每轮迭代都会使用PC-2置换来生成48位的子密钥。
初始置换（IP）：在加密和解密过程的开始，使用初始置换来重新排列64位的输入。
扩展置换（E）：在每轮迭代中，使用扩展置换将32位的输入扩展到48位。
S盒：在每轮迭代中，使用S盒将48位的输入转换为32位的输出。
P盒置换（P）：在每轮迭代中，使用P盒置换来重新排列32位的输出。
逆初始置换（IP-1）：在加密和解密过程的结束，使用逆初始置换来得到最终的64位的输出。

DES中的数学基础

DES（数据加密标准）的数学基础主要包括以下几个部分：

置换和代换的数学原理：在DES中，置换和代换是两种基本的操作。置换是将输入的位重新排列，而代换是将输入的位进行非线性变换。这两种操作的组合可以提供混淆和扩散，这是现代密码学的两个基本原则。
S盒的设计和数学性质：S盒（Substitution-box）是DES中的核心部分，它提供了非线性变换。S盒的设计基于一些复杂的数学性质，例如在给定输入差分的情况下，输出差分的概率分布应该尽可能均匀。这可以防止差分密码分析等攻击。
轮函数和Feistel网络的数学性质：DES使用了Feistel网络结构，这是一种特殊的轮函数结构。在Feistel网络中，每一轮的输出可以表示为输入和子密钥的某种函数。这种结构的一个重要性质是，解密过程和加密过程几乎相同，只是子密钥的顺序相反。

DES的安全性分析

DES（数据加密标准）的安全性分析主要包括以下几个部分：

差分密码分析：差分密码分析是一种针对对称密钥加密算法的攻击方法，它基于输入和输出之间的差分分布。在DES中，由于S盒的设计，差分密码分析的效率并不高。
线性密码分析：线性密码分析是另一种针对对称密钥加密算法的攻击方法，它基于输入、输出和密钥之间的线性关系。在DES中，由于P盒和S盒的设计，线性密码分析的效率也并不高。
对DES的常见攻击：除了差分密码分析和线性密码分析，还有一些其他的攻击方法可以用于攻击DES，例如穷举攻击（暴力破解）。由于DES的密钥长度只有56位，所以穷举攻击是可行的。这也是为什么现在很少使用单DES，而更倾向于使用三重DES或AES。

DES的基本实现

DES加密算法的伪代码

function DES_Encrypt(plaintext, key):
    // 初始置换
    plaintext = initial_permutation(plaintext)
    
    // 密钥调度
    subkeys = key_schedule(key)
    
    // 16轮迭代
    for i from 1 to 16:
        left, right = split(plaintext)
        temp = right
        right = left xor f_function(right, subkeys[i])
        left = temp
        plaintext = join(left, right)
    
    // 逆初始置换
    ciphertext = inverse_initial_permutation(plaintext)
    
    return ciphertext

DES解密算法的伪代码

function DES_Decrypt(ciphertext, key):
    // 初始置换
    ciphertext = initial_permutation(ciphertext)
    
    // 密钥调度
    subkeys = key_schedule(key)
    
    // 16轮迭代（注意子密钥的顺序相反）
    for i from 16 down to 1:
        left, right = split(ciphertext)
        temp = right
        right = left xor f_function(right, subkeys[i])
        left = temp
        ciphertext = join(left, right)
    
    // 逆初始置换
    plaintext = inverse_initial_permutation(ciphertext)
    
    return plaintext

编程代码实现

这里主要考虑在 ECB 工作模式下实现 DES 加解密算法。

Pyhton的版本可以直接使用pycryptodome第三方库快速实现DES加解密功能，这里的代码执行的结果也可用于验证下面 C++ 实现 DES 加解密的正确性。

在使用 C++ 实现 DES 的过程中可能会出现加解密可以正常工作，但是中间生成的密文并不符合标准 DES 算法生成的密文的情况，这实际上只是满足了对称加解密的特点，并没有标准 DES 算法的安全性。因此，一般不推荐任何人去使用个人实现的加解密算法，而应该选择那些经过全世界验证的公开的加解密算法库。

from Crypto.Cipher import DES
# from Crypto.Util.Padding import pad, unpad
from binascii import hexlify, unhexlify

key = unhexlify('0123456789ABCDEF')
plaintext = unhexlify('0123456789ABCDEF')

cipher = DES.new(key, DES.MODE_ECB)
# ciphertext = cipher.encrypt(pad(plaintext, DES.block_size))
ciphertext = cipher.encrypt(plaintext)
print("密文: ", hexlify(ciphertext).decode())

cipher = DES.new(key, DES.MODE_ECB)
# decrypted = unpad(cipher.decrypt(ciphertext), DES.block_size)
decrypted = cipher.decrypt(ciphertext)
print("明文: ", hexlify(decrypted).decode())

C++版本的实现较为复杂，可以参考以下开源库

openssl: C语言实现，功能相当强大和全面，代码量比较庞大，不太适合初学者学习
cryptopp: C++实现，代码庞大且复杂
libtomcrypt: C语言实现，适合初学密码学或期望对密码学有进一步了解的人。名气和使用广泛性不如 OpenSSL 和 Crypto++

实现的思路如下，将代码分为以下几个文件逐步实现

des.h：这个头文件中定义了DES类和它的公有接口。这些接口包括构造函数（用于设置密钥），加密函数和解密函数。
des.cpp：这个源文件中实现了DES类的公有接口。这包括构造函数（其中调用了密钥调度算法），加密函数和解密函数（其中调用了初始置换、F函数和逆初始置换）。
utils.h：这个头文件中定义了一些工具函数，如置换函数和代换函数。
utils.cpp：这个源文件中实现了工具函数。
main.cpp：这个源文件中包含了主函数，用于测试DES类的功能。

实现的过程参考如下，其中涉及的大量置换等统一封装到工具函数

先考虑密钥调度算法实现，生成 16 轮迭代中轮函数f_function所需要的 16 把子密钥。
密钥调度算法细节：
64 位主密钥 $\stackrel{PC-1}\longrightarrow$ 56 位密钥 $\stackrel{均分}\longrightarrow$ 两把 28 位密钥 $\stackrel{循环左移}\longrightarrow$ 两把 28 位密钥 $\stackrel{合并}\longrightarrow$ 56 位密钥 $\stackrel{PC-2}\longrightarrow$ 48 位子密钥
重复上述过程 16 次，只有第一次使用 64 位的主密钥初始化，其余都使用上一次合并后的 56 位密钥初始化，对两把 28 位的密钥法分别进行循环左移操作时，按照固定设计的位移规则进行。
轮函数细节：
32 位的密文 $\stackrel{扩展置换}\longrightarrow$ 48 位的密文 $\stackrel{与子密钥异或}\longrightarrow$ 48 位的密文 $\stackrel{S盒代换}\longrightarrow$ 32 位的密文 $\stackrel{P盒置换}\longrightarrow$ 32 位的密文
S 盒的实现细节：
48 位的密文均分为 8 组，每组 6 位，取最高位和最低位组合成 2 位二进制，计算得到十进制的行号；取剩余的 4 位二进制计算得到列号，根据行、列号找到 S 盒中对应的数字记录到密文中。重复 8 次，每次从不同的 S 盒寻找对应值。
这样从 8 个 S 盒中取出 8 个数字，每个数字占 4 位二进制，组成 32 位的密文。
再考虑加解密算法实现，按照初始置换、16 轮迭代、逆初始置换的先后顺序执行即可。
迭代的细节：
在每一轮迭代中，先把初始置换得到的密文均分为左右 2 段密文，缓存右半部分用于后面进行左右交换。右半部分由左半部分密文与轮函数的返回值（即 48 位子密钥）进行异或运算得到，左半部分则接收之前缓存的右半部分原始值，最后将左、右部分合并得到本轮迭代的 64 位密文，这样的过程重复 16 次。
注意：
16 轮迭代意味着有 16 次左右交换，但有的算法只进行了 15 次交换，在最后一轮迭代时将右、左部分合并，相当于没有进行交换。
实际上，按正常 16 次迭代之后，已经交换了 16 次，但是逆初始置换本身就具有左右交换的性质，那么逆初始置换之后，总共交换了 17 次，这并不是标准的 DES 实现。所以可能会出现以下两种实现：
- 在 16 轮迭代之后，再加一次左右交换用于抵消逆初始置换造成的影响
- 在 16 轮迭代的最后一轮不进行左右交换，第 16 次交换就由逆初始置换去完成
这两种实现都是可行的，笔者的参考代码使用的是后者。
由于对称密码体系的特点，解密的算法与加密基本一致，只需要以相反于加密算法的顺序依次使用 16 把子密钥即可解密。

完整的 C++ 实现代码存放在github 仓库中。

补充

在DES加密算法中，涉及到位数变化的置换主要有以下几种：

PC-1置换：将64位的密钥减少到56位。这个置换丢弃了原始密钥中的每个字节的最后一位，这些位通常用作奇偶校验位。
PC-2置换：将56位的密钥减少到48位，用于生成子密钥。这个置换丢弃了8位，使得每个子密钥都有一个不同的48位的部分。
扩展置换（E）：在每个轮次的开始，将右半部分（32位）扩展到48位，以便与子密钥进行异或操作。这个置换通过复制一些位来实现扩展。

DES的变体和替代方案

**三重DES（3DES）和高级加密标准（AES）**是DES的两个主要替代方案：

三重DES（3DES）：由于DES的密钥长度只有56位，所以它容易受到穷举攻击。为了解决这个问题，人们提出了三重DES。三重DES是对DES加密算法的一个扩展，它使用了三个56位的密钥，所以总的密钥长度为168位。三重DES的工作方式是先用第一个密钥进行DES加密，然后用第二个密钥进行DES解密，最后用第三个密钥进行DES加密。这样，即使有一部分密钥被破解，攻击者也无法得到完整的明文。
高级加密标准（AES）：AES是一种更先进的对称密钥加密算法，它取代了DES成为了新的加密标准。AES使用了128位、192位或256位的密钥，所以它的安全性更高。与DES不同，AES不是基于Feistel网络，而是基于置换-代换网络（SPN）。AES的设计更加简单和高效，所以现在它被广泛应用在各种场合。

参考资料

【计算机博物志】DES的生与死

树下集熵