1. 项目概述从“玩具”到“实战”的密码学演练最近在整理自己的密码学学习笔记翻到了一个几年前做的课程设计项目名字挺唬人叫“四轮对称分组加密算法设计与线性差分攻击实战实现”。现在回头看这个项目虽然规模不大但麻雀虽小五脏俱全它几乎涵盖了现代分组密码设计与分析的核心思想。说白了这就是一个自己动手造一个“玩具级”的加密算法然后再亲手把它“破解”掉的过程。对于想深入理解DES、AES这些经典算法背后“为什么这么设计”以及“攻击者怎么想”的朋友来说这是一个绝佳的练手项目。它不要求你具备多深的数学功底但能让你对“混淆与扩散”、“S盒设计”、“轮函数结构”以及“差分分析”这些概念有肌肉记忆般的理解。如果你是一名信息安全专业的学生或者是对密码学原理感兴趣的开发者跟着这个思路走一遍绝对比读十篇论文来得实在。2. 算法设计打造我们自己的“微型AES”设计一个加密算法尤其是对称分组加密核心目标是在安全性和效率之间取得平衡。我们的“四轮对称分组加密算法”就是一个简化模型旨在清晰地展示这一平衡过程。2.1 核心参数与整体结构定义首先我们需要定义算法的基本参数这决定了算法的“体格”。经过权衡我选择了以下配置分组长度 (Block Size):64位。这是一个经典的选择早期的DES就是64位分组。对于教学和演示来说64位足够展示所有操作又不会让计算和可视化过于复杂。密钥长度 (Key Size):80位。为什么不是64位或128位这里有个小心思80位介于两者之间既能与64位分组形成区别避免某些简单的弱密钥情况又比128位计算量小。更重要的是它为后续的线性差分攻击分析留下了一个有趣的“攻击面”——密钥编排算法Key Schedule的设计将直接影响攻击复杂度。轮数 (Rounds):4轮。轮数少是为了让后续的差分攻击能够在可接受的计算时间内完成演示。在实际算法中如AES-128为10轮足够的轮数是为了确保密码达到“充分混淆”抵抗各种已知攻击。算法的整体结构采用经典的Feistel网络或SPN结构。为了更贴近AES的设计哲学我选择了SPN结构。加解密过程可以概括为初始密钥加 (AddRoundKey):明文分组与第一轮子密钥进行异或操作。轮函数迭代 (Round Function):重复执行4次轮函数。每一轮包含字节代换、行移位、列混合最后一轮省略、轮密钥加。最终轮 (Final Round):执行字节代换、行移位和轮密钥加不进行列混合。注意选择SPN而非Feistel是因为SPN在每一轮都对整个分组进行了混淆和扩散理论上比Feistel网络每轮只处理一半数据的扩散速度更快也更符合现代密码的设计趋势。2.2 轮函数核心组件详解轮函数是算法的发动机由四个核心步骤构成。2.2.1 S盒设计非线性的灵魂S盒是整个算法中唯一的非线性组件是抵抗线性密码分析和差分密码分析的关键。我们不能直接用AES的S盒那就失去了“设计”的意义。这里我采用了一种经典且透明的设计方法基于有限域GF(2^4)的乘法逆元再加上一个仿射变换。设计过程如下将输入的4位因为我们的基本操作单元定为4位即半字节视为有限域GF(2^4)上的元素。不可约多项式选择P(x) x^4 x 1这是一个在密码学中常用的本原多项式。计算该元素在GF(2^4)上的乘法逆元。0的逆元定义为0。将得到的4位逆元结果通过一个可逆的仿射变换矩阵进行混淆。将结果输出为4位。例如我们手动计算输入为0x4二进制0100的情况在GF(2^4)下0x4对应多项式x^2。计算(x^2)^-1 mod (x^4x1)。通过扩展欧几里得算法或查表可得x^2的逆元是x^2 x 1对应二进制0111即0x7。对0x7(0111) 进行一个特定的仿射变换例如乘以一个4x4的矩阵并加上一个常数向量。假设变换后输出为0x9(1001)。这样我们就得到了S盒的一个映射0x4 - 0x9。遍历所有16种输入0x0到0xF就可以生成一个完整的4x4 S盒。这个S盒具有良好的非线性度和差分均匀性足以抵抗针对我们这个简化算法的简单分析。实操心得自己推导S盒的过程能让你深刻理解“非线性”的含义。你可以写个小程序生成整个S盒表并验证其是否满足“输出比特平衡”、“无固定点”等基本密码学性质。切忌使用随机生成的替换表那很可能存在致命的密码学弱点。2.2.2 行移位与列混合实现比特扩散扩散的目的是让明文或密钥的一位变动能影响到密文中的多位从而隐藏统计特性。行移位 (ShiftRows):我们的64位分组可以视为一个4x4的半字节矩阵每个元素4位。行移位操作就是将这个矩阵的第0行不变第1行循环左移1个位置第2行循环左移2个位置第3行循环左移3个位置。这个操作实现了比特在行内的扩散。列混合 (MixColumns):这是扩散的主力。我们将状态矩阵的每一列视为GF(2^4)上的一个4维向量并与一个固定的4x4可逆矩阵相乘。这个矩阵的每个元素都是GF(2^4)上的值。这个操作确保了输入列中一个半字节的变化会影响到输出列的所有四个半字节实现了强大的列间扩散。列混合矩阵示例在GF(2^4)上[ 02 03 01 01 ] [ 01 02 03 01 ] [ 01 01 02 03 ] [ 03 01 01 02 ]这里的01,02,03是GF(2^4)上的元素分别对应多项式1,x,x1。乘法运算需要模之前提到的不可约多项式x^4 x 1。2.2.3 密钥编排算法从主密钥到轮密钥我们需要从80位的主密钥中为4轮加密加上初始密钥加共需5个子密钥衍生出5个64位的轮子密钥。设计密钥编排算法时需要考虑“密钥雪崩效应”和抵抗“相关密钥攻击”。我设计的简易密钥编排流程如下将80位主密钥存储在一个寄存器中。每次需要轮密钥时取寄存器的左64位作为当前轮密钥。然后对80位寄存器进行一系列操作以更新它为下一轮做准备。更新操作包括循环左移若干位、经过一个S盒替换使用算法本身的S盒或一个不同的固定S盒、与轮常数进行异或。例如第i轮的轮常数RC[i]可以设计为RC[i] i作为4位常数将其放在寄存器的特定位置进行异或以打破对称性。注意事项密钥编排是线性差分攻击的重点突破对象。如果编排算法过于简单例如只是简单截取主密钥的不同部分那么攻击者可能很容易建立轮密钥之间的线性关系大大降低攻击难度。因此引入非线性S盒和不对称性轮常数是必要的。3. 算法实现从伪代码到可运行的程序设计完成后我们需要用代码将其实现。这里以Python为例因为它易于阅读和实验。3.1 基础运算与组件实现首先实现有限域GF(2^4)上的基本运算这是S盒和列混合的基础。# 不可约多项式: x^4 x 1 二进制表示为 10011 (0x13) IRREDUCIBLE_POLY 0b10011 def gf16_mul(a, b): GF(2^4)上的乘法模不可约多项式 x^4 x 1 p 0 for i in range(4): if b 1: p ^ a hi_bit_set a 0x8 # 检查x^3系数是否为1 a 1 if hi_bit_set: a ^ IRREDUCIBLE_POLY b 1 return p 0xF # 确保结果在4位内 def gf16_inv(a): GF(2^4)上求乘法逆元使用扩展欧几里得算法 if a 0: return 0 for i in range(1, 16): if gf16_mul(a, i) 1: return i return 0 # 实际上不会发生接着基于上述运算生成S盒和逆S盒。def generate_sbox(): 生成S盒 inv - 仿射变换 sbox [0] * 16 # 假设仿射变换为: y Ax b, 这里用一个简单的固定变换示例 # 实际应使用一个精心设计的可逆仿射变换矩阵 for x in range(16): inv gf16_inv(x) # 求逆 # 示例仿射变换 (非安全仅演示): 循环左移1位然后与0x5异或 y ((inv 1) | (inv 3)) 0xF # 循环左移1位 y ^ 0x5 sbox[x] y return sbox SBOX generate_sbox() INV_SBOX [SBOX.index(i) for i in range(16)] # 生成逆S盒3.2 核心加密流程代码实现分组和轮函数操作。def add_round_key(state, round_key): 轮密钥加64位状态与64位轮密钥异或 return state ^ round_key def sub_bytes(state, sbox): 字节代换将64位状态分为16个4位半字节分别进行S盒替换 output 0 for i in range(16): nibble (state (i * 4)) 0xF sub_nibble sbox[nibble] output | (sub_nibble (i * 4)) return output def shift_rows(state): 行移位将64位状态视为4x4矩阵对行进行循环左移 # 将64位数解析为4x4半字节矩阵 matrix [(state (i*16)) 0xFFFF for i in range(4)] # 每行16位 new_matrix [0]*4 for r in range(4): row matrix[r] # 每行4个半字节循环左移r个半字节 shifted 0 for c in range(4): nibble (row (c*4)) 0xF shifted | (nibble (((c r) % 4) * 4)) new_matrix[r] shifted # 重新组合为64位 new_state 0 for r in range(4): new_state | (new_matrix[r] (r*16)) return new_state def mix_columns(state): 列混合在GF(2^4)上对每一列进行矩阵乘法 # 提取列 (每列4个半字节共16位) cols [(state (c*4)) 0xFFFF for c in range(4)] # 注意这里列索引 new_cols [0]*4 # 固定矩阵 M (示例需确保可逆) # M [[2,3,1,1], [1,2,3,1], [1,1,2,3], [3,1,1,2]] in GF(2^4) M [ [0x2, 0x3, 0x1, 0x1], [0x1, 0x2, 0x3, 0x1], [0x1, 0x1, 0x2, 0x3], [0x3, 0x1, 0x1, 0x2] ] for c in range(4): col cols[c] # 将列向量提取为4个半字节列表 col_vec [(col (i*4)) 0xF for i in range(4)] new_col_vec [0]*4 for i in range(4): # 计算新列向量的每个元素 s 0 for j in range(4): s ^ gf16_mul(M[i][j], col_vec[j]) new_col_vec[i] s # 将新列向量组合回16位整数 new_col 0 for i, val in enumerate(new_col_vec): new_col | (val (i*4)) new_cols[c] new_col # 将列重新组合成状态 (注意这里需要转置回行优先) new_state 0 for r in range(4): # 行 for c in range(4): # 列 nibble (new_cols[c] (r*4)) 0xF new_state | (nibble ((r*4 c)*4)) # 需要仔细计算位置 # 上面的位置计算较复杂另一种更清晰的方法是先构建矩阵再扁平化 # 此处为简化假设我们有一个正确的矩阵转置和组合函数 return new_state # 注意此mix_columns函数为概念演示位操作需仔细调试 def key_schedule(master_key): 密钥编排从80位主密钥生成5个64位轮密钥 round_keys [] key_reg master_key # 假设master_key是80位整数 for r in range(5): # 提取当前轮密钥高64位 round_key (key_reg 16) 0xFFFFFFFFFFFFFFFF # 取80位中的高64位 round_keys.append(round_key) # 更新密钥寄存器 # 1. 循环左移若干位例如13位 key_reg ((key_reg 13) | (key_reg (80-13))) ((180)-1) # 2. 将寄存器低4位通过S盒替换 low_nibble key_reg 0xF key_reg (key_reg ~0xF) | SBOX[low_nibble] # 3. 与轮常数异或例如轮常数放在特定位置 rc r # 轮常数 key_reg ^ (rc 60) # 在寄存器中间位置异或 return round_keys def encrypt(plaintext, master_key): 完整加密流程 round_keys key_schedule(master_key) state plaintext # 初始密钥加 state add_round_key(state, round_keys[0]) # 前3轮 for r in range(1, 4): state sub_bytes(state, SBOX) state shift_rows(state) state mix_columns(state) state add_round_key(state, round_keys[r]) # 最后一轮无列混合 state sub_bytes(state, SBOX) state shift_rows(state) state add_round_key(state, round_keys[4]) return state踩坑实录在实现mix_columns时最头疼的是位操作和矩阵索引的对应关系。一个4x4的半字节矩阵在内存中可以用多种方式表示行优先/列优先。我强烈建议在实现时先编写一个print_state(state)函数将64位状态以4x4半字节矩阵的形式打印出来每完成一个步骤就打印一次这样能直观地验证行移位和列混合是否正确。位操作的bug非常隐蔽肉眼难以察觉。4. 线性差分攻击原理与目标造好了“锁”现在我们来当“开锁匠”。线性密码分析是一种已知明文攻击其核心思想是寻找算法行为与随机置换之间的偏差。具体来说就是寻找一个线性逼近式它关联了明文、密文和密钥的一些比特并且这个式子成立的概率p ≠ 1/2。偏差ε |p - 1/2|越大攻击效果越好。对于我们的4轮SPN结构算法直接攻击全轮非常困难。一个经典的策略是攻击最后一轮。我们寻找一个针对前3轮的线性逼近这个逼近绕过或近似了S盒的非线性。然后我们猜测最后一轮轮密钥K4的部分比特称为“攻击子密钥”用猜测的密钥对密文进行部分解密即逆操作到第3轮结束的状态然后验证线性逼近式是否以较高的偏差成立。对每个可能的攻击子密钥候选值进行统计使得偏差明显最大的那个候选值就最有可能是真实的子密钥比特。我们的攻击目标恢复最后一轮轮密钥K4的部分比特。由于算法只有4轮恢复部分K4后结合密钥编排算法有可能反推主密钥或者大大降低暴力搜索剩余密钥空间的复杂度。5. 攻击实战步步为营恢复密钥理论很美好实战则需要细致的步骤。下面我们一步步拆解如何对我们的算法实施线性差分攻击。5.1 构建线性逼近表攻击的第一步是分析算法中的唯一非线性组件——S盒。我们需要为S盒构建一个线性逼近表。这个表的大小是2^(输入比特数) * 2^(输出比特数)对于4位S盒就是16x16。表项LAT[a][b]的值表示满足线性掩码方程a·x b·S(x)的输入x的个数减去8因为期望值是8其中a是输入掩码b是输出掩码·表示点积按位与后异或。def compute_lat(sbox): 计算S盒的线性逼近表 n len(sbox) # 16 lat [[0 for _ in range(n)] for _ in range(n)] for input_mask in range(n): for output_mask in range(n): count 0 for x in range(n): # 计算 a · x input_parity bin(input_mask x).count(1) % 2 # 计算 b · S(x) output_parity bin(output_mask sbox[x]).count(1) % 2 if input_parity output_parity: count 1 # 偏差 (count / n) - 0.5 这里存储 count - n/2 lat[input_mask][output_mask] count - n//2 return lat LAT compute_lat(SBOX) # 寻找偏差绝对值最大的项 max_bias 0 best_masks [] for a in range(16): for b in range(16): if abs(LAT[a][b]) max_bias: max_bias abs(LAT[a][b]) best_masks [(a, b)] elif abs(LAT[a][b]) max_bias: best_masks.append((a, b)) print(f最大偏差: {max_bias/16:.4f} 对应掩码对: {best_masks})假设我们找到了一个强线性逼近例如输入掩码a0xB输出掩码b0x4偏差为0.25。这意味着对于随机输入a·x b·S(x)成立的概率是0.5 0.25 0.75。5.2 寻找多轮线性特征单轮S盒的逼近需要穿过整个算法。我们需要将单轮的线性特征连接起来形成一个多轮的线性特征。这涉及到线性掩码在经过线性层行移位、列混合、密钥加时的传播规则。密钥加线性掩码直接穿过因为(a·x) ⊕ (a·k) a·(x⊕k)。密钥比特会引入一个固定但未知的偏差常数这会在最终的攻击统计中被抵消。行移位和列混合作为线性变换它们会改变掩码的值。如果线性变换用矩阵M表示那么掩码λ在穿过该层后变为(M^T)^{-1} λ在二进制域上。对于我们的简化算法我们可以手动追踪或编写代码模拟掩码的传播。假设我们通过分析找到了一个贯穿前3轮的线性特征它将第1轮S盒输入的某些比特与明文和第一轮子密钥相关与第3轮结束后的状态的某些比特我们称之为U3关联了起来偏差较大。这个特征可以表示为P[i1] ⊕ P[i2] ⊕ ... ⊕ K1[j1] ⊕ K1[j2] ⊕ ... U3[k1] ⊕ U3[k2] ⊕ ...其中P是明文比特K1是第一轮子密钥比特U3是第3轮输出即第4轮输入的状态比特。5.3 实施攻击与子密钥恢复我们不知道U3但知道密文C和U3的关系C SubBytes(ShiftRows(U3)) ⊕ K4。因此U3 InvShiftRows(InvSubBytes(C ⊕ K4))。这里K4就是我们要攻击的最后一轮密钥。攻击步骤收集数据获取大量例如10000对已知明文-密文对(P, C)。确定攻击子密钥位我们的线性特征涉及U3的某些比特。根据U3的计算公式恢复这些比特需要知道K4的哪些比特由于S盒和行移位是按半字节4位或字节操作的通常我们需要猜测影响目标U3比特所在的那个半字节或字节的全部4位或8位密钥。这就是我们的“攻击子密钥”。猜测与统计遍历攻击子密钥所有可能的值对于4位半字节是16种可能。对于每个候选值guess对每一个密文C用guess对相应的半字节进行部分解密计算出我们关心的U3的那一个比特的值记为U3_bit。同时从对应的明文P中根据线性特征提取出明文侧的比特和记为P_sum。注意线性特征中涉及的第一轮密钥比特K1[...]是未知常数它们的影响会合并成一个固定的偏差。统计P_sum ⊕ U3_bit 0的次数T。分析结果对于每个候选密钥guess计算统计量|T/N - 0.5|其中N是总明文对数量。理论上对于正确的密钥猜测这个统计量应该接近我们之前从线性特征推导出的理论偏差|ε|。而对于错误的密钥猜测我们相当于用错误的密钥去“解密”导致计算出的U3_bit基本上是随机的从而使P_sum ⊕ U3_bit的结果也接近随机其统计量会接近0。确定密钥选择使得|T/N - 0.5|最大的那个候选值guess作为攻击子密钥最可能的值。def linear_attack(plaintexts, ciphertexts, input_mask, output_mask, target_nibble_pos): 实施线性攻击 :param plaintexts: 明文列表 :param ciphertexts: 密文列表 :param input_mask: 针对目标S盒的输入线性掩码 (4位) :param output_mask: 针对目标S盒的输出线性掩码 (4位) :param target_nibble_pos: 目标S盒在状态中的位置 (0-15) :return: 最可能的子密钥候选值 N len(plaintexts) best_guess -1 max_bias_obs 0 # 遍历该半字节所有可能的密钥值 (0-15) for key_guess in range(16): count 0 for p, c in zip(plaintexts, ciphertexts): # 1. 从明文中提取输入掩码对应的比特和 # 假设我们的线性特征只涉及目标S盒的输入且input_mask对应明文和K1的某些位 # 简化起见假设我们已知这个线性关系这里用一个函数get_plain_sum(p)表示 plain_sum get_plain_sum(p, input_mask) # 需要根据具体特征实现 # 2. 用猜测的密钥对密文进行部分解密得到目标S盒的输入U3 # 提取密文中目标半字节 cipher_nibble (c (target_nibble_pos * 4)) 0xF # 部分解密逆S盒的输入 密文半字节 ⊕ 猜测的密钥半字节 inverse_sbox_input cipher_nibble ^ key_guess # 通过逆S盒得到U3的半字节 (注意这里需要逆S盒) u3_nibble INV_SBOX[inverse_sbox_input] # 3. 从U3的半字节中提取输出掩码对应的比特和 u3_bit_sum (output_mask u3_nibble).bit_count() % 2 # Python 3.10 # 或者用 bin(output_mask u3_nibble).count(1) % 2 # 4. 检验线性逼近式是否成立 if (plain_sum ^ u3_bit_sum) 0: count 1 # 计算观察到的偏差 bias_obs abs(count / N - 0.5) if bias_obs max_bias_obs: max_bias_obs bias_obs best_guess key_guess return best_guess, max_bias_obs5.4 攻击扩展与密钥还原成功恢复一个4位的子密钥块后我们可以攻击其他半字节寻找其他线性特征攻击最后一轮密钥的其他半字节。由于SPN结构每轮的列混合将比特扩散到不同列攻击不同位置的S盒可能需要不同的线性特征但方法类似。验证与整合将所有恢复的最后一轮子密钥片段组合起来形成完整的最后一轮密钥K4的猜测。反推主密钥根据我们设计的密钥编排算法key_schedule从K4反向推导主密钥。由于密钥编排算法通常不是完全可逆的尤其是包含非线性S盒时可能需要结合多个轮密钥的信息或者进行一个较小范围的搜索例如对主密钥未知的少量比特进行暴力破解最终确定唯一的80位主密钥。实操心得攻击成功的关键在于数据量。理论偏差ε决定了所需明文对数量N大约与1/ε^2成正比。如果偏差为0.25大约需要几十对明文就能以较高概率区分正确密钥如果偏差只有0.01则需要上万对。在实际运行攻击代码时一定要用统计显著性检验如计算|T/N - 0.5|与理论偏差的接近程度或观察其与第二名候选值的差距是否明显。攻击过程就像侦探破案线索线性特征越清晰偏差越大需要的证据明文对就越少破案速度就越快。6. 常见问题与排查技巧实录在整个设计、实现和攻击的过程中我遇到了不少坑。这里把一些典型问题和解决方法记录下来希望能帮你节省时间。问题一加密/解密结果不对或者加密后再解密无法还原明文。排查思路这是最常见的问题。务必分模块测试。单元测试单独测试sub_bytes和inv_sub_bytes确保它们是互逆的。随机生成1000个半字节输入验证inv_sub_bytes(sub_bytes(x)) x。行移位测试手动构造一个状态矩阵应用shift_rows和inv_shift_rows打印出矩阵观察是否正确。列混合测试这是重灾区。首先确保你的mix_columns和inv_mix_columns矩阵在GF(2^4)上确实是互逆的写个函数验证矩阵相乘是否为单位矩阵。其次仔细检查位操作确保从状态中提取列、进行矩阵乘法、再写回状态的过程行列索引没有错乱。强烈建议编写一个state_to_matrix和matrix_to_state的辅助函数并在列混合前后打印矩阵进行肉眼比对。密钥编排测试验证密钥编排算法是否可逆如果设计为可逆或者至少验证每一轮的轮密钥是否都不同且没有明显的模式。问题二线性攻击时统计结果不显著正确密钥的偏差不是最大的。可能原因及解决数据量不足这是最可能的原因。增加已知明文对的数量N。根据偏差大小N可能需要从几千到几十万不等。线性特征偏差太小或无效你选择的S盒输入/输出掩码对可能在实际的多轮路径中偏差被其他操作尤其是线性变换削弱或抵消了。需要重新分析线性掩码的传播路径或者尝试寻找偏差更大的S盒逼近对。代码bug检查攻击代码中明文侧比特和plain_sum的计算是否正确是否与线性特征严格对应。检查部分解密过程inv_shift_rows和inv_sub_bytes是否正确特别是当攻击涉及多个S盒时密钥猜测和部分解密的范围是否正确。密钥编排的影响你的线性特征可能涉及了第一轮或中间轮的密钥比特。这些密钥比特与最后一轮密钥猜测是独立的吗如果它们之间存在线性关系由于简单的密钥编排可能会引入干扰。需要确保你的统计模型正确地处理了这些常数偏差。问题三攻击恢复出的子密钥片段组合后无法正确解密。排查思路验证单个片段用恢复出的子密钥片段单独对它所负责的那个半字节进行部分解密并验证线性逼近式是否成立。如果不成立说明该片段的攻击可能失败了。检查特征独立性攻击不同半字节所使用的线性特征是否相互独立如果它们依赖于相同的中间比特可能会相互影响。理想情况下应使用彼此独立的线性特征。考虑算法其他部分你的算法是否有初始置换或最终置换攻击时是否考虑进去了最后一轮是否真的没有列混合确认算法实现与攻击假设完全一致。尝试其他特征如果当前特征效果不好可以回到S盒的线性逼近表寻找其他偏差大的掩码对构造新的线性特征路径。这个项目做下来最大的体会是密码学是一门非常严谨的工程学科。设计和攻击是一个硬币的两面自己设计算法时觉得“这里加个非线性应该很安全”等到自己动手攻击时才发现一个微小的设计疏忽比如S盒的某个特性、密钥编排的简单线性就可能被无限放大成为致命的漏洞。真正理解了“为什么AES的S盒要那样设计”、“为什么轮数不能太少”这种理解是看书看论文无法替代的。最后记得所有代码和实验都只是用于学习和研究目的加深对原理的理解才是核心价值所在。