Python复现DES线性密码分析：从原理到实战破解简化算法

1. 项目概述一次对经典密码学攻击的深度复现最近在整理一些老旧的密码学资料时又翻到了那个标志性的历史事件1993年日本学者松井充Mitsuru Matsui首次公开演示了对DES算法的线性密码分析攻击。这个事件在当时堪称密码学界的一场“地震”它用实验数据有力地证明了即便在当时看来固若金汤的DES在理论上也存在被攻破的可能。这不仅仅是宣告了一个算法的“过时”更重要的是它为我们打开了一扇窗让我们得以用一种全新的、系统性的视角去审视和分析密码算法的内在结构。很多朋友在学习密码学时都会接触到“线性密码分析”这个概念但往往停留在数学公式和理论描述的层面感觉云里雾里。公式里的S盒、线性逼近表达式、偏差、数据复杂度……这些术语堆在一起很容易让人望而却步。我当时学习的时候就在想如果能亲手用代码把这个攻击过程跑一遍看着它从一堆密文里一点点“榨”出密钥的比特那理解起来肯定会透彻得多。所以这个项目的核心目的非常明确我们不满足于纸上谈兵我们要用Python从零开始手把手地复现一次针对简化版DES的线性密码分析攻击。通过这个过程你将不仅仅知道线性密码分析“是什么”更能深刻理解它“为什么”能工作以及“如何”一步步地实施。你会发现那些看似高深的数学概念最终都会转化为清晰的代码逻辑和可观测的实验结果。这对于理解现代密码分析、评估算法强度甚至设计自己的密码组件都有着不可替代的价值。2. 核心原理拆解线性密码分析到底在分析什么在动手写代码之前我们必须把攻击背后的核心思想掰开揉碎讲清楚。线性密码分析属于一种已知明文攻击也就是说攻击者需要收集一定数量的明文密文对。它的终极目标是恢复出加密使用的密钥。2.1 从“绝对随机”到“略有偏好”任何一个安全的密码算法其输入明文和密钥与输出密文之间的关系在理想状态下应该是完全随机的、不可预测的。线性密码分析的精妙之处在于它不去寻找那种“输入A一定导致输出B”的确定性关系这种关系在强密码算法中几乎不存在而是去寻找一种微弱的“统计偏好”。具体来说它试图找到明文、密文和密钥某些比特之间的一个线性关系。这个关系形如P[i1] ⊕ P[i2] ⊕ ... ⊕ C[j1] ⊕ C[j2] ⊕ ... ⊕ K[k1] ⊕ K[k2] ⊕ ... 0其中P[i],C[j],K[k]分别代表明文、密文和密钥的第i, j, k个比特⊕表示异或XOR运算。如果这个等式成立的概率严格不等于 1/2比如是 0.5 ε那么我们就说存在一个线性逼近ε 被称为偏差Bias。偏差的绝对值越大说明这个线性关系成立的概率偏离随机1/2的程度越大它所携带的关于密钥的信息就越多攻击也就越有效。注意这里有个关键点。对于攻击者而言明文P和密文C是已知的但密钥K是未知的。因此上面那个等式左边除了涉及密钥的比特部分其他都是已知量。我们可以把已知部分算出来得到一个值我们暂时称之为“中间结果”。这个“中间结果”等于密钥部分比特的异或和的概率不是1/2而是有偏差的。2.2 DES算法结构与攻击突破口S盒DES算法之所以能被线性密码分析成功攻击关键突破口在于其非线性组件——S盒。DES的核心运算Feistel结构中的F函数包含扩展、与子密钥异或、S盒替换和置换。其中S盒是唯一的非线性环节它将6位输入映射为4位输出。线性密码分析要做的就是为这些S盒寻找高质量的线性逼近表达式。也就是找到S盒的输入比特和输出比特之间的一个线性关系使得这个关系成立的概率明显偏离1/2。松井充的研究成果就是找到了DES中多个S盒的一系列这样的高偏差逼近。2.3 攻击的总体流程理解了上述核心思想整个攻击流程就可以概括为以下四个步骤寻找线性逼近分析DES的S盒找到一条或组合多条贯穿多轮加密的、高偏差的线性逼近路径。这步通常需要深厚的密码分析理论功底在我们的复现中我们会直接采用已知的、针对简化DES的经典逼近路径。收集数据获取大量已知的明文密文对。数量取决于线性逼近的偏差大小偏差越大所需数据越少。部分密钥恢复对于每个可能的候选子密钥攻击目标通常是最后一轮或首尾几轮的子密钥用所有已知的明文密文对去验证那个关键的线性表达式。统计表达式成立结果为0的次数。正确的子密钥会使统计结果最明显地体现出预期的偏差而错误的子密钥则会使结果趋近于随机1/2附近。密钥验证与扩展恢复出部分轮的子密钥后再利用DES的密钥调度算法反推或暴力搜索主密钥的剩余比特最终用少量明文密文对验证整个密钥的正确性。我们的Python复现将严格遵循这个逻辑流程将每一个步骤都转化为具体的函数和循环。3. 实验环境与简化模型搭建为了聚焦于线性密码分析本身而不被DES完整的16轮复杂度和庞大的密钥空间所淹没我们首先需要构建一个简化版的实验模型。这是学习过程中非常实用的一步。3.1 为什么需要简化完整的DES有16轮每轮使用48位的子密钥主密钥56位。对其进行线性分析需要处理非常复杂的线性逼近路径和天文数字般的候选密钥2^48这对于教学和复现来说计算量过大。因此我们通常会选择一个3轮或4轮的简化DES作为攻击目标。这样我们可以清晰地观察到线性逼近如何贯穿有限的轮数以及攻击过程如何运作同时将候选密钥空间控制在可计算的范围内例如攻击最后一轮的48位子密钥简化后可能只针对其中关键的若干比特。3.2 核心模块设计与实现我们的代码将围绕几个核心模块构建简化DES加解密模块实现一个3轮DES的加密和解密函数。这包括IP/FP置换、Feistel轮函数、子密钥生成等。我们需要确保这个简化算法本身是正确的这样才能为我们生成可靠的明文密文测试数据。线性逼近表生成模块针对我们简化DES中使用的S盒可以直接使用标准DES的S盒计算并存储其线性逼近表。这个表记录了所有可能的输入掩码和输出掩码组合下的偏差。这是攻击的“弹药库”。数据收集模块随机生成一个固定密钥然后用我们的简化DES加密大量随机明文生成明文-密文对数据集。攻击实施模块这是核心。根据选定的线性逼近路径例如贯穿第1轮到第3轮的某条路径编写函数遍历可能的候选子密钥例如最后一轮子密钥中参与目标S盒运算的6位并对每个候选密钥统计线性表达式成立的概率找出偏差最大的那个。3.3 工具与库选择我们将使用纯Python的标准库进行实现主要依赖random生成数据itertools进行密钥遍历collections.Counter进行统计。不引入复杂的密码学库如pycryptodome目的是保证每一步都透明可见。实操心得在实现简化DES时比特的操作是基础。我强烈建议将数据明文、密文、密钥都表示为整数然后使用Python的位运算,|,^,,,~和位掩码来提取和设置特定位。相比于操作字符串形式的‘0’和‘1’整数位运算不仅效率高而且代码更简洁更符合我们对比特流的直觉。例如获取一个32位整数data的第i位从右向左从0开始计数可以用(data i) 1。4. 手把手代码复现构建简化DES与攻击框架现在让我们进入具体的代码实现环节。我会分块解释并提供完整的代码片段。4.1 实现一个3轮简化DES首先我们实现一个极度简化的3轮DES。为了突出重点我们会省略一些置换如IP/FP或者使用简化的S盒和P置换。这里的关键是Feistel结构和轮函数F要正确。# 示例一个极度简化的组件定义 # 假设我们使用DES的第一个S盒 (S1)并简化其输出 S_BOX_SIMPLE [ # 简化后的4行16列S盒实际DES的S盒是4行16列输入6位输出4位 [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] ] def permute(bits, permutation_table, input_bits_len): 通用置换函数 output 0 for i, pos in enumerate(permutation_table): if (bits (input_bits_len - pos)) 1: # 注意位序这里假设表格是从左到右的位序 output | (1 (len(permutation_table) - 1 - i)) return output def feistel_function(half_block, subkey): 简化的轮函数F # 1. 扩展 (例如32位扩展到48位这里我们简化) expanded half_block # 简化假设扩展就是自身 # 2. 与子密钥异或 xored expanded ^ subkey # 3. S盒替换 (这里只用一个简化S盒) # 假设xored的6位作为S盒输入 row ((xored 0b100000) 4) | (xored 0b000001) col (xored 0b011110) 1 sbox_output S_BOX_SIMPLE[row][col] # 4. 置换 (简化) p_perm [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] # 注意我们的sbox_output只有4位需要先扩展到32位简化处理 output permute(sbox_output, p_perm, 32) # 这里参数需要根据实际情况调整 return output def simplified_des_encrypt(plaintext, key, rounds3): 简化版3轮DES加密 L plaintext 32 R plaintext 0xFFFFFFFF # 简化密钥调度直接生成3个子密钥此处仅为示例实际应生成不同密钥 subkeys [key (16*i) 0xFFFF for i in range(rounds)] # 生成简单的16位子密钥 for i in range(rounds): L, R R, L ^ feistel_function(R, subkeys[i]) ciphertext (R 32) | L return ciphertext以上是一个高度简化的框架用于说明结构。在实际的复现项目中你需要实现完整的DES组件包括初始置换、逆初始置换、完整的8个S盒、P置换以及正确的密钥调度算法即使是对于3轮版本。4.2 计算S盒的线性逼近表这是线性密码分析的“心脏”。对于每个S盒我们计算其线性逼近表LAT。LAT[a][b]的值表示对于所有可能的6位输入X满足(a·X) (b·S(X))的X的数量减去8因为总共有64个输入期望值是32减去32得到偏差的倍数。其中·表示点积即比特的异或和。def compute_linear_approximation_table(sbox): 计算给定S盒的线性逼近表。 sbox: 一个列表下标为输入0-63值为输出0-15 返回一个 64x16 的列表LAT[input_mask][output_mask] count - 32 n_input 6 # S盒输入位数 n_output 4 # S盒输出位数 lat [[0 for _ in range(1n_output)] for _ in range(1n_input)] total_inputs 1 n_input for input_mask in range(1n_input): for output_mask in range(1n_output): count 0 for x in range(total_inputs): # 计算输入点积: input_mask · x input_parity bin(input_mask x).count(1) % 2 # 计算输出点积: output_mask · S(x) output_parity bin(output_mask sbox[x]).count(1) % 2 if input_parity output_parity: count 1 # LAT值 符合的个数 - 期望值(总数/2) lat[input_mask][output_mask] count - (total_inputs // 2) return lat注意事项计算LAT是计算密集型任务但对于6位输入4位输出的S盒64*161024种掩码组合每种遍历64个输入在现代计算机上瞬间即可完成。LAT中绝对值大的项就是我们要找的高质量线性逼近。例如LAT[0b001100][0b0011] 12意味着偏差 ε 12/64 0.1875这是一个很强的线性关系。4.3 实施线性密码分析攻击假设我们针对一个3轮简化DES并已知一条高质量的线性逼近路径。这条路径可能涉及第1轮和第3轮的某些S盒并绕过第2轮利用Feistel结构的特性。设这条路径的线性表达式为P[i1] ⊕ ... ⊕ C[j1] ⊕ ... ⊕ K[k1] ⊕ ... 0 其偏差为 ε。攻击目标是恢复最后一轮第3轮子密钥中参与特定S盒运算的若干比特比如6位。设这部分子密钥比特为K_sub。攻击步骤如下收集N个已知的明文P密文C对。对于K_sub所有可能的候选值0 到 2^6 - 1 63 a. 对于每一个P, C对 i. 根据候选的K_sub和密文C的右半部分R3反向计算出第3轮S盒的输入需要经过逆置换和逆扩展具体取决于路径。 ii. 根据线性逼近路径从P、C以及计算出的中间值中提取出线性表达式左边的所有已知比特计算出一个结果T0或1。 b. 统计所有N对数据中T0的次数记为count_zero。 c. 计算实验概率p count_zero / N。 d. 计算实验偏差|p - 0.5|。记录下这个偏差值。遍历完所有候选K_sub后选择那个使得实验偏差最接近理论偏差 ε或绝对值最大的候选值作为最有可能的正确子密钥部分。def linear_cryptanalysis_attack(plaintexts, ciphertexts, lat, target_sbox_idx, input_mask, output_mask, theoretical_bias): 实施线性密码分析攻击恢复最后一轮特定S盒的子密钥比特。 plaintexts, ciphertexts: 明文和密文列表 lat: 线性逼近表 target_sbox_idx: 目标S盒的索引用于定位密文中对应的比特 input_mask, output_mask: 针对目标S盒的线性逼近掩码 theoretical_bias: 该线性逼近的理论偏差 best_key_guess None best_bias 0.0 # 假设子密钥参与该S盒的部分是6位 for key_guess in range(64): # 2^6 64 count_zero 0 for p, c in zip(plaintexts, ciphertexts): # 1. 根据密文和候选密钥计算目标S盒的输入需要根据具体DES结构实现 # 假设ciphertext是64位R3是右32位。需要提取进入目标S盒的6位。 # 这里是一个高度简化的示意 # expanded_r3 expansion_function(c 0xFFFFFFFF) # 扩展 # sbox_input extract_sbox_bits(expanded_r3, target_sbox_idx) ^ key_guess sbox_input ... # 根据具体结构计算 # 2. 计算线性表达式左边的值 # 从明文p、密文c中提取路径涉及的其他比特并与S盒的输入输出掩码点积结合 # T (input_mask · sbox_input) ⊕ (output_mask · sbox_output) ⊕ (其他路径上的明文/密文比特) # 其中sbox_output可以通过S盒查询得到sbox_output SBOX[sbox_input] T ... # 计算线性表达式的结果应为0或1 if T 0: count_zero 1 experimental_prob count_zero / len(plaintexts) experimental_bias abs(experimental_prob - 0.5) # 记录与理论偏差最接近的或者偏差绝对值最大的 if abs(experimental_bias - abs(theoretical_bias)) abs(best_bias - abs(theoretical_bias)): # 或者 if experimental_bias best_bias: best_bias experimental_bias best_key_guess key_guess return best_key_guess, best_bias5. 实战演练运行攻击并分析结果有了上面的框架我们就可以运行一个完整的实验了。5.1 生成测试数据首先我们随机生成一个主密钥并用我们的简化3轮DES加密大量随机明文。import random def generate_test_data(num_pairs, key): 生成指定数量的明文密文对 plaintexts [] ciphertexts [] for _ in range(num_pairs): pt random.getrandbits(64) # 生成64位随机明文 ct simplified_des_encrypt(pt, key) plaintexts.append(pt) ciphertexts.append(ct) return plaintexts, ciphertexts # 设置密钥和生成数据 true_key 0x133457799BBCDFF1 # 一个示例密钥 plaintexts, ciphertexts generate_test_data(10000, true_key) # 生成1万对数据5.2 选择线性逼近并执行攻击假设我们通过分析找到了针对第一个S盒S1的一个高偏差逼近其输入掩码α 0x0F二进制001111输出掩码β 0x0E二进制001110从LAT表中查得偏差ε 12/64 0.1875。并且我们的攻击路径设计使得最终表达式只依赖于最后一轮子密钥中进入S1的6位密钥比特。# 假设我们已经计算好了LAT表 lat_s1 compute_linear_approximation_table(S1_BOX) # S1_BOX是标准DES的S1盒定义 input_mask 0x0F # 0b001111 output_mask 0x0E # 0b001110 theoretical_bias 12/64 # 执行攻击 recovered_partial_key, achieved_bias linear_cryptanalysis_attack( plaintexts, ciphertexts, lat_s1, target_sbox_idx0, input_maskinput_mask, output_maskoutput_mask, theoretical_biastheoretical_bias ) print(f恢复出的部分子密钥6位: {recovered_partial_key:06b}) print(f攻击得到的实验偏差: {achieved_bias:.6f}) print(f理论偏差: {theoretical_bias:.6f})5.3 结果解读与有效性验证如果攻击成功你会看到以下情况recovered_partial_key的值应该等于真实密钥中对应那6位的值。achieved_bias应该非常接近theoretical_bias0.1875而其他错误的候选密钥对应的偏差会接近0。为了验证我们可以计算所有候选密钥的偏差并绘制成图。正确的密钥会像一个明显的“尖峰”一样突出。import matplotlib.pyplot as plt # ... 在攻击函数中记录所有候选密钥的偏差 ... all_key_guesses list(range(64)) all_biases [] # 在循环中收集每个key_guess的experimental_bias plt.figure(figsize(10, 6)) plt.bar(all_key_guesses, all_biases) plt.axhline(ytheoretical_bias, colorr, linestyle--, labelTheoretical Bias) plt.xlabel(Candidate Partial Key (0-63)) plt.ylabel(Experimental Bias |p-0.5|) plt.title(Linear Cryptanalysis Result: Bias for each Key Guess) plt.legend() plt.grid(True, alpha0.3) plt.show()在成功的攻击中图表上会有一个柱子的高度明显高于其他所有柱子并且接近红色的理论偏差虚线那个柱子对应的横坐标就是正确的部分子密钥。实操心得数据量N至关重要。根据线性密码分析的理论所需明文对数量N大约与c / ε^2成正比其中c是一个常数例如对于95%的成功率c≈8。对于偏差 ε0.1875N ≈ 8 / (0.1875^2) ≈ 227。但在实际代码中由于简化模型和计算中的近似你可能需要几千对数据才能让“尖峰”足够明显。如果数据量太少正确密钥的偏差可能不会显著高于噪声。6. 常见问题、调试技巧与深度思考在实际复现过程中你几乎一定会遇到各种问题。下面是我在实现过程中踩过的坑和总结的经验。6.1 攻击没有出现明显尖峰这是最常见的问题。可能的原因和排查步骤检查简化DES实现是否正确这是基础。用你的加密函数加密几个已知的测试向量可以从标准DES测试中简化得到确保结果正确。如果加密算法本身有误那么所有的分析都是徒劳。检查线性逼近路径是否正确这是攻击的灵魂。你需要反复核对论文或参考资料中的线性逼近表达式确保你代码中提取明文、密文、中间值比特的位序完全正确。一个比特的错误就会导致整个统计失效。调试技巧打印出前几对数据的中间计算过程。手动选择一对明文密文根据你猜测的正确部分子密钥一步步计算线性表达式的值T。然后统计这少量数据中T0的比例看看是否明显偏离0.5。如果连在小样本下都没有偏差那肯定是路径或计算错了。检查密钥调度和子密钥使用确保你的攻击代码中候选子密钥应用的位置和方式与加密过程中真实子密钥的使用方式完全一致。特别是扩展置换E和置换P它们改变了比特的位置需要仔细跟踪。增加数据量线性密码分析是一种统计攻击。数据量越大统计结果越稳定。尝试将num_pairs从1万增加到5万甚至10万观察尖峰是否变得明显。验证偏差计算确保你的experimental_bias计算的是|p - 0.5|其中p是表达式成立的概率。有时可能会混淆成p本身。6.2 如何确定需要多少明文对这是一个理论联系实际的问题。松井的公式N ≈ 1 / (ε^2)给出了一个阶的估计。对于我们的例子 ε0.1875理论值 N ≈ 28。但在实践中由于以下原因需要更多多个近似攻击可能组合了多个S盒的逼近总偏差会变小。错误密钥的随机波动错误密钥的统计结果虽然期望是0.5但会有方差。为了正确密钥的偏差能显著地高出这个随机波动需要更多数据来降低方差。成功率要求理论公式对应一定的成功概率。如果你要求99%的成功率常数c会更大。一个实用的方法是进行多次实验。用不同的随机密钥和明文集运行攻击100次看看成功恢复部分密钥的次数比例。然后调整数据量N直到成功率满足你的要求比如95%。这个过程本身也是一个很好的蒙特卡洛模拟实验。6.3 从部分密钥到完整密钥成功恢复出最后一轮子密钥的若干比特比如6位后这只是万里长征第一步。DES的子密钥有48位。我们需要攻击其他S盒用类似的线性逼近方法可能需要不同的逼近路径攻击最后一轮其他7个S盒对应的子密钥比特。这样我们有可能恢复出全部48位最后一轮子密钥K16在完整16轮DES中。逆向密钥调度DES的密钥调度算法是确定的。已知一轮的子密钥48位由于密钥调度是线性的主要是置换和循环移位我们可以逆向推导出主密钥56位的大部分比特。通常这不足以唯一确定主密钥但可以将主密钥的可能数量从2^56减少到一个很小的集合比如几千或几万个。暴力搜索剩余可能对于这剩下的几千种可能的主密钥直接用一两个已知的明文密文对进行验证瞬间就能找出唯一正确的那个。在我们的简化3轮模型中密钥调度也相应简化恢复部分子密钥后可能直接就能推出完整的主密钥或者只需要极小的暴力搜索。6.4 线性密码分析的局限性与现代意义通过这次复现我们切身感受到了线性密码分析的威力——它利用算法中微小的统计缺陷以远低于暴力破解的复杂度恢复密钥。但它也有明显的局限性需要大量已知明文对于偏差很小的逼近所需明文数量可能非常庞大上百万甚至更多这在某些实际场景中难以获取。算法设计可抵御现代密码算法如AES在设计阶段就严格考虑了抵抗线性密码分析和差分密码分析其S盒和整体结构被精心设计使得任何线性逼近的偏差都极低从而将所需数据量提高到不切实际的程度。那么在今天学习线性密码分析还有意义吗意义重大。理解安全性基础它是衡量密码算法强度的核心工具之一。理解攻击才能更好地理解什么是“安全”。侧信道分析的基础线性密码分析的思想与侧信道攻击中的模板攻击、相关能量分析等有深刻的联系。这些攻击将物理泄露如功耗、电磁辐射视为密码运算的“输出”同样利用统计方法来恢复密钥。密码学研究的基石它是密码分析学的重要范式许多更高级的分析方法都由此演变而来。亲手复现一次这样的经典攻击就像在密码学的历史地图上完成了一次精准的坐标定位。你不再只是听说“DES被线性分析攻破了”而是亲眼看到了攻破它的那道裂缝究竟在哪里有多宽以及需要怎样的工具和耐心去撬开它。这种从理论到实践从公式到代码的完整穿越所带来的理解深度是任何教科书都无法替代的。