现代密码学——DES

Entropy Lv4

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

DES的工作原理

DES(数据加密标准)是一种对称密钥加密算法,它的工作原理如下:

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

DES算法中置换表的使用顺序如下:

  1. PC-1置换:在密钥调度算法中,首先使用PC-1置换来选择56位的密钥材料。
  2. PC-2置换:在密钥调度算法中,每轮迭代都会使用PC-2置换来生成48位的子密钥。
  3. 初始置换(IP):在加密和解密过程的开始,使用初始置换来重新排列64位的输入。
  4. 扩展置换(E):在每轮迭代中,使用扩展置换将32位的输入扩展到48位。
  5. S盒:在每轮迭代中,使用S盒将48位的输入转换为32位的输出。
  6. P盒置换(P):在每轮迭代中,使用P盒置换来重新排列32位的输出。
  7. 逆初始置换(IP-1):在加密和解密过程的结束,使用逆初始置换来得到最终的64位的输出。

DES中的数学基础

DES(数据加密标准)的数学基础主要包括以下几个部分:

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

DES的安全性分析

DES(数据加密标准)的安全性分析主要包括以下几个部分:

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

DES的基本实现

DES加密算法的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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解密算法的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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 算法的安全性。因此,一般不推荐任何人去使用个人实现的加解密算法,而应该选择那些经过全世界验证的公开的加解密算法库。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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++

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

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

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

  1. 先考虑密钥调度算法实现,生成 16 轮迭代中轮函数f_function所需要的 16 把子密钥。

    密钥调度算法细节:

    64 位主密钥 PC1\stackrel{PC-1}\longrightarrow 56 位密钥 均分\stackrel{均分}\longrightarrow 两把 28 位密钥 循环左移\stackrel{循环左移}\longrightarrow 两把 28 位密钥 合并\stackrel{合并}\longrightarrow 56 位密钥 PC2\stackrel{PC-2}\longrightarrow 48 位子密钥

    重复上述过程 16 次,只有第一次使用 64 位的主密钥初始化,其余都使用上一次合并后的 56 位密钥初始化,对两把 28 位的密钥法分别进行循环左移操作时,按照固定设计的位移规则进行。

    轮函数细节:

    32 位的密文 扩展置换\stackrel{扩展置换}\longrightarrow 48 位的密文 与子密钥异或\stackrel{与子密钥异或}\longrightarrow 48 位的密文 S盒代换\stackrel{S盒代换}\longrightarrow 32 位的密文 P盒置换\stackrel{P盒置换}\longrightarrow 32 位的密文

    S 盒的实现细节:

    48 位的密文均分为 8 组,每组 6 位,取最高位和最低位组合成 2 位二进制,计算得到十进制的行号;取剩余的 4 位二进制计算得到列号,根据行、列号找到 S 盒中对应的数字记录到密文中。重复 8 次,每次从不同的 S 盒寻找对应值。

    这样从 8 个 S 盒中取出 8 个数字,每个数字占 4 位二进制,组成 32 位的密文。

  2. 再考虑加解密算法实现,按照初始置换、16 轮迭代、逆初始置换的先后顺序执行即可。

    迭代的细节:

    在每一轮迭代中,先把初始置换得到的密文均分为左右 2 段密文,缓存右半部分用于后面进行左右交换。右半部分由左半部分密文与轮函数的返回值(即 48 位子密钥)进行异或运算得到,左半部分则接收之前缓存的右半部分原始值,最后将左、右部分合并得到本轮迭代的 64 位密文,这样的过程重复 16 次。

    注意:

    16 轮迭代意味着有 16 次左右交换,但有的算法只进行了 15 次交换,在最后一轮迭代时将右、左部分合并,相当于没有进行交换。

    实际上,按正常 16 次迭代之后,已经交换了 16 次,但是逆初始置换本身就具有左右交换的性质,那么逆初始置换之后,总共交换了 17 次,这并不是标准的 DES 实现。所以可能会出现以下两种实现:

    • 在 16 轮迭代之后,再加一次左右交换用于抵消逆初始置换造成的影响
    • 在 16 轮迭代的最后一轮不进行左右交换,第 16 次交换就由逆初始置换去完成

    这两种实现都是可行的,笔者的参考代码使用的是后者。

    由于对称密码体系的特点,解密的算法与加密基本一致,只需要以相反于加密算法的顺序依次使用 16 把子密钥即可解密。

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

补充

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

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

DES的变体和替代方案

**三重DES(3DES)高级加密标准(AES)**是DES的两个主要替代方案:

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

参考资料

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

  • 标题: 现代密码学——DES
  • 作者: Entropy
  • 创建于 : 2023-11-18 22:48:03
  • 更新于 : 2023-11-23 20:13:20
  • 链接: https://www.entropy-tree.top/2023/11/18/cryptology-des/
  • 版权声明: 本文章采用 CC BY-NC-SA 4.0 进行许可。
评论