线性密码分析实战：从S盒线性逼近表到SPN网络密钥恢复

1. 项目概述：一次从理论到实践的密码学“破译”之旅

如果你对密码学感兴趣，尤其是想弄明白那些看似坚不可摧的加密算法背后，是否存在可以被“撬开”的缝隙，那么线性密码分析绝对是你绕不开的一课。这不仅仅是书本上的数学理论，更是一种极具实战价值的攻击方法。这次，我们不谈空泛的概念，直接聚焦于一个核心目标：如何利用线性密码分析，从一个简化版的加密算法中恢复出密钥。整个过程，我们会从一个最基础的密码组件——S盒（Substitution-box）开始，一步步推导出线性逼近表，构建出有效的线性表达式，最终编写代码，像侦探一样从密文和明文的蛛丝马迹中，把隐藏的密钥给“算”出来。

这听起来很酷，对吧？但别担心，我们不会一头扎进复杂的数学公式里。我会用最直白的语言，结合具体的代码示例，让你理解每一步背后的“为什么”。无论你是信息安全专业的学生，还是对密码分析充满好奇的开发者，甚至是CTF（Capture The Flag）比赛的爱好者，这篇内容都将为你提供一套完整的、可复现的实战指南。我们将构建一个简化但结构清晰的SPN（Substitution-Permutation Network，代换-置换网络）密码模型作为攻击目标，它包含了真实分组密码（如AES）的核心思想，但又足够简单，能让我们把注意力集中在分析过程本身。

整个演练的核心在于“线性逼近”。简单来说，就是我们在加密算法那看似完美的非线性操作（比如S盒）中，寻找一种微弱的、非随机的统计偏差。这种偏差就像锁芯里一个极其微小的公差，虽然不能直接打开锁，但通过成千上万次的尝试（选择大量明密文对），我们就能利用这个统计规律，以高于随机猜测的概率，推断出部分密钥比特的信息。这，就是线性密码分析的威力。

2. 核心原理：线性逼近——在非线性世界中寻找确定性

在深入代码之前，我们必须夯实理论基础。线性密码分析的成功，完全建立在“线性逼近”这一核心概念之上。理解它，就理解了整个攻击的引擎。

2.1 S盒与它的“指纹”：线性逼近表

S盒是大多数现代分组密码的非线性来源，它通过一个查找表，将一组输入比特映射到另一组输出比特。理想情况下，这种映射应该是完全随机、无规律的。但现实中，为了兼顾效率和实现，S盒总会存在一些微弱的、可被利用的统计特性。

线性逼近，就是尝试用一组输入比特的线性组合（即异或和），去“逼近”另一组输出比特的线性组合。所谓“逼近”，是指这个等式成立的概率不是50%（完全随机），而是明显偏离50%，比如52%或更高。

为了系统地找出S盒所有可能的、有偏差的线性关系，我们引入线性逼近表（Linear Approximation Table, LAT）。这是一个非常强大的工具。对于一个n输入、m输出的S盒，其LAT是一个2^n行、2^m列的表格。表格中的每一项LAT[α, β]的值计算方式如下：

值 = (满足等式的输入数量) - (不满足等式的输入数量)

其中，等式为：(α • X) = (β • S(X))。这里，α是输入掩码（input mask），β是输出掩码（output mask），•表示点积（即对应比特位相与后全部异或起来，α • X = α₁X₁ ⊕ α₂X₂ ⊕ ... ⊕ αₙXₙ）。X遍历S盒所有可能的输入。

注意：LAT[0, 0]的值永远是 2^n（或 -2^n，取决于定义），因为它对应的是0=0这个永远成立的平凡等式。我们关注的是非零掩码对应的、绝对值大的项。绝对值越大，表示该线性关系成立（或相反）的偏差越大，也就越有用。

为什么LAT如此重要？因为它量化了S盒的“线性度”。攻击者通过查阅LAT，可以迅速找到偏差最大的(α, β)对，这些对就是构建有效攻击路径的“积木”。一个“好”的S盒，其LAT中所有非平凡项的绝对值都应该非常小，从而抵抗线性分析。

2.2 构建攻击路径：线性特征与Piling-up引理

单一的S盒线性逼近偏差可能很小（例如，概率为0.75，偏差为0.25）。但一个加密算法通常有多轮，每轮都有S盒操作。我们需要将多轮的线性逼近连接起来，形成一条贯穿加解密过程的路径，这称为线性特征（Linear Characteristic）。

连接的关键在于，线性逼近只关注输入输出掩码的线性关系。当数据经过轮密钥加（XOR）时，如果密钥比特是固定的，它只会影响等式是否成立的概率，但不会改变偏差的符号（在某些假设下）。当数据经过置换层（P-Box）时，我们只需要相应地调整掩码的位置即可。

那么，如何计算一条多轮线性特征的总偏差呢？这里就要用到Piling-up引理。它告诉我们，对于多个独立的、具有偏差ε_i的随机二元事件，它们同时成立（或同时不成立）的总偏差ε_total可以近似计算为：

ε_total ≈ 2^{k-1} ∏_{i=1}^{k} ε_i

其中k是独立事件的个数。这个引理是线性的核心，它允许我们将多个微小的偏差“堆积”起来，形成一个虽然仍然很小、但已足够被统计检测到的总偏差。例如，4个偏差为0.25的事件堆积，总偏差约为2^3 * (0.25)^4 = 8 * 0.0039 = 0.03125。这意味着对应的线性表达式成立的概率约为0.5 + 0.03125 = 0.53125。

实操心得：Piling-up引理是近似计算，它假设各个线性逼近是独立的。在实际的密码算法中，这个假设可能不完全成立，但通常作为攻击复杂度的有效估计。在设计攻击时，我们的目标就是找到一条总偏差绝对值最大的线性特征，因为这意味着我们需要更少的明密文对就能成功恢复密钥。

2.3 密钥恢复：从统计偏差到密钥比特

有了高偏差的线性特征，我们知道了某个关于输入明文P、输出密文C和中间轮密钥K的线性表达式以较高的概率p = 0.5 + ε成立。这个表达式通常形如：

(掩码_a • P) ⊕ (掩码_b • C) ⊕ (掩码_k • K) = 0（或以概率p成立）

在这个等式中，P和C是已知的（我们收集了大量明密文对），K是未知的密钥部分（通常是最后一轮或第一轮的少量子密钥比特）。掩码_k • K是我们要猜测的密钥比特的线性组合。

攻击步骤如下：

1. 数据收集：收集N个随机明密文对(P, C)。
2. 猜测与统计：对于所有可能的候选子密钥（掩码_k • K涉及的可能密钥值），用每个候选密钥去部分解密最后一轮（或处理第一轮），计算出等式左边的值(掩码_a • P) ⊕ (掩码_b • C‘)，其中C‘是经过候选密钥处理后的中间值。
3. 计数：统计对于每个候选密钥，上面等式成立（结果为0）的次数T。
4. 决策：理论上，正确的密钥对应的成立次数T应该最接近N * p。而错误的密钥，由于它们相当于引入了额外的随机化，其对应的等式成立次数应围绕N * 0.5呈二项分布。因此，选择|T - N/2|值最大的候选密钥作为正确密钥。

所需明密文对的数量N与总偏差ε的平方成反比，约为c / ε^2，其中c是一个较小的常数（如8）。偏差越小，需要的明密文对就越多。

3. 实战目标：一个简化的4比特SPN密码

为了将理论付诸实践，我们设计一个极度简化但五脏俱全的SPN密码作为攻击目标。这能让我们聚焦于分析过程本身，而不被复杂的算法细节干扰。

3.1 密码结构定义

我们的玩具密码参数如下：

• 分组大小：16比特。这足够小以便手动验证，又足够大以体现SPN结构。
• 轮数：4轮。这是展示多轮线性分析的典型轮数。
• 轮函数：每轮包含三个步骤：
  1. 密钥加（AddRoundKey）：将16比特的轮密钥与状态进行按位异或（XOR）。
  2. S盒代换（SubBytes）：将16比特状态划分为4个4比特的小块，每个小块独立通过一个4x4的S盒进行非线性代换。这是我们分析的核心。
  3. P盒置换（Permute）：对16比特状态进行一个固定的比特位置换，提供扩散性。
• 密钥扩展：我们使用一个简单的密钥扩展算法，从一个16比特的主密钥派生出5个16比特的轮密钥（K0, K1, K2, K3, K4）。K0用于初始密钥加，K1-K3用于前三轮的轮密钥加，K4用于最后一轮（第四轮）的轮密钥加。注意：在标准的SPN中，最后一轮通常省略S盒和P盒，只进行密钥加。但为了教学清晰，我们的模型在最后一轮也包含S盒和P盒，攻击目标将是恢复最后一轮的轮密钥K4（或其中的部分比特）。在实际攻击如DES时，攻击的也常是最后一轮的子密钥。

3.2 核心组件设计：S盒与P盒

S盒设计（4输入4输出）： 我们选择一个在密码学教材中常见的、线性性质较差的4x4 S盒作为示例。它的具体映射如下（输入0-15，输出0-15）：S = [0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7]这个S盒不是随机的，它被设计成具有较好的非线性度和差分均匀性，但为了演示，我们依然能从中找到有偏差的线性逼近。

P盒设计（16比特置换）： 我们设计一个简单的置换，目标是将一个S盒输出的比特尽可能快地扩散到多个下一轮的S盒输入中。例如，可以将输入的第i比特置换到输出第(4*i) mod 15的位置（对0-15索引）。具体的置换表在代码中给出。P盒的作用是让线性特征在下一轮中“激活”更多的S盒，虽然这增加了分析的复杂性，但也体现了真实密码的扩散性。

注意事项：在真实的线性分析中，攻击者通常已知或可以逆向工程出S盒和P盒。我们的演练是在“白盒”环境下进行，即我们知道密码的全部细节。黑盒分析是更高级的话题。

4. 代码实现：构建线性分析工具箱

理论说再多，不如一行代码。我们将用Python来构建整个分析流程。确保你已安装Python环境，我们主要会用到numpy来进行高效的数值计算和统计。

4.1 第一步：实现基础密码与计算线性逼近表

首先，我们实现这个玩具SPN密码的加解密功能，这是后续生成测试数据的基础。

import numpy as np # 定义S盒和逆S盒 S_BOX = [0xE, 0x4, 0xD, 0x1, 0x2, 0xF, 0xB, 0x8, 0x3, 0xA, 0x6, 0xC, 0x5, 0x9, 0x0, 0x7] INV_S_BOX = [S_BOX.index(i) for i in range(16)] # 计算逆S盒 # 定义一个简单的16比特P盒（示例，需保证是置换） # 这里将比特i移动到位置 (i*4) % 15，0保持不变 P_BOX = [0] for i in range(1, 16): P_BOX.append((i * 4) % 15) # 注意：需要确保P_BOX是一个完整的0-15的排列，这里仅为示例，实际应定义一个双射。 # 为简化，我们使用一个预设的置换： P_BOX = [0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15] INV_P_BOX = [P_BOX.index(i) for i in range(16)] def sub_bytes(state, sbox): """对16比特状态进行S盒代换，分成4个4比特块""" result = 0 for i in range(4): nibble = (state >> (4*i)) & 0xF sub_nibble = sbox[nibble] result |= (sub_nibble << (4*i)) return result def permute(state, pbox): """根据P盒置换比特位""" result = 0 for i in range(16): bit = (state >> i) & 0x1 if bit: result |= (1 << pbox[i]) return result def spn_encrypt(plaintext, round_keys): """SPN加密，round_keys包含K0到K4共5个密钥""" state = plaintext ^ round_keys[0] # 初始密钥加 for r in range(1, 4): # 前3轮 state = sub_bytes(state, S_BOX) state = permute(state, P_BOX) state = state ^ round_keys[r] # 第4轮（最后一轮） state = sub_bytes(state, S_BOX) state = permute(state, P_BOX) ciphertext = state ^ round_keys[4] return ciphertext # 密钥扩展示例（简单地将主密钥移位） def key_expansion(master_key): # 简单起见，我们生成5个固定的测试密钥 # 实际中应有更复杂的扩展算法 return [master_key ^ (i * 0x1111) for i in range(5)] # 测试加密 master_key = 0x1234 round_keys = key_expansion(master_key) plaintext = 0xABCD ciphertext = spn_encrypt(plaintext, round_keys) print(f"Plaintext: {plaintext:04X}, Ciphertext: {ciphertext:04X}")

接下来，我们实现计算S盒线性逼近表的核心函数。这是整个攻击的基石。

def compute_linear_approximation_table(sbox, input_bits=4, output_bits=4): """ 计算S盒的线性逼近表(LAT)。 返回一个2^input_bits x 2^output_bits的numpy数组。 LAT[alpha, beta] = #{x | dot(alpha, x) == dot(beta, sbox(x))} - 2^(input_bits-1) 另一种常见定义是：计数满足等式的x，再减去不满足的。这里采用偏差形式。 """ n = 2**input_bits m = 2**output_bits lat = np.zeros((n, m), dtype=int) # 遍历所有输入掩码alpha和输出掩码beta for alpha in range(n): for beta in range(m): count = 0 # 遍历所有可能的输入x for x in range(n): # 计算 dot(alpha, x) input_parity = bin(alpha & x).count('1') % 2 # 计算 dot(beta, sbox(x)) output_parity = bin(beta & sbox[x]).count('1') % 2 # 如果相等，计数加1 if input_parity == output_parity: count += 1 # 计算偏差：满足的数量 - 不满足的数量 # 满足的数量 = count, 不满足的数量 = n - count bias = count - (n - count) # 等价于 2*count - n lat[alpha, beta] = bias return lat # 计算我们S盒的LAT lat = compute_linear_approximation_table(S_BOX) print("线性逼近表 (LAT) 示例 (偏差值):") print("alpha\\beta", end="") for beta in range(16): print(f"{beta:4d}", end="") print() for alpha in range(16): print(f"{alpha:6d}:", end="") for beta in range(16): print(f"{lat[alpha, beta]:4d}", end="") print() # 找出偏差绝对值最大的几项（非零掩码） max_bias = 0 max_pairs = [] for alpha in range(1, 16): # 排除alpha=0 for beta in range(1, 16): # 排除beta=0 bias_abs = abs(lat[alpha, beta]) if bias_abs > max_bias: max_bias = bias_abs max_pairs = [(alpha, beta, lat[alpha, beta])] elif bias_abs == max_bias and bias_abs > 0: max_pairs.append((alpha, beta, lat[alpha, beta])) print(f"\n最大偏差为 {max_bias}/16 = {max_bias/16:.3f}") print("对应的(alpha, beta, bias)对有：") for a, b, bias in max_pairs: print(f" alpha={a:04b}({a}), beta={b:04b}({b}), bias={bias}")

运行这段代码，你会看到S盒的LAT。关注那些偏差为±4或±6的项（对于4比特S盒，最大可能偏差是±8，但好的S盒会避免这种情况）。例如，你可能会发现alpha=0xB (1011)和beta=0x2 (0010)的偏差是-6。这意味着线性关系(x3 ⊕ x1 ⊕ x0) = (y1)成立的偏差是-6/16 = -0.375，即成立概率为0.5 - 0.375/2?等等，这里需要小心。

偏差（Bias）与概率（Probability）的转换： 如果LAT[α, β] = b，那么等式α • X = β • S(X)成立的概率p = (b + N) / (2N)，其中N=2^n是输入总数。因为b = #满足 - #不满足 = 2*#满足 - N，所以#满足 = (N+b)/2，概率p = #满足 / N = 1/2 + b/(2N)。 对于我们的4比特S盒，N=16。如果b=-6，则p = 0.5 + (-6)/(2*16) = 0.5 - 6/32 = 0.5 - 0.1875 = 0.3125。这个概率显著偏离0.5，偏差绝对值|ε| = |p-0.5| = 0.1875。这是一个很强的线性逼近！

4.2 第二步：寻找高偏差的线性特征

有了单个S盒的强线性逼近，我们需要为4轮SPN构造一条完整的线性特征。这通常是一个手工与自动化结合的过程。为了简化，我们假设攻击者已知密码结构，并采用一种“贪心”策略：从最后一轮开始反向推导，选择偏差最大的路径。

假设我们的目标是恢复最后一轮轮密钥K4的部分比特。我们构建一条从第一轮S盒输入到第三轮S盒输出（即进入最后一轮密钥加之前）的3轮线性特征。

1. 选择起点：我们选择一个第一轮S盒的输入掩码α1。为了最大化影响，我们通常选择只激活一个S盒（即α1只有4比特非零）。
2. S盒传播：通过查LAT，找到该S盒偏差最大的输出掩码β1。
3. P盒扩散：将β1通过P盒的逆（或根据P盒性质）进行变换，得到第二轮S盒层的输入掩码α2。由于P盒是线性的比特置换，这个变换是确定性的。
4. 重复过程：对第二、第三轮重复步骤2和3。在每一轮，α_i可能会激活多个S盒，我们需要考虑所有被激活S盒的偏差，并使用Piling-up引理计算这一轮的总偏差。
5. 计算总偏差：将每一轮S盒逼近的偏差（ε_i = bias_i / N，N=16）通过Piling-up引理相乘，得到3轮特征的总偏差ε_total。

这个过程可能比较繁琐，需要尝试不同的起点。作为演示，我们假设通过手动搜索（或简单脚本），找到了一条特征，其总偏差|ε_total| ≈ 2^{-5}（即大约0.03125）。这意味着对应的线性表达式成立的概率约为0.5 + 0.03125 = 0.53125。

实操心得：在实际分析AES等复杂密码时，寻找高偏差线性特征是一个研究热点，会用到更复杂的算法和工具（如MILP）。对于我们的玩具密码，手动枚举是可行的。关键在于理解，特征的质量（总偏差）直接决定了攻击所需的数据量N ≈ c / ε_total^2。偏差越小，需要的明密文对就越多。

4.3 第三步：实现密钥恢复攻击

假设我们找到的3轮线性特征涉及最后一轮（第4轮）密钥加前的某些比特。设该线性表达式为：

(λ_p • P) ⊕ (λ_u • U) ⊕ (λ_k • K4) = 0(以概率p = 0.5 + ε成立)

其中：

• P是明文。
• U是第三轮输出（即第四轮S盒和P盒之前的输入，U = C ⊕ K4，但这里C是经过第四轮S盒和P盒后的密文，所以关系更复杂，通常需要部分解密）。
• λ_p, λ_u, λ_k是相应的掩码。
• K4是最后一轮轮密钥。

由于U未知，我们需要用密文C和猜测的最后一轮密钥K4_part（λ_k所涉及的那部分密钥比特）来部分解密，计算出U中与λ_u相关的比特。

攻击算法实现：

def linear_attack(encryption_oracle, lambda_p, lambda_u, lambda_k, target_sbox_indices, sbox, pbox, num_pairs=10000): """ 执行线性密码分析攻击，恢复部分最后一轮密钥。 :param encryption_oracle: 一个函数，输入明文，返回密文（使用未知密钥加密） :param lambda_p: 明文掩码（整数，表示哪些明文比特参与线性表达式） :param lambda_u: 第三轮输出U的掩码（整数，表示哪些U的比特参与） :param lambda_k: 涉及的最后轮密钥比特掩码（通常与lambda_u通过S盒/P盒相关） :param target_sbox_indices: lambda_k涉及的密钥比特影响了哪些S盒（列表） :param num_pairs: 使用的明密文对数量 :return: 猜测的密钥部分（整数），以及所有候选密钥的偏差绝对值 """ # 生成随机明密文对 plaintexts = np.random.randint(0, 65536, size=num_pairs, dtype=np.uint16) ciphertexts = np.array([encryption_oracle(pt) for pt in plaintexts]) # 确定需要猜测的密钥比特数 # 例如，如果lambda_k涉及最后一个S盒的4比特输入密钥，则需要猜测2^4=16种可能 # 这里简化：假设我们攻击一个4比特的S盒对应的密钥，即猜测4比特 guess_space = 2**4 key_guesses = range(guess_space) # 初始化计数器：对于每个密钥猜测，统计线性表达式成立的次数 counts = np.zeros(guess_space, dtype=int) # 对于每个明密文对 for pt, ct in zip(plaintexts, ciphertexts): # 计算表达式左边已知部分：lambda_p • pt left_known_parity = (bin(lambda_p & pt).count('1') % 2) # 对于每个可能的密钥猜测kg for kg in key_guesses: # 部分解密：用猜测的密钥kg，还原出U中与lambda_u相关的比特所需的中间状态 # 这通常需要逆向最后一轮的部分操作（S盒和P盒）。 # 简化模型：假设我们的特征直接指向最后一轮S盒的输入。 # 我们需要从密文ct中，提取出受猜测密钥kg影响的S盒的输出，然后逆S盒得到输入。 # 步骤： # 1. 根据target_sbox_indices，从密文ct中提取出对应的S盒输出（4比特）。 # 2. 用猜测的密钥kg与该输出进行运算（通常是XOR，取决于密钥加的位置）。 # 3. 逆S盒得到该S盒的输入（即U的对应部分）。 # 4. 从该输入中提取出lambda_u所指示的比特，计算奇偶性。 # 这里是一个高度简化的示例，假设攻击最后一个S盒（索引0），且lambda_u只关注该S盒输出的最低位。 # 实际情况复杂得多，需要根据具体的线性特征来编写。 target_sbox_output = (ct >> 0) & 0xF # 假设密文的低4比特是目标S盒输出 # 假设密钥加在S盒之后，那么U的对应部分 = 逆S盒(target_sbox_output ^ kg) u_part = INV_S_BOX[target_sbox_output ^ kg] # 计算lambda_u • u_part (这里假设lambda_u=0x1，即取最低位) u_parity = (u_part & lambda_u) & 0x1 # 简化计算，实际应按点积 # 线性表达式： left_known_parity XOR u_parity XOR (lambda_k • kg) = 0 # 其中 (lambda_k • kg) 是固定的，对于每个kg，我们可以预先计算或直接比较。 # 我们统计等式成立的情况： left_known_parity == u_parity XOR (lambda_k • kg) # 为了简化，我们假设lambda_k • kg = 0（或合并到统计中）。实际上，我们需要考虑。 # 这里我们统计 left_known_parity XOR u_parity == 0 的次数。 total_parity = left_known_parity ^ u_parity if total_parity == 0: counts[kg] += 1 # 计算每个密钥猜测对应的偏差 |T - N/2| biases = np.abs(counts - num_pairs // 2) # 最可能的密钥是偏差最大的那个 best_guess = np.argmax(biases) return best_guess, biases # 示例：假设我们通过特征分析，确定了一个攻击参数 # 这些参数需要根据你实际找到的线性特征来设置 lambda_p = 0x0800 # 示例：明文第11比特（从0开始）参与 lambda_u = 0x0001 # 示例：U的最低位参与 lambda_k = 0x0001 # 示例：涉及K4的最低位 target_sbox_idx = [0] # 涉及最后一个S盒 # 定义一个加密Oracle（使用我们不知道的密钥） true_master_key = 0x5678 true_round_keys = key_expansion(true_master_key) def encryption_oracle(pt): return spn_encrypt(pt, true_round_keys) # 执行攻击 best_guess, biases = linear_attack(encryption_oracle, lambda_p, lambda_u, lambda_k, target_sbox_idx, S_BOX, P_BOX, num_pairs=5000) print(f"\n攻击结果：") print(f"所有候选密钥的偏差绝对值：{biases}") print(f"最可能的密钥部分（4比特）：{best_guess:04b} ({best_guess})") # 验证：提取真实最后一轮密钥的对应4比特 true_k4_part = (true_round_keys[4] >> 0) & 0xF # 假设对应低4比特 print(f"真实的密钥部分（低4比特）：{true_k4_part:04b} ({true_k4_part})") if best_guess == true_k4_part: print("攻击成功！") else: print("攻击失败。可能需要更多数据或调整特征。")

这段代码展示了攻击的骨架。在实际操作中，lambda_p、lambda_u、lambda_k的确定以及部分解密的实现是攻击中最精细、最容易出错的部分。你需要根据你找到的具体线性特征，精确地推导出这些掩码，并编写正确的部分解密代码来计算出U的相关比特奇偶性。

4.4 第四步：优化与扩展

上面的基础攻击可以进一步优化：

1. 多特征组合：可以使用多条线性特征，对同一批密钥比特进行投票，提高成功率。
2. 密钥枚举：恢复出最后一轮的部分密钥比特后，可以降低剩余密钥空间的复杂度，通过穷举或进一步的分析来恢复主密钥。
3. 数据复杂度优化：根据偏差精确计算所需明密文对数量N，避免浪费或不足。
4. 错误容忍：统计上，错误的密钥也可能有较高的偏差。可以保留前几个候选密钥，进行后续验证。

5. 常见问题与排查技巧实录

在实际实现线性分析攻击时，你肯定会遇到各种问题。以下是我在演练中踩过的坑和总结的技巧：

5.1 线性特征偏差计算错误

• 问题：攻击完全无效，最佳候选密钥的偏差不显著，甚至随机分布。
• 排查：
  1. 检查LAT计算：确保你的compute_linear_approximation_table函数计算正确。手动验证几个(α, β)对，特别是偏差最大的那几个。
  2. 验证Piling-up引理应用：确保在计算多轮特征总偏差时，正确应用了Piling-up引理，并且考虑了每一轮所有被激活的S盒。常见错误是只考虑了偏差最大的那条路径，而忽略了同一轮中其他被激活的S盒（其偏差可能是0，即概率0.5，这会稀释总偏差）。
  3. 确认线性表达式：从头到尾仔细推导你的线性表达式。确保在每一轮经过S盒、P盒和密钥加时，掩码的变换是正确的。画一张图来跟踪掩码的传播路径非常有用。

5.2 部分解密逻辑与掩码不对应

• 问题：攻击能产生一个显著偏差最大的密钥，但它是错误的。
• 排查：
  1. 逐比特核对：将你的线性表达式(λ_p • P) ⊕ (λ_u • U) ⊕ (λ_k • K) = 0中的每一个比特都标出来。在代码的部分解密环节，打印出中间值，手动计算几个明密文对，验证对于正确的密钥，等式是否以高概率成立；对于错误密钥，是否接近随机。
  2. 注意密钥加的位置：你的线性特征结束于“第四轮密钥加前”还是“第四轮S盒前”？这决定了部分解密时需要逆操作到哪一步。在我们的简化模型中，如果最后一轮有S盒和P盒，那么U是第三轮的输出，要得到U的相关比特，需要从密文C中逆向最后一轮的密钥加、P盒和S盒。这里的顺序千万不能错。
  3. 掩码方向：线性分析中使用的掩码是作用于数据的。当用猜测的密钥进行部分解密时，你是在计算λ_u • U。确保你从密文和猜测密钥计算出的值，确实是U的对应部分，而不是别的中间状态。

5.3 数据量不足或过多

• 问题：偏差不明显，或者即使数据量很大，攻击也失败。
• 技巧：
  1. 估算数据量：使用公式N ≈ 8 / (ε_total)^2来粗略估计所需明密文对。例如，若ε_total = 2^{-5} = 0.03125，则N ≈ 8 / (0.03125^2) = 8 / 0.0009765625 ≈ 8192。你可以从2N开始尝试。
  2. 观察偏差分布：运行攻击后，不要只看最佳候选。打印出所有候选密钥的偏差绝对值。如果正确的密钥没有排在第一位，但排在前三，说明特征可能是对的，只是数据量不够或噪声干扰。增加数据量再试。
  3. 检查随机性：确保你的明密文对是随机均匀采样的。如果明文有特定模式，可能会影响统计结果。

5.4 代码实现中的细节陷阱

• 比特序：在代码中处理比特掩码和移位时，务必明确你的比特序（LSB 0还是MSB 0）。在整个计算中保持一致性，否则会导致灾难性的错误。建议在关键函数添加注释说明比特序。
• 整数类型：使用明确位宽的无符号整数类型（如np.uint16），避免Python大整数的符号位干扰。
• 性能优化：当num_pairs很大（如10万以上）时，双重循环（对每个明密文对，对每个密钥猜测）会很慢。可以向量化操作：对每个密钥猜测，一次性处理所有明密文对，利用numpy的数组运算提升速度。
• 验证环境：先在一个已知密钥的环境下调试你的攻击代码。确保当你知道正确密钥时，你的攻击代码能将其识别为偏差最大的那个。这是最重要的调试步骤。

线性密码分析是一次完美的理论联系实践的旅程。它要求你对密码算法的结构有清晰的认识，对概率统计有直观的理解，并且具备严谨的代码实现能力。成功恢复出密钥的那一刻，你会对密码算法的脆弱性和设计者的智慧有前所未有的深刻认识。