现代密码学复习地图：四层骨架与高频习题解析

简介：这份资源是清华大学杨波《现代密码学》第4版的配套习题与参考答案文档，面向高校密码学课程学习者、考研复习者及需要巩固古典密码体制计算方法的读者，用于课后练习自测与解题思路对照。压缩包内共1个docx文件，约1.61MB，以习题题干加完整解答的形式编排，覆盖仿射变换、多表代换密码等核心考点。内容从具体算例展开：如对明文“THE NATIONAL SECURITY AGENCY”做E11,23(m)≡11m+23(mod 26)加密并用逆元19验证解密，由已知明文前两字符反推密钥a=9、b=10，以及用矩阵A、B完成多表代换的分组加密与A⁻¹解密验证，还涉及3级线性反馈移位寄存器的输出序列与周期分析。解答过程保留模26运算、求逆元、分组矩阵运算等关键步骤，便于读者对照检查自己的推导。目前已有5680人学习，适合需要系统刷题、理清古典密码计算细节的读者参考。

1. 现代密码学复习地图：从古典代换到公钥体制的四层骨架

翻开现代密码学的习题册，很多人第一反应是“公式太多、符号太密”，但真正梳理下来会发现，整门课其实只有四层骨架：第一层是古典密码的数学化表达，仿射变换、多表代换把字母变成模运算；第二层是流密码，线性反馈移位寄存器（LFSR）用递推关系生成密钥流，m 序列的周期与游程是核心；第三层是分组密码，DES 与 SM4 靠 Feistel 结构和轮函数实现混淆扩散，工作模式决定错误传播；第四层是公钥密码，RSA 建立在模逆、欧拉定理与中国剩余定理之上。这份笔记把习题里反复出现的计算套路、证明思路和易错点按这四层重新排布，适合正在系统学现代密码学、准备期末或考研复习的人，拿来就能对照查漏补缺。

2. 古典密码：仿射变换与多表代换的计算套路

古典密码在现代密码学教材里不是历史陈列，而是模运算的训练场。仿射变换和多表代换这两类题，几乎每年都以计算题形式出现，套路固定、步骤清晰，但细节上翻车的概率不低。把这两类题的解法拆成可复现的流程，比死记公式有用得多。

2.1 仿射变换：加密、解密与模逆元

仿射变换的加密形式是 E(m) ≡ a·m + b (mod 26)，解密形式是 D(c) ≡ a⁻¹·(c − b) (mod 26)。关键在于 a 必须与 26 互素，否则逆元不存在，解密无从谈起。以习题中 a=11、b=23 为例，11 与 26 互素，逆元通过 11×19 ≡ 1 (mod 26) 得到 19。整个流程可以固化成三步：字母转数字（A=0 到 Z=25）、逐字符代入公式、数字转回字母。

# 仿射变换加密与解密的最小实现 def affine_encrypt(text, a, b): nums = [ord(ch) - ord('A') for ch in text if ch.isalpha()] return [(a * m + b) % 26 for m in nums] # 逐字符模26 def affine_decrypt(cipher_nums, a, b): a_inv = pow(a, -1, 26) # Python 3.8+ 直接求模逆元 return [(a_inv * (c - b)) % 26 for c in cipher_nums] c = affine_encrypt("THENATIONALSECURITYAGENCY", 11, 23) m = affine_decrypt(c, 11, 23) print(''.join(chr(x + ord('A')) for x in m)) # 还原明文

这段代码里pow(a, -1, 26)是求模逆元最省事的方式，等价于习题里“欧几里得算法或穷举 1~25”的手工过程。参数 a 必须满足 gcd(a,26)=1，可选值只有 1、3、5、7、9、11、15、17、19、21、23、25 共 12 个，b 可取 0~25 任意值。手工计算时最容易错的是负数取模，比如 (c−23) 为负时要先加 26 再乘逆元，顺序颠倒结果就全错。

第二类仿射题是“已知明文前两个字符反求密钥”。习题中密文前两位 ed 对应明文 if，列出两个同余方程 4 ≡ 8a+b、3 ≡ 5a+b (mod 26)，相减得 1 ≡ 3a (mod 26)，解得 a=9、b=10。这类题的重点不是解方程本身，而是验证解出的 a 是否与 26 互素——9 与 26 互素，逆元为 3，解密才成立。如果解出的 a 不互素，说明题设或计算有误，这是检查答案的第一道关口。

2.2 多表代换：矩阵密钥与分组运算

多表代换把明文按 4 个一组（或与矩阵阶数一致）分组，加密为 Cᵢ ≡ A·Mᵢ + B (mod 26)，其中 A 是 n×n 矩阵，B 是 n 维向量。解密需要 A 的模 26 逆矩阵 A⁻¹，满足 A·A⁻¹ ≡ I (mod 26)。习题里 A 是 4×4 矩阵、B 是 4 维向量，加密时先分组再逐组做矩阵乘加，解密时用 A⁻¹ 左乘 (Cᵢ − B)。

矩阵求逆在模 26 下比实数域麻烦：先算行列式 det(A)，求 det(A) 模 26 的逆元，再用伴随矩阵乘以该逆元。习题中 A⁻¹ 已直接给出，复习时要能自己验证 A·A⁻¹ ≡ I，这是判断矩阵是否可逆的唯一标准。另一个高频题是“已知明文 dont 加密为 elni，求 2×2 矩阵 A”，本质是解矩阵方程，把两组明密文对列成四个同余方程联立求解，解出后同样要验证 det(A) 与 26 互素。

梳理下来会发现，古典密码题的共同点是“一切运算在模 26 下进行”，加、减、乘、求逆都要带 mod 26，手工计算时建议每步都写余数，避免中间结果越算越大导致符号错误。这部分在考试中属于送分题，但送分题丢分往往就丢在模运算的细节上。

3. 流密码：LFSR 的递推、周期与 m 序列性质

流密码这一章的习题集中在 LFSR 的序列生成、周期判定和 m 序列的统计性质上。表面看是递推计算，实际考的是对“特征多项式—序列周期—游程分布”这条逻辑链的理解。把这条链拆开，每类题都有固定的切入点。

3.1 LFSR 递推与特征多项式

n 级 LFSR 的递推关系是 aₙ₊ₖ = c₁aₙ₊ₖ₋₁ ⊕ c₂aₙ₊ₖ₋₂ ⊕ … ⊕ cₙaₖ，特征多项式为 f(x) = 1 + c₁x + … + cₙxⁿ。给定初始状态和反馈函数，逐位递推就能得到输出序列。习题中 3 级 LFSR 在特定条件下有 4 种线性反馈函数，对应 4 条不同的输出序列，周期分别为 1、3、7 等，其中特征多项式不可约且本原时周期达到最大值 2ⁿ−1，即 m 序列。

# 3级LFSR：反馈抽头由特征多项式决定 def lfsr(seed, taps, steps): state = seed[:] out = [] for _ in range(steps): out.append(state[-1]) # 输出最右位 fb = 0 for t in taps: # 抽头位置异或 fb ^= state[t] state = [fb] + state[:-1] # 右移并填入反馈位 return out # 特征多项式 x^3+x+1 对应抽头 (0,2)，初态 101 seq = lfsr([1,0,1], [0,2], 14) print(seq) # 周期应为 7

代码中taps对应特征多项式中系数为 1 的项位置，state[-1]是当前输出位。判断周期的方法是把输出序列与自身平移比较，第一次重合的平移量就是周期。手工计算时，初态不能全零，否则输出恒为 0，周期为 1，这是最容易被忽略的边界情况。

证明“输出序列周期等于特征多项式阶”这类题，核心是构造生成函数并利用 f(x) 整除 xᵀ−1 的最小 T。习题中的证明思路是：设序列最小周期为 p，由递推关系可得 (xᵖ−1) 与 f(x) 的关系，再结合次数比较得出 p 等于 f(x) 的阶。复习时不必背完整证明，但要记住结论：f(x) 不可约时序列周期等于 f(x) 的阶，f(x) 本原时周期为 2ⁿ−1。

3.2 m 序列的游程分布与比特对计数

m 序列的统计性质是流密码的另一个考点。n 级 m 序列周期为 2ⁿ−1，其中长为 i 的游程有 2ⁿ⁻ⁱ⁻¹ 个，0 游程和 1 游程各占一半。习题中要求统计形如 (Sⱼ, Sⱼ₊₁)=(1,1) 的比特对数量，答案 2ⁿ⁻²−n+1 的推导依赖游程计数：每个长为 k 的 1 游程贡献 k−1 个 (1,1) 对，把所有游程的贡献求和再化简。

这类题的易错点在于游程定义：长为 k 的游程指连续 k 个相同比特且两端不同，周期序列首尾相接时还要考虑跨周期的游程。习题中求和式的化简用了错位相减，复习时建议把 n 取小值（如 n=4）手工枚举验证公式，比硬记结论可靠。

破译类题目同样有套路。已知 3 级 LFSR 的明密文对，先异或得到密钥流，再列线性方程组解出反馈系数。习题中密钥流 1110100111 代入递推式，解出 c₁、c₂、c₃ 后即可预测后续密钥。如果只知道 2n−2 位明密文，则需要枚举未知的 2 位，共 16 种组合，逐一检验是否符合 m 序列性质，符合的即为正确密钥流——这种“枚举加性质筛选”的思路在流密码破译题里反复出现。

4. 分组密码：DES 与 SM4 的结构、模式与证明

分组密码是整门课分量最重的一章，DES 的 Feistel 结构、互补性、解密互逆证明，SM4 的对合性证明，以及 ECB/CBC/CFB 的错误传播，都是习题高频区。这一章的题分两类：证明题考结构理解，计算题考模式行为，两者都要求对轮函数的输入输出关系有清晰把握。

4.1 DES 的互补性与解密互逆

DES 的互补性结论是：若 Y = DES_K(X)，则 Y' = DES_K'(X')，即明文和密钥同时取补，密文也取补。证明的关键在于轮函数中扩展后的数据与密钥异或，取补后异或结果不变（因为两个补码异或等于原码异或），S 盒和 P 置换对补码的处理保持对称。这个结论的实际价值在于穷搜索攻击：给定一组明密文，一次试探同时覆盖 K 和 K' 两种情况，密钥空间从 2⁵⁶ 减半到 2⁵⁵。

解密互逆的证明用到了交换函数 T 和对合性。定义 T(L,R)=(R,L)，则 T²=I；轮函数 F_Kᵢ 满足 F_Kᵢ²=I。加密过程写成 IP⁻¹·F_K₁₆·T·…·F_K₁·IP，解密过程把轮密钥倒序排列，利用 (T·F)⁻¹ = F·T 逐层抵消，最终得到恒等变换。复习这个证明时，重点抓住“T 交换左右、F 异或密钥”这两个动作的逆运算性质，比背公式链条更有效。

4.2 工作模式的错误传播

四种模式的错误传播行为是选择题和简答题的常客，用一张表对比最清楚。

CBC 的错误传播长度为什么是 2？因为解密时 Pᵢ = D(Cᵢ) ⊕ Cᵢ₋₁，C₁ 出错会污染 P₁（通过 D(C₁)）和 P₂（通过 C₁ 作为异或项），从 P₃ 起 C₁ 不再参与，错误消失。CFB 的 9 组来自 8 比特移位寄存器的填充过程，1 比特错在寄存器中滚动 8 次后移出，加上当前组共影响 9 组。这些数字不是背出来的，而是从模式的定义式推出来的，复习时自己推一遍比记表格牢。

4.3 SM4 的对合性与 IDEA 的模运算

SM4 的加密轮函数由加密变换 G 和交换 E 组成，G 对合（G²=I），E 也是对合，因此整个轮函数对合。加密过程写成 G₀EG₁E…G₃₁R，解密过程写成 G₃₁EG₃₀E…G₀R，两者运算完全相同，只是轮密钥顺序相反。证明的核心是验证 G 中 T 变换的异或抵消：G(Xᵢ,…,Xᵢ₊₃, rkᵢ) 连续作用两次，T 的输出异或两次归零，回到原状态。

IDEA 的模乘题考的是为什么模数取 2¹⁶+1 而不是 2¹⁶。答案指向群论：模乘要构成群，模数必须是素数，2¹⁶+1=65537 是素数，2¹⁶ 不是；而模加要构成群，模数取 2¹⁶ 即可，且模加与模乘不能在同一群内，否则分配律和结合律的独立性被破坏。习题中关于 ab = q(2ⁿ+1)+r 的六问，本质是推导模 2ⁿ+1 乘法的快速实现：先算普通乘法的商 q 和余 r，再根据 q+r 与 2ⁿ 的大小关系修正结果，r 的最终表达式 r = (ab mod 2ⁿ) − (ab div 2ⁿ) 表示 ab 的低 n 位与高 n 位之差。这类题计算量大，但每一步都有明确的代数依据，按部就班即可。

5. 公钥密码：模逆、中国剩余定理与 RSA 的证明链

公钥密码章的习题围绕数论工具展开：Fermat 定理、Euclid 算法、中国剩余定理、Legendre 符号、本原根，最后汇聚到 RSA 的加解密与加速。这一章的题看似零散，实则是一条“数论工具→RSA 构造→性能优化”的证明链，每一环都为下一环服务。

5.1 数论工具：从模逆到中国剩余定理

扩展 Euclid 算法求逆元是最高频的计算题。习题中用表格迭代 q、x、y、z 四列，最终 x₃=1 时对应的 x₁ 或 y₁ 即为逆元。手工计算时建议每行都写清 q = ⌊a/b⌋、余数更新，避免跳步。Fermat 定理求 aᵖ⁻¹ mod p 的题，关键是先判断模数是否为素数，再用 aᵖ⁻¹ ≡ 1 降幂，比如求 2¹⁰⁰ mod 13，先算 100 mod 12 = 4，再算 2⁴ mod 13。

中国剩余定理的解题模板是：设 M = ∏mᵢ，Mᵢ = M/mᵢ，求 Mᵢ 模 mᵢ 的逆元 yᵢ，解为 x ≡ ΣaᵢMᵢyᵢ (mod M)。习题中的同余方程组按此模板逐步代入即可。Legendre 符号的计算用二次互反律和 (a/p) 的分解性质，本原根的判定则要验证 g^(p−1)/q ≠ 1 (mod p) 对所有素因子 q 成立。这些工具单独看是计算技巧，放到 RSA 里就是密钥生成和解密加速的基础。

5.2 RSA 加解密与 CRT 加速证明

RSA 的基本流程是：选素数 p、q，n=pq，φ(n)=(p−1)(q−1)，选 e 与 φ(n) 互素，d ≡ e⁻¹ (mod φ(n))，公钥 (e,n)，私钥 d。加密 c ≡ mᵉ (mod n)，解密 m ≡ cᵈ (mod n)。习题中给定公钥和密文求明文，直接代入模指数运算即可，计算时用重复平方降低复杂度。

CRT 加速的证明是这一章的难点：原解密运算的运行时间是 O(log³n)，用 CRT 分解到模 p 和模 q 后，每个模指数运算的时间是 O((log n/2)³) = O(log³n/8)，两个加起来是 O(log³n/4)，因此速度提升 4 倍。证明的关键在于“两个大素因子长度近似相等，各为模数比特长度的一半”，这个前提不成立时 4 倍结论不严格。复习时要能说清“为什么是 4 倍而不是 2 倍”——因为三次方关系，模长减半带来 8 倍单次加速，两次运算合计 4 倍。

另一类题是“已知重复平方的中间结果分解 n”。如果敌手拿到 m^(2^k) mod n 的中间值，可以通过 gcd(中间值−1, n) 尝试分解，因为中间值可能恰好是模 p 或模 q 下的 1 的非平凡平方根。这类题考的是 RSA 实现中泄露中间值的危险性，属于安全性分析而非纯计算。

6. 易错点排查：五类最容易翻车的细节

复习到后期，拉开差距的往往不是不会做，而是会做却做错。把习题里反复出现的错误归成五类，每条按“易漏点→为什么漏→怎么补”走一遍，考前对照自查。

易漏点一：模逆元存在性未验证。仿射变换解出 a 后直接套解密公式，忘了检查 gcd(a,26)=1；RSA 中选 e 时忘了与 φ(n) 互素。为什么漏？因为题目通常直接给可逆的参数，形成思维惯性。怎么补？任何涉及除法或求逆的步骤，先写一行 gcd 判断，不互素立即回头检查前序计算。

易漏点二：负数取模顺序错误。仿射解密 (c−b) 为负时，先乘逆元再取模与先取模再乘逆元结果不同。为什么漏？手工计算时负数符号容易丢。怎么补？统一写成 ((c−b) % 26 + 26) % 26 再乘逆元，代码里用 Python 的 % 天然处理负数，手工算时先加 26 的倍数转正。

易漏点三：LFSR 初态全零与周期边界。判断周期时忽略全零初态导致输出恒零，或把周期 1 误判为异常。为什么漏？教材例题多用非零初态。怎么补？拿到 LFSR 题先看初态是否全零，全零直接写周期 1；非零则用平移比对法求最小周期。

易漏点四：工作模式错误传播长度记混。CBC 记成影响 1 组、CFB 记成影响 8 组。为什么漏？数字相近且缺乏推导。怎么补？从解密定义式现场推：CBC 的 Pᵢ 依赖 Cᵢ 和 Cᵢ₋₁，故影响 2 组；CFB 的寄存器长度决定滚动次数，8 比特模式影响 9 组。推一遍比背十遍牢。

易漏点五：CRT 加速的 4 倍结论前提缺失。直接写“CRT 加速 4 倍”而不说明 p、q 长度近似相等。为什么漏？结论被当作定理记。怎么补？答题时补一句“在 p、q 比特长度近似相等且不计 CRT 合并代价的前提下”，这是证明完整性的得分点。

提示：以上五条建议在考前一周每天挑两条，用习题原题重做一遍，重点看自己是否在相同位置再次出错。

7. 复习清单：按题型归类的查漏补缺法

复习现代密码学最怕的是“书看了三遍，题还是不会”。我的做法是把习题按题型而非章节归类，每类题提炼一个固定动作，考前只练动作不刷全书。下面这张清单按四层骨架展开，每行给出题型、核心动作和自检标准，照着走一遍就能定位薄弱环节。

具体执行分三步。第一步，拿一张白纸默写四层骨架和每层的核心公式，写不出来的就是盲区，回到对应章节补。第二步，从习题里每类挑两道原题限时重做，重点不是做对，而是看步骤是否完整——模逆验证、负数处理、前提说明这些细节有没有漏。第三步，把做错的题按上面的五类易错点归档，考前只看错题归档，不再翻新题。

# 复习节奏建议：按天分配，不贪多 第1天：古典密码计算题 4 道 + 模逆验证习惯 第2天：LFSR 序列生成与周期判定 3 道 第3天：DES 证明 2 道 + 模式传播推导 第4天：数论工具 5 道（模逆、CRT、Legendre） 第5天：RSA 加解密与加速证明 2 道 第6天：错题归档重做 + 骨架默写

这套节奏的关键在于“每天只攻一层”，避免四层混着看导致每层都半生不熟。错题归档那一步尤其重要，因为现代密码学的错误高度重复，同一个模运算细节可能在不同题里错三次，归档后一眼就能看出自己的固定翻车点。

从那以后我每次复习这类偏证明和计算的课，都强制先默写骨架再刷题，做完每道计算题必回头验证逆元或周期，绝不让“看起来会了”蒙混过去。希望这份梳理能帮你在考前把地图装进脑子，而不是把公式塞进短期记忆。

本文还有配套的精品资源，点击获取