密码学习题精解：从仿射变换到RSA的完整演算链与代码验证-北京尧图网络

简介这份资源是清华大学杨波《现代密码学》第4版的配套习题与参考答案文档面向高校密码学课程学习者、考研复习者及需要巩固古典密码与现代密码学基础的读者可用于课后练习对照、期末备考与知识点自查。压缩包内共1个docx文件约1.61MB内容按教材章节组织涵盖仿射变换、多表代换密码、线性反馈移位寄存器等典型题型。以第1章为例文档完整给出仿射变换 E(m)≡11m23(mod 26) 的加密与解密验证过程包括模逆元求解、密文与明文字符串的逐位计算还演示了由已知明文前两字符反推密钥、多表代换中矩阵 A 与向量 B 的构造及 A⁻¹ 解密验证并附有求解 2×2 矩阵 A 的完整推导。第2章则涉及3级线性反馈移位寄存器的反馈函数、输出序列与周期分析。已有5680人学习适合需要按章节刷题、核对解题步骤与理解计算细节的读者使用。1. 一份能对着敲的密码学习题集从仿射变换到 RSA 的完整演算链期中考前一周某高校密码学课程群里最常出现的消息不是“老师划重点”而是“第 4 章第 12 题那个中间结果到底怎么分解”。现代密码学这门课的特点很鲜明概念听懂了题还是不会做公式看明白了手算还是对不上。这份《现代密码学第 4 版》习题参考答案覆盖了从古典密码的仿射变换、多表代换到流密码的 LFSR 序列分析再到 DES、IDEA、SM4 的分组密码论证最后落到 RSA 与中国剩余定理的数论计算是一条完整的演算链。它适合两类人正在跟课、需要对照步骤把每道题走通的学生以及想快速回顾古典密码到公钥密码核心推导的从业者。下面不按章节顺序复述答案而是把这份材料里真正容易翻车的几个技术点拆开讲清楚每一步为什么这么算、参数怎么定、错在哪。2. 仿射变换与多表代换模 26 运算的三个死穴古典密码部分看起来最简单实际上手算错误率最高。仿射变换 (E_{a,b}(m) \equiv amb \pmod{26}) 和解密 (D_{a,b}(c) \equiv a^{-1}(c-b) \pmod{26}) 只有两个参数但这两个参数背后藏着三个必须过的坎模逆元是否存在、负数取模怎么处理、字母到数字的映射是否统一。2.1 模逆元先判 gcd再谈求解仿射变换能解密的前提是 (a) 在模 26 下可逆也就是 (\gcd(a,26)1)。26 的因子是 2 和 13所以 (a) 不能是偶数也不能是 13 的倍数。材料里第一题取 (a11)第二题反推出 (a9)都满足这个条件。求逆元有两条路扩展欧几里得算法或者直接穷举 1 到 25。穷举在模 26 这种小模数下完全够用材料里也是这么提示的。我一般会写个小脚本把逆元表一次性打出来避免每次手算出错# 模 26 下的乘法逆元表只保留与 26 互素的 a def mod_inverse(a, m): for x in range(1, m): if (a * x) % m 1: return x return None inverse_table {a: mod_inverse(a, 26) for a in range(1, 26) if mod_inverse(a, 26)} print(inverse_table) # 输出包含 11: 19, 9: 3, 5: 21 等可直接对照手算结果这段代码的逻辑很直白对每个候选 (x) 检查 (a \cdot x \bmod 26) 是否为 1。参数m固定为 26因为英文字母表长度就是 26如果换成 27 个符号含空格的字母表模数和逆元表都要整体重算这是很多人抄答案时忽略的前提。材料第一题里 (11 \times 19 209 8 \times 26 1)所以 (11^{-1}19)这个验证步骤建议每次都写出来考试时也是得分点。2.2 负数取模Python 和手算的差异解密公式里有 (c-23) 这种减法结果可能是负数。手算时习惯“加 26 直到为正”但写代码时不同语言的取模行为不一样。Python 的%对负数返回非负结果C 和 Java 则可能返回负数。材料里大量出现 (19 \times (c-23) \bmod 26) 这类运算如果直接照搬到 C 语言里会出现负的明文字母下标。稳妥写法是先加模数再取模def affine_decrypt(c_list, a_inv, b, m26): # 先做 (c - b) % m 保证非负再乘逆元并再次取模 return [ (a_inv * ((c - b) % m)) % m for c in c_list ] cipher [24,22,15,10,23,24,7,21,10,23,14,13,15,19,9,2,7,24,1,23,11,15,10,19,1] plain affine_decrypt(cipher, 19, 23) print(.join(chr(p ord(A)) for p in plain)) # 输出 THENATIONALSECURITYAGENCY参数说明a_inv是加密参数 (a) 的逆元b是加密时的偏移量解密时减的是同一个 (b)不是 (-b) 的逆元这一点初学者经常搞混。输出里没有空格因为材料在数字化时把空格去掉了还原成人读文本时需要按语义补空格这一步没有算法能替你做。2.3 多表代换矩阵可逆性与分组补齐多表代换 (C_i \equiv A M_i B \pmod{26}) 把单个字母的运算升级成矩阵运算坑也随之升级。第一矩阵 (A) 必须在模 26 下可逆判据是 (\det(A)) 与 26 互素第二明文要按矩阵维度分组不足一组要补齐材料里第四题用 4 维向量分组最后一组不足 4 个字符时补了什么、补了之后解密怎么去掉答案里没有展开实际做题必须自己定规则。第三矩阵乘法不满足交换律(A M_i) 的顺序不能反。材料第三题给出的 (A^{-1}) 是一个 4×4 矩阵直接用于验证。手工验证时建议先算 (A \cdot A^{-1} \bmod 26) 是否等于单位矩阵这一步能提前发现抄错数字import numpy as np A np.array([[3,13,21,9],[15,10,6,25],[10,17,4,8],[12,3,7,2]]) A_inv np.array([[23,13,20,5],[0,10,11,0],[9,11,15,22],[9,22,6,25]]) prod (A A_inv) % 26 print(prod) # 期望接近单位矩阵若某元素不为 0/1说明矩阵抄录或模运算有误这里用 NumPy 只是为了快速验算考试手算时按行乘列展开即可。注意是矩阵乘*是逐元素乘混用会导致结果完全错误。材料里密文分组后出现NQXB BTWB DCJJ这样的四字母块解密时同样按四字母一组处理组与组之间独立这也是多表代换相比流密码的一个特点错误不会跨组传播但分组边界一旦错位后面全错。3. LFSR 序列分析从特征多项式到密钥流破译流密码章节的题目集中在 LFSR 的周期、m 序列性质和已知明文攻击。这部分是整份材料里推导密度最高的也是考试中最容易“看懂答案但自己推不出来”的部分。核心就一句话n 级 LFSR 的一切行为都由特征多项式决定周期、序列结构、可破译性都挂在它上面。3.1 特征多项式与周期先判不可约再谈 m 序列材料第 2 章第 1 题问 3 级 LFSR 有几种线性反馈函数、各自输出序列和周期。3 级意味着特征多项式是 3 次系数在 GF(2) 上取值常数项必须为 1否则退化成低阶所以候选只有 4 个。逐个判断是否不可约、本原才能确定哪些产生 m 序列、周期为 (2^3-17)。这里的关键概念链是不可约多项式保证序列周期整除 (2^n-1)本原多项式才保证周期恰好等于 (2^n-1)。很多人把“不可约”直接当成“m 序列”这是典型误判。验证一个 3 次多项式是否本原可以手算 (x^{2^3-1} \bmod f(x)) 是否为 1且对 7 的真因子 1 不成立。更实际的做法是直接跑序列def lfsr_sequence(taps, init, steps): # taps: 反馈抽头系数列表长度等于级数 # init: 初始状态列表最高位在前 state init[:] seq [] n len(state) for _ in range(steps): seq.append(state[-1]) feedback sum(taps[i] * state[i] for i in range(n)) % 2 state [feedback] state[:-1] return seq # 例f(x)x^3x1 对应抽头 (1,1,0)初态 (1,0,1) seq lfsr_sequence([1,1,0], [1,0,1], 14) print(seq) # 观察前 7 位是否循环循环即周期为 7参数taps的顺序要和状态向量对齐材料里不同题目的状态排列方向不完全一致抄的时候必须确认“哪一端是输出位”。steps取两倍周期就够看出循环。如果序列在 7 步内没有回到初态说明多项式不是本原的或者抽头抄错了。3.2 已知明文破译2n 比特够不够材料第 6 题给了一段 10 比特的密钥流3 级 LFSR要求破译。3 级需要 6 个未知系数含常数项10 个比特足够列方程组。第 7 题更进一步只知道 (2n-2) 个明密文对时怎么办答案是枚举最后 2 个未知比特的 4 种取值凑出 (2n) 长度再解最后用 m 序列性质筛掉不合法的解。这个思路在实战里对应的是“密钥流短于理论需求时的穷举补全”代价是解可能不唯一。用矩阵形式写出来更清楚。设密钥流为 (s_0,s_1,\dots)递推关系 (s_{in} \sum_{j0}^{n-1} c_j s_{ij})取连续 (n) 个方程解 (c)import numpy as np def solve_lfsr_coeffs(bits, n): # bits 长度至少 2n取前 n 个方程 M np.array([[bits[ij] for j in range(n)] for i in range(n)], dtypeint) y np.array([bits[in] for i in range(n)], dtypeint) # 在 GF(2) 上解线性方程组这里用模 2 高斯消元 aug np.hstack([M, y.reshape(-1,1)]) % 2 rows, cols aug.shape r 0 for c in range(cols-1): pivot next((i for i in range(r, rows) if aug[i,c]), None) if pivot is None: continue aug[[r,pivot]] aug[[pivot,r]] for i in range(rows): if i ! r and aug[i,c]: aug[i] (aug[i] aug[r]) % 2 r 1 return aug[:, -1].tolist() key_stream [1,1,1,0,1,0,0,1,1,1] coeffs solve_lfsr_coeffs(key_stream, 3) print(coeffs) # 得到反馈系数再回代验证后续比特是否吻合这段代码的价值不在结果而在流程先列方程、再模 2 消元、最后回代验证。材料第 6 题的答案直接给了递推关系但没展示消元过程自己补一遍才能应对变体题。注意bits的顺序必须和递推方向一致反向取位会得到完全不同的系数。3.3 m 序列的游程性质比特对计数怎么推第 5 题问周期为 (2^n-1) 的 m 序列中有多少个 ((1,1)) 比特对答案是 (2^{n-2}-n1)。这个结论来自游程分布长度为 (i) 的 1 游程有 (2^{n-i-1}) 个每个长度为 (i) 的游程贡献 (i-1) 个 ((1,1)) 对求和后得到闭式。推导里用了错位相减材料写得很紧凑手推时建议把 (n4) 的具体情况列出来对一遍周期 151 游程分布为长度 1 有 4 个、长度 2 有 2 个、长度 3 有 1 个((1,1)) 对数为 (0224)代入公式 (2^{2}-411)这里要小心公式里的 (n) 和游程长度的对应关系容易错位实际核算应以逐项展开为准。这类题最稳的办法是小规模枚举验证公式再推广。4. 分组密码论证DES、IDEA、SM4 的对合性与错误传播分组密码部分的题目以证明为主看起来抽象但每道证明都对应一个实际设计问题DES 的补性质能不能减少穷举空间、CBC 的错误传播有多长、IDEA 为什么选 (2^{16}1) 做模乘、SM4 为什么加密解密可以共用一套轮函数。这些结论在写代码实现算法时直接决定你怎么组织轮结构和密钥调度。4.1 DES 补性质密钥空间砍半的代价材料第 3 章第 1 题证明若 (Y DES_K(X))则 (\overline{Y} DES_{\overline{K}}(\overline{X}))。证明的关键是轮函数中扩展、异或、S 盒、P 置换对补运算的传递性其中异或那一步满足 ((\overline{A} \oplus \overline{B}) A \oplus B)所以补运算穿过轮函数后只翻转数据、不改变轮密钥的作用方式。这个性质的实际意义是穷举时对每个候选密钥 (K)同时检验 (DES_K(X)) 和 (DES_{\overline{K}}(\overline{X}))一次搜索覆盖两个密钥密钥空间从 (2^{56}) 降到 (2^{55})。但要注意边界这只在明文和密钥同时取补时成立单独补明文或单独补密钥都不行。写验证脚本时两组输入必须成对构造# 伪代码示意成对检验实际需接入 DES 实现 def complement_attack_check(des_func, plaintext, key): c1 des_func(plaintext, key) c2 des_func(complement(plaintext), complement(key)) assert c2 complement(c1), 补性质不成立检查实现 return Truecomplement是按比特取反长度与分组一致。这个断言在自实现 DES 时是很好的单元测试能快速暴露 S 盒或 P 置换写错的问题。4.2 CBC 与 CFB 的错误传播长度第 3 题和第 4 题问错误传播。CBC 模式下密文分组 (C_1) 出错解密后 (P_1) 和 (P_2) 受影响从 (P_3) 开始恢复传播长度为 2因为 (P_i D(C_i) \oplus C_{i-1})错误只通过相邻的 (C_{i-1}) 传递一次。CFB-8 模式下 1 比特密文错误会影响连续 9 组解密输出原因是反馈路径把错误带进了移位寄存器寄存器长度 8 字节加当前组共 9 组。这两个数字在选模式时很关键文件传输容忍局部错误选 CBC实时流怕延迟选 CFB 但要接受更长的错误尾巴。材料第 3 题第 (2) 问还问明文错误的影响CBC 下 (P_1) 错一个比特后续所有密文分组都错但解密后只有 (P_1) 错其余明文正确恢复。这个“密文全错、明文只错一组”的非对称性是 CBC 自恢复能力的另一面设计校验机制时不能只看密文完整性。4.3 IDEA 模乘与 SM4 对合性群结构决定参数IDEA 用 (2^{16}1) 做模乘、(2^{16}) 做模加材料第 6 题解释了原因模乘要构成群模数必须是素数(2^{16}165537) 是素数模加要构成群(2^{16}) 就够且不能和模乘同群否则分配律会破坏算法结构。第 5 题进一步给出模 (2^{16}1) 乘法的快速实现利用 (ab q(2^n1)r) 的关系把大数乘法转成低位和高位的加减避免真正的除法。这个技巧在资源受限设备上实现 IDEA 时很实用。SM4 的对合性证明第 7 题核心是轮函数 (G) 满足 (G \circ G I)数据交换 (E) 也满足 (E^2 I)所以加密轮序列反过来就是解密轮序列只需把轮密钥倒序使用。写 SM4 实现时这意味着加密和解密可以共用同一个round_function只改密钥调度顺序def sm4_crypt(block, rk, decryptFalse): # rk: 32 个轮密钥decryptTrue 时倒序使用 keys rk[::-1] if decrypt else rk x block for i in range(32): x round_function(x, keys[i]) return x参数rk必须是完整 32 轮密钥少一轮对合性就不成立。这个结构也让代码审计变简单只要验证加密路径正确解密路径的正确性由对合性保证不需要单独测。5. 数论与 RSA中国剩余定理加速和中间结果分解第 4 章是整份材料里计算量最大的部分从 Fermat 小定理、扩展欧几里得、中国剩余定理一路到 RSA 解密加速和中间结果攻击。这些题目对应的是公钥密码实现中最常见的性能优化和侧信道风险做工程的人看这一章会比看古典密码更有代入感。5.1 扩展欧几里得求逆元表格法别抄错行材料第 4 题用扩展欧几里得求逆元给了一张循环表列是 (q, x_1, x_2, x_3, y_1, y_2, y_3)。手算时最常见的错误是 (q) 取整方向搞反或者 (x)、(y) 两组更新时串行。稳妥做法是固定迭代格式每轮 (q \lfloor x_3 / y_3 \rfloor)然后 ((x_1,x_2,x_3) \leftarrow (y_1,y_2,y_3))((y_1,y_2,y_3) \leftarrow (x_1 - q y_1, x_2 - q y_2, x_3 - q y_3))。用代码跑一遍对照表格比反复检查手算快得多def extended_gcd(a, b): # 返回 (g, x, y) 使得 ax by g old_r, r a, b old_s, s 1, 0 old_t, t 0, 1 while r: q old_r // r old_r, r r, old_r - q * r old_s, s s, old_s - q * s old_t, t t, old_t - q * t return old_r, old_s, old_t g, x, y extended_gcd(19, 26) print(g, x % 26) # g1, x%26 即 19 在模 26 下的逆元old_r最终是 gcdold_s是 (a) 的系数取模后就是逆元。材料表格里的 (x_3) 列对应这里的old_r序列逐行对照能快速定位抄错的位置。5.2 中国剩余定理加速 RSA4 倍从哪来第 11 题证明 CRT 加速后 RSA 解密快 4 倍。推导逻辑是模数 (n pq)(p) 和 (q) 各约 (n) 的一半比特长模指数运算时间与模长三次方成正比所以分别在模 (p)、模 (q) 下做指数运算每个耗时约为原来的 ((1/2)^3 1/8)两个加起来 (1/4)即速度提升 4 倍。这个估算忽略了 CRT 合并的计算代价实际实现中提升通常在 3 到 4 倍之间取决于合并步骤的优化程度。实现时要注意 (p) 和 (q) 的逆元预计算def rsa_decrypt_crt(c, p, q, dp, dq, q_inv): # dp d mod (p-1), dq d mod (q-1), q_inv q^{-1} mod p m1 pow(c, dp, p) m2 pow(c, dq, q) h (q_inv * (m1 - m2)) % p return m2 h * qdp、dq、q_inv都是密钥生成阶段算好存下来的解密时不再做除法。参数顺序不能乱q_inv是模 (p) 的逆元不是模 (n) 的。这套结构也是很多硬件 RSA 加速器的标准数据通路。5.3 中间结果攻击一次平方泄露就够分解 n第 12 题描述的场景是敌手拿到 RSA 加密过程中重复平方的中间结果如何分解 (n)。原理是如果某个中间结果 (a) 与 (n) 不互素那么 (\gcd(a,n)) 直接给出 (p) 或 (q)。即使中间结果本身不泄露因子两个不同底数的中间结果之差也可能与 (n) 共享因子。防御手段是盲化加密前把明文乘一个随机数 (r^e)解密后再乘 (r^{-1})让中间值随机化。这道题在材料里只给了开头完整推导需要结合具体中间结果列表做题时把每个中间结果都和 (n) 求一次 gcd是最直接的检查方法。6. 把答案变成可验证脚本三个我每次都会跑的自检对着答案抄一遍和把答案变成能跑的验证脚本是两种完全不同的掌握程度。这份材料里的题目有一个共同点几乎每道题都能用几十行代码复现而且复现过程中暴露的错误比看答案多得多。我自己的习惯是每做完一章就写三个自检跑通了才算过。第一个自检是模运算一致性。古典密码和数论部分的答案全是模运算把每道题的中间结果用脚本重算一遍和材料里的数字逐个比对。比如仿射变换那题密文数组有 25 个元素手抄错一个数字后面全错脚本比对能秒级定位。第二个自检是对合性断言。DES 补性质、SM4 加解密互逆、IDEA 模乘群性质这些都能写成assert实现写错时立刻炸出来比肉眼检查轮函数可靠。第三个自检是小规模穷举验证公式。m 序列比特对计数、LFSR 周期、CRT 加速倍数这些闭式结论在 (n) 较小时可以暴力枚举枚举结果和公式对不上说明公式里的下标或边界条件理解错了。自检项覆盖章节验证方式常见失败原因模运算一致性第 1、4 章脚本重算中间结果并比对负数取模、逆元抄错对合性断言第 3 章加密后解密断言等于原文轮密钥顺序、S 盒错位小规模穷举第 2 章枚举序列与公式对比状态方向、游程定义这三个自检跑下来一份习题答案才真正变成自己的东西。血泪经验是不要等整章看完再验证每道题做完立刻跑错误不会累积。从那以后我每次拿到这类演算型资料都强制先写一个最小验证脚本再往下读希望帮到你。本文还有配套的精品资源点击获取

密码学习题精解：从仿射变换到RSA的完整演算链与代码验证

相关推荐

GitHub Actions自动化工作流实战指南

连接追踪技术原理与性能优化实践

连接追踪技术解析：原理、优化与实战案例

更多资讯

模电面试高频考点：从三极管耦合到运放反馈稳定性

Claude会话记忆增强：用claude-mem打造跨会话长期记忆

一文搞懂三个ECC：椭圆曲线密码学原理与SAP LSMW迁移实战

从形容词到交付标准：拆解“完美无瑕”的产品细节方法论

高效图片查找工具与技术方案全解析

SAP ECC企业级ERP系统核心解析：架构、模块与实操

今日更新

微信个人号API开发案例：图片/语音/视频消息怎么下载解析存到本地？

Python股票自动交易系统源码解析：从行情获取到风控的完整链路

视酷酷信IM源码部署指南：Java 17+MySQL 8.0.33实战配置

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？