加解密模式分析 - DES 加密算法 | Alice and Bobの神秘小屋

从这一章开始，我们进入分组密码的世界。在此之前，建议先回到密码学前置内容 - 密码分类与简介复习一下分组密码的基本概念和构成，方便理解。

分组密码是对称加密算法中最重要的一类算法，它将明文分成固定大小的块进行加密，常见的分组大小有 64 位和 128 位。DES（Data Encryption Standard）是分组密码的经典代表之一，虽然现在已经被认为不安全，但它在密码学史上具有重要地位。

话不多说，我们直接进入 DES 加密算法的核心原理与实现细节。我们将从 DES 的基本结构出发，逐步拆解其初始置换、16 轮 Feistel 结构、子密钥生成等关键步骤，深入理解 DES 的加密过程和安全性分析。

DES 加密算法 🫡

DES 块长度为 64 位，密钥长度为 64 位（其中 8 位为校验位，实际有效 56 位），明文按照 64 位分组，加密得到 64 位密文。DES 对明文进行 16 轮加密运算，每一轮都有一个相应的子密钥参与（子密钥由密钥扩展算法计算得出）。此外，开头和结尾分别有初始置换和最终置换的操作，用于适应硬件电路的算法实现。

这里给出一个简单示意图：
DES 加密算法示意图

密钥扩展算法

一开始，我们填入 56 位的密钥，经过系统按奇校验规则，在每 7 位后插入 1 位校验位（共 8 位），补成 64 位 DES 标准密钥。DES 的密钥扩展算法将 64 位的密钥扩展为 16 个 48 位的子密钥，每个子密钥用于 DES 的每一轮加密运算。这个过程包括以下几个步骤：

先通过 PC-1（Permuted Choice 1）置换去除掉 8 位校验位，得到原来 56 位的密钥。
将 56 位的密钥分成左右 28 位两部分，分别记为 C 和 D。
连续 16 轮运算，每一轮分别先对 C 和 D 进行左移操作（根据轮数不同，左移 1 位或 2 位），然后通过 PC-2（Permuted Choice 2）置换从 C 和 D 中选取 48 位作为当前轮的子密钥。
最终得到 16 个 48 位的子密钥，分别用于 DES 的 16 轮加密运算。

# 代码仅作为表意伪代码，后续一样
subkey=[]
if len(bkey)== 64:
    #PC-1
    bkey = PC_1(bkey)
elif len(bkey) == 56:
    raise ValueError("key must be 56-bit or 64-bit in length")
 #divide the block into two halves
Ci, Di = bkey[:28], bkey[28:]
for i in range(16):
    #Left Rotation
    Ci, Di = LR(Ci, Di, i)
    #PC-2
    subkey.append(PC_2(Ci + Di))
return subkey

初始置换和最终置换（Initial and Final Permutation）

初始置换（IP）和最终置换（IP^-1）是 DES 加密算法中的两个固定置换操作。初始置换在加密开始时对输入的明文进行重新排列，而最终置换在加密结束时对输出的密文进行重新排列。就是简单地根据置换表，吧长度为 64 位的 block 每一个位置进行变换。
IP 和 FP

IP_table=
[
    58,50,42,34,26,18,10,2,
    60,52,44,36,28,20,12,4,
    62,54,46,38,30,22,14,6,
    64,56,48,40,32,24,16,8,
    57,49,41,33,25,17,9,1,
    59,51,43,35,27,19,11,3,
    61,53,45,37,29,21,13,5,
    63,55,47,39,31,23,15,7,
]

def IP(block):
    result=[]
    for i in range(len(IP_table)):
        result.append(block[IP_table[i]-1])
    return result

FP_table=
[
    40,8,48,16,56,24,64,32,
    39,7,47,15,55,23,63,31,
    38,6,46,14,54,22,62,30,
    37,5,45,13,53,21,61,29,
    36,4,44,12,52,20,60,28,
    35,3,43,11,51,19,59,27,
    34,2,42,10,50,18,58,26,
    33,1,41,9,49,17,57,25,
]

def FP(block):
    result = []
    for i in range(len(FP_table)):
        result.append(block[FP_table[i]-1])
    return result

DES 轮加密过程

DES 的加密过程包括 16 轮 Feistel 结构的加密运算，每一轮的输入是前一轮的输出。每一轮的加密过程如下：

将明文分成左右两部分，分别记为 $L_0$ 和 $R_0$。
在每一轮中，计算

$\begin{aligned} L_{i+1} &= R_{i} \\ R_{i+1} &= L_{i} \oplus F(R_{i}, K_{i}) \end{aligned}$

其中 $F$ 是轮函数，$K_i$ 是当前轮的子密钥。

经过 16 轮加密后，将左右两部分合并，并通过最终置换得到密文。

 #Initial permutation
m = IP(m)
 #divide the block into two 32-bit halves
Li, Ri = m[:32], m[32:]
 #16 rounds
for i in range(16):
    Li, Ri = Ri, BlockXor(Li, Feistel(Ri, subkey[i]))
 #merge the two divided half block which is 32-bit into one 64-bit block
m = Ri + Li # There is a need to change order of the final two halves
 #Final permutation
m = FP(m)

轮函数（Feistel Function 费斯妥函数）

这里我们详细讲解轮函数，这种结构的函数有一个更专业的命名，叫做 Feistel Function。这个函数不仅是 DES 加密算法中每一轮加密运算的核心部分，也是许多其他分组密码算法的基础。

轮函数的输入包括一个 32 位的数据块和一个 48 位的子密钥，输出也是一个 32 位的数据块。轮函数的主要步骤如下：

先通过一个扩展置换（Expansion Permutation）将 32 位的数据块扩展为 48 位，以便与子密钥进行异或运算。
将扩展后的数据块与当前轮的子密钥进行异或运算，得到一个 48 位的结果。
将异或结果分成 8 个 6 位的小块，每个小块通过一个 S-Box（Substitution Box）进行替换，得到 32 位的输出。
最后通过一个 P-Box（Permutation Box）对替换后的结果进行置换，得到最终的轮函数输出。

def Feistel(HalfBlock, subkey):
    eHalfBlock = Expansion(HalfBlock)
    xHalfBlock = BlockXor(eHalfBlock, subkey)
    sHalfBlock = Substitution(xHalfBlock)
    return Permutation(sHalfBlock)

DES 加解密 🙂

在已知密文和 16 个子密钥的情况下，由于轮函数以及置换的可逆性，仅需要在轮函数作用时使用逆序的子密钥即可，这也是 DES 加密算法的一个重要特点（Feistel 结构的优势），使得加密和解密过程非常相似，极大地简化了算法的实现。
DES 加解密

# 实际代码实现中，我们可以使用 Python 的 Crypto 库来进行 DES 加密和解密，以下是一个简单的示例：
from Crypto.Cipher import DES

key = ''
des = DES.new(key,DES.MODE_ECB)
plaintext = b''

cipher = des.encrypt(plaintext)
des.decrypt(cipher)

补充：3DES 加密算法 🫢

由于 DES 的安全性问题，3DES（Triple DES）被提出作为 DES 的增强版本。3DES 通过对数据进行三次 DES 加密来提高安全性，常见的模式有 EDE（Encrypt-Decrypt-Encrypt）和 EEE（Encrypt-Encrypt-Encrypt）。虽然 3DES 在一定程度上提高了安全性，但由于其效率较低，现在已经逐渐被 AES 等更现代的加密算法所取代。

具体做法看名字也可以知道，拿 EEE 模式举例，首先准备三个密钥 $K_1$、$K_2$ 和 $K_3$，然后用 $K_1$ 对明文进行 DES 加密，得到中间密文；再用 $K_2$ 对中间密文进行 DES 加密，得到新的中间密文；最后用 $K_3$ 对新的中间密文进行 DES 加密，得到最终的密文。解密过程则是反过来进行。

EDE 模式则是先用 $K_1$ 对明文进行 DES 加密，得到中间密文；再用 $K_2$ 对中间密文进行 DES 解密，得到新的中间密文；最后用 $K_3$ 对新的中间密文进行 DES 加密，得到最终的密文。解密过程同样是反过来进行。
3DES 加密算法