目录
- 一、算法原理
- 每一轮的加密过程
- 1. 初始分组
- 2. 16轮迭代加密
- 3. F函数(核心加密步骤)
- 4. 16轮加密结束
- 密钥生成过程
- 二、代码实例
一、算法原理
DES(数据加密标准)算法对明文数据进行16轮的替换和置换操作,每一轮都会生成一个不同的子密钥,并依次对数据块进行操作。
每一轮的加密过程
DES的每一轮都将64位的明文分为两个部分:左半部分(32位)和右半部分(32位)。加密操作实际上只对右半部分进行变换,而左半部分则直接参与异或运算。具体步骤如下:
1. 初始分组
- 将64位明文经过初始置换(Initial Permutation, IP),重新排列位的顺序,得到新的64位数据,并将其分为左右两部分:
- 左半部分:L₀(32位)
- 右半部分:R₀(32位)
2. 16轮迭代加密
每一轮都会使用不同的子密钥 (K_i),并将当前轮的左半部分 (L_i) 和右半部分 (R_i) 进行如下操作:
-
步骤 1:将前一轮的右半部分 (R_{i-1}) 作为这一轮的新左半部分,即:
L_i = R_{i-1}
-
步骤 2:将前一轮的右半部分 (R_{i-1}) 送入 F函数,并与当前轮的子密钥 (K_i) 进行操作。F函数的详细步骤见后续。F函数的输出结果与前一轮的左半部分 (L_{i-1}) 进行异或运算,生成这一轮的新右半部分 (R_i),即:
R_i = L_{i-1} ⊕ F(R_{i-1}, K_i) -
步骤 3:继续进行下一轮。经过16轮后,左半部分和右半部分合并,形成64位的加密数据。
在每一轮操作中,左右两部分交换一次位置,从而保证密文与明文之间的复杂关系。
3. F函数(核心加密步骤)
F函数是DES算法中的关键步骤,用于生成复杂的加密结果。F函数将32位的右半部分 (R_{i-1}) 和48位的子密钥 (K_i) 结合起来,具体操作如下:
-
扩展置换(E扩展):
32位的右半部分 (R_{i-1}) 经过扩展置换操作,变成48位,扩展时根据一定的规则重复某些位。这一步的作用是增加密文的混淆性,并使其与48位的子密钥 (K_i) 进行异或操作。 -
异或运算:
将扩展后的48位数据与48位的子密钥 (K_i) 进行异或运算,得到48位的新数据。 -
S盒替代:
将48位数据分成8组,每组6位(48位/6),然后使用8个不同的S盒(Substitution box,替代盒)对每组6位进行替代。S盒的作用是将6位的输入转化为4位的输出,从而将48位数据变成32位。每个S盒都有一个特定的查表,用于根据输入的6位值确定输出的4位值。S盒是DES中最重要的非线性变换步骤,是加密过程产生混淆的关键。
-
置换操作(P盒置换):
对S盒替代后的32位输出进行置换操作,将数据位重新排列,增加混淆性。经过这一置换操作后,得到最终的32位输出结果。
F函数的输出与当前轮的左半部分进行异或运算,完成这一轮的加密。
4. 16轮加密结束
在完成16轮加密后,得到两个部分:左半部分 (L_{16}) 和右半部分 (R_{16})。此时将这两个部分组合在一起,并进行逆初始置换(Inverse Initial Permutation, IP⁻¹),得到最终的64位密文。
密钥生成过程
DES使用的是一个56位的主密钥(尽管输入是64位的,但其中每8位用于校验,只留下56位用于实际加密),然后通过一系列的位移和置换操作,从这个主密钥中生成16个子密钥,每个子密钥长度为48位。
-
去掉奇偶校验位:
虽然输入的密钥是64位,但每8位中的第8位是奇偶校验位。因此,首先需要将64位的密钥中的校验位去除,剩下56位用于密钥生成。 -
密钥置换选择 1(PC-1):
对去除校验位后的56位密钥进行第一次置换,称为置换选择1(Permutation Choice 1,PC-1)。PC-1会根据固定规则重新排列这56位密钥,将其分为两部分:左半部分 (C_0) 和右半部分 (D_0),每部分28位。初始56位密钥 -> PC-1 -> 28位的 C_0 和 28位的 D_0
-
左移操作:
在每一轮加密开始时,都会对(C_0) 和 (D_0) 进行左移操作。左移的位数不是固定的,而是根据当前轮次决定的。具体来说,每一轮的左移位数如下:- 第1、2、9、16轮:左移1位
- 其他轮:左移2位
每一轮左移后的值会生成新的 (C_i) 和 (D_i)。
注意是循环左移
C_0, D_0 -> 左移 -> C_1, D_1 -> 左移 -> C_2, D_2 -> …… -> C_16, D_16
-
密钥置换选择 2(PC-2):
左移之后,将 (C_i) 和 (D_i) 组合成56位的密钥,然后使用置换选择2(Permutation Choice 2,PC-2)将这56位压缩为48位。这是通过从56位中选择48位进行排列完成的。PC-2的目的是通过重新选择位的位置并减少位数来生成本轮的子密钥 (K_i)(48位)。56位的 C_i + D_i -> PC-2 -> 48位的子密钥 K_i
-
生成16个子密钥:
通过左移和置换选择2的操作,DES一共会生成16个不同的48位子密钥 (K_1, K_2, …, K_{16}),分别用于每一轮的加密运算。
二、代码实例
# 将十六进制字符串转为二进制字符串
def hex_to_bin(hex_str):bin_str = bin(int(hex_str, 16))[2:].zfill(len(hex_str) * 4)return bin_str# 将二进制字符串转为十六进制字符串
def bin_to_hex(bin_str):hex_str = hex(int(bin_str, 2))[2:].upper().zfill(len(bin_str) // 4)return hex_str# DES初始置换表
IP = [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]# 逆初始置换表
IP_INV = [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]# 扩展置换表
E = [32, 1, 2, 3, 4, 5, 4, 5,6, 7, 8, 9, 8, 9, 10, 11,12, 13, 12, 13, 14, 15, 16, 17,16, 17, 18, 19, 20, 21, 20, 21,22, 23, 24, 25, 24, 25, 26, 27,28, 29, 28, 29, 30, 31, 32, 1]# S盒表
S_BOX = [# S1[[14, 4, 13, 1, 2, 15, 11, 8, 3, 10, 6, 12, 5, 9, 0, 7],[0, 15, 7, 4, 14, 2, 13, 1, 10, 6, 12, 11, 9, 5, 3, 8],[4, 1, 14, 8, 13, 6, 2, 11, 15, 12, 9, 7, 3, 10, 5, 0],[15, 12, 8, 2, 4, 9, 1, 7, 5, 11, 3, 14, 10, 0, 6, 13]],# S2[[15, 1, 8, 14, 6, 11, 3, 4, 9, 7, 2, 13, 12, 0, 5, 10],[3, 13, 4, 7, 15, 2, 8, 14, 12, 0, 1, 10, 6, 9, 11, 5],[0, 14, 7, 11, 10, 4, 13, 1, 5, 8, 12, 6, 9, 3, 2, 15],[13, 8, 10, 1, 3, 15, 4, 2, 11, 6, 7, 12, 0, 5, 14, 9]],# S3[[10, 0, 9, 14, 6, 3, 15, 5, 1, 13, 12, 7, 11, 4, 2, 8],[13, 7, 0, 9, 3, 4, 6, 10, 2, 8, 5, 14, 12, 11, 15, 1],[13, 6, 4, 9, 8, 15, 3, 0, 11, 1, 2, 12, 5, 10, 14, 7],[1, 10, 13, 0, 6, 9, 8, 7, 4, 15, 14, 3, 11, 5, 2, 12]],# S4[[7, 13, 14, 3, 0, 6, 9, 10, 1, 2, 8, 5, 11, 12, 4, 15],[13, 8, 11, 5, 6, 15, 0, 3, 4, 7, 2, 12, 1, 10, 14, 9],[10, 6, 9, 0, 12, 11, 7, 13, 15, 1, 3, 14, 5, 2, 8, 4],[3, 15, 0, 6, 10, 1, 13, 8, 9, 4, 5, 11, 12, 7, 2, 14]],# S5[[2, 12, 4, 1, 7, 10, 11, 6, 8, 5, 3, 15, 13, 0, 14, 9],[14, 11, 2, 12, 4, 7, 13, 1, 5, 0, 15, 10, 3, 9, 8, 6],[4, 2, 1, 11, 10, 13, 7, 8, 15, 9, 12, 5, 6, 3, 0, 14],[11, 8, 12, 7, 1, 14, 2, 13, 6, 15, 0, 9, 10, 4, 5, 3]],# S6[[12, 1, 10, 15, 9, 2, 6, 8, 0, 13, 3, 4, 14, 7, 5, 11],[10, 15, 4, 2, 7, 12, 9, 5, 6, 1, 13, 14, 0, 11, 3, 8],[9, 14, 15, 5, 2, 8, 12, 3, 7, 0, 4, 10, 1, 13, 11, 6],[4, 3, 2, 12, 9, 5, 15, 10, 11, 14, 1, 7, 6, 0, 8, 13]],# S7[[4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1],[13, 0, 11, 7, 4, 9, 1, 10, 14, 3, 5, 12, 2, 15, 8, 6],[1, 4, 11, 13, 12, 3, 7, 14, 10, 15, 6, 8, 0, 5, 9, 2],[6, 11, 13, 8, 1, 4, 10, 7, 9, 5, 0, 15, 14, 2, 3, 12]],# S8[[13, 2, 8, 4, 6, 15, 11, 1, 10, 9, 3, 14, 5, 0, 12, 7],[1, 15, 13, 8, 10, 3, 7, 4, 12, 5, 6, 11, 0, 14, 9, 2],[7, 11, 4, 1, 9, 12, 14, 2, 0, 6, 10, 13, 15, 3, 5, 8],[2, 1, 14, 7, 4, 10, 8, 13, 15, 12, 9, 0, 3, 5, 6, 11]],
]# P盒置换表
P_BOX = [16, 7, 20, 21, 29, 12, 28, 17,1, 15, 23, 26, 5, 18, 31, 10,2, 8, 24, 14, 32, 27, 3, 9,19, 13, 30, 6, 22, 11, 4, 25]# 置换选择1(PC-1)表
PC_1 = [57, 49, 41, 33, 25, 17, 9,1, 58, 50, 42, 34, 26, 18,10, 2, 59, 51, 43, 35, 27,19, 11, 3, 60, 52, 44, 36,63, 55, 47, 39, 31, 23, 15,7, 62, 54, 46, 38, 30, 22,14, 6, 61, 53, 45, 37, 29,21, 13, 5, 28, 20, 12, 4]# 置换选择2(PC-2)表
PC_2 = [14, 17, 11, 24, 1, 5, 3, 28,15, 6, 21, 10, 23, 19, 12, 4,26, 8, 16, 7, 27, 20, 13, 2,41, 52, 31, 37, 47, 55, 30, 40,51, 45, 33, 48, 44, 49, 39, 56,34, 53, 46, 42, 50, 36, 29, 32]# 子密钥生成左移位数
SHIFT_SCHEDULE = [1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1]# 将输入密钥转为64位,并去除校验位得到56位密钥
def key_permutation(key):# key = hex_to_bin(key)print('密钥的key:', key)key = ''.join(key[i - 1] for i in PC_1)return key[:28], key[28:]# 左移操作
def left_shift(key, shifts):return key[shifts:] + key[:shifts]# 根据C和D生成子密钥
def generate_subkeys(C, D):subkeys = []for shift in SHIFT_SCHEDULE:C = left_shift(C, shift)D = left_shift(D, shift)subkey = C + D# 这里也就是在PC_2的列表为下标,看subkey[i]是什么,全部赋值完后,加入到新的subkey中subkey = ''.join(subkey[i - 1] for i in PC_2)subkeys.append(subkey)return subkeys# 执行初始置换和逆置换
def permute(data, table):return ''.join(data[i - 1] for i in table)# 加密的核心f函数,包括扩展置换E、S盒和P盒
def f_function(R, K):# 1. 扩展置换R = ''.join(R[i - 1] for i in E)# 2. 与子密钥K进行异或 字符格式转换 int(K, 2)R = bin(int(R, 2) ^ int(K, 2))[2:].zfill(48)# 3. 经过S盒压缩result = ''for i in range(8):block = R[i * 6:(i + 1) * 6]row = int(block[0] + block[5], 2)col = int(block[1:5], 2)result += bin(S_BOX[i][row][col])[2:].zfill(4)# 4. 经过P盒置换result = ''.join(result[i - 1] for i in P_BOX)return result# DES加密函数
def des_encrypt(plaintext, key):# 1. 初始置换plaintext = permute(plaintext, IP)# 初始置换后的输出print('初始置换后的输出:', plaintext)# 2. 分成左右两部分L, R = plaintext[:32], plaintext[32:]print("R的值为:", R)# 生成16轮子密钥C, D = key_permutation(key) # 去掉奇偶校验位subkeys = generate_subkeys(C, D) # 使用列表将每一层密钥存储起来# 利用enumerate()函数,遍历密钥列表for i, subkey in enumerate(subkeys, 1):print(f"第{i}轮子密钥: {bin_to_hex(subkey)}")# 3. 进行16轮加密for i in range(16):L_new = R# 查看下变换前L的值if i == 0:print("第1轮的L变换前的值为:", L)R_new = bin(int(L, 2) ^ int(f_function(R, subkeys[i]), 2))[2:].zfill(32)L, R = L_new, R_newif i == 0:print("第1轮的R_new的值为:", R_new)print(f"第1轮输出: L = {bin_to_hex(L)}, R = {bin_to_hex(R)}")# 4. 合并L和R,逆初始置换combined = R + Lciphertext = permute(combined, IP_INV)return bin_to_hex(ciphertext)# 主函数
if __name__ == "__main__":plaintext = "0123456789ABCDEF"key = "133457799BBCDFF1"# 转为二进制plaintext_bin = hex_to_bin(plaintext)key_bin = hex_to_bin(key)print("明文的二进制:",plaintext_bin)print("密钥的二进制:", key_bin)# 加密ciphertext = des_encrypt(plaintext_bin, key_bin)print(f"最终密文: {ciphertext}")
下面这个链接是结合例子讲解的,讲的不错
链接: DES加密算法介绍(含例子)