密码学：期中指定课后习题全解析（31 题）

本篇全面覆盖期中指定演练的 31 道经典课后题。题设参数均已严格核对校正，计算推导自洽完备，无需频繁翻阅教材即可独立完成推导与复习。

建议结合理论篇章对照复习：第1至2章基础解析 $\to$ 第3至5章对称密码解析 $\to$ 第6至7章数论与RSA解析。全局学习地图参见 密码学学习导航。

章节分类	覆盖典型题号	核心考查主线
第1章	1.1、1.2、1.5、1.7、1.9	单表代换统计分析、移位密码、同余模运算与乘法逆元判据
第2章	2.1(1)(2)、2.5、2.8	序列密码逐字加密、LFSR 状态递推时序、特征多项式与状态转移环分析
第3章	3.1、3.3、3.4、3.5、3.6、3.9	DES S盒查表规范、首轮数据流展开、单比特雪崩效应传播、穷举密钥空间计算
第4章	4.4、4.5、4.6、4.7	$\mathrm{GF}(2^8)$ 元素多项式表示、异或加法、模不可约多项式乘法与乘法逆元求解
第5章	5.1、5.2、5.3、5.5、5.16	分组操作模式（ECB/CBC/OFB/CTR）方程、初始向量 IV 机制、差错传播与重放/操纵攻击
第6章	6.3、6.5、6.6、6.10	对称密钥配对组合数、辗转相除法（GCD）、扩展欧几里得算法（EEA）与模逆验证
第7章	7.1、7.2、7.3、7.11	欧拉函数 $\varphi(n)$、公私钥对生成判定、平方-乘模幂计算、RSA 签名/加解密验证与小模数质因数分解

共计 31 道核心考查题。本篇对每道题均遵循“题意梳理 $\to$ 核心数学模型/代数关系 $\to$ 逐步手算推导 $\to$ 最终结论与易错陷阱”的标准答题格式展开。针对原教材个别印刷勘误（如习题 2.1 密钥末位字符），推导中均给出了严谨的代数校正与对照说明。

第1章：从字母频率到模运算

1.1：单表替换的频率攻击

题意。 对教材给出的替换密码密文统计A—Z频率，据英文统计与词结构恢复明文，并识别作者。密文如下，忽略大小写与换行：

lrvmnir bpr sumvbwvr jx bpr lmiwv yjeryrkbi jx qmbm wibpr xjvni mkd ymibrut
jx irhx wi bpr riirkvr jx ymbinlmtmipw utn qmumbr dj w ipmhh but bj rhnvwdmbr
bpr yjeryrkbi jx bpr qmbm mvvjudwko bj yt wkbrusurbmbwjk lmird jk xjubt trmui
jx ibndt
wb wi kjb mk rmit bmiq bj rashmwk rmvp yjeryrkb mkd wbi iwokwxwvmkvr mkd
ijyr ynib urymwk nkrashmwkrd bj ower m vjyshrbr rashmkmbwjk jkr cjnhd pmer bj
lr fnmhwxwrd mkd wkiswurd bj invp mk rabrkb bpmb pr vjnhd urmvp bpr ibmbr jx
rkhwopbrkrd ywkd vmsmlhr jx urvjokwgwko ijnkdhrii ijnkd mkd ipmsrhrii ipmsr w
dj kjb drry ytirhx bpr xwkmh mnbpjuwbt lnb yt rasruwrkvr cwbp qmbm pmi hrxb kj
djnlb bpmb bpr xjhhjcwko wi bpr sujsru msshwvmbwjk mkd wkbrusurbmbwjk w jxxru
yt bprjuwri wk bpr pjsr bpmb bpr riirkvr jx jqwkmcmk qmumbr cwhh urymwk wkbmvb

对应知识。 单表替换保持字母的出现次数与重复模式。短文中频率与长期英文统计会有差异，所以频率用于猜测，不能替代统一代回全文。

(1) 频率统计。 仅统计字母，共646个。每个频率为次数除以646，再乘100%。

字母	次数	频率%	字母	次数	频率%
A	5	0.77	N	17	2.63
B	68	10.53	O	7	1.08
C	5	0.77	P	30	4.64
D	23	3.56	Q	7	1.08
E	5	0.77	R	84	13.00
F	1	0.15	S	17	2.63
G	1	0.15	T	13	2.01
H	23	3.56	U	24	3.72
I	41	6.35	V	22	3.41
J	48	7.43	W	47	7.28
K	49	7.59	X	20	3.10
L	8	1.24	Y	19	2.94
M	62	9.60	Z	0	0.00

(2) 怎样从猜测走到全文。 最高频R可先猜E；反复出现的三字母词bpr猜成the，得到B→T、P→H、R→E。jx与mkd结合上下文可试of和and。第一个词lrvmnir随后还原为because，再把新增映射用于其他位置。每一步都必须检查与旧映射是否冲突。

最后得到密文字母到明文字母的替换表：

密文：ABCDEFGHIJKLMNOPQRSTUVWXYZ
明文：XTWDVQZLSONBAUGHKEPYRCIFMJ

恢复正文并补上自然空格、大小写与标点：

Because the practice of the basic movements of kata is the focus and mastery of self is the essence of Matsubayashi Ryu karate do, I shall try to elucidate the movements of the kata according to my interpretation based on forty years of study.

It is not an easy task to explain each movement and its significance, and some must remain unexplained. To give a complete explanation, one would have to be qualified and inspired to such an extent that he could reach the state of enlightened mind capable of recognizing soundless sound and shapeless shape. I do not deem myself the final authority, but my experience with kata has left no doubt that the following is the proper application and interpretation. I offer my theories in the hope that the essence of Okinawan karate will remain intact.

(3) 作者。 Shoshin Nagamine（长岭将真），对应《The Essence of Okinawan Karate-Do》。作者归属另与教材作者提供的第一版奇数题解答，第2页核对。

易错点。 空格不计入字母频率。Z在密文中未出现；若要求完整26字母置换，它对应唯一未用的明文字母J，可由排除法补齐，但这不是从Z的频率直接观察到的。

1.2：移位密码：猜一个对应，验证整段

题意。 密文为：

Xultpaajcxitltlxaarpjhtiwtgxktghidhipxciwtvgtpilpitghlxiwiwtxgqadds.

问频率攻击需要确定多少个字母对应，明文是什么，以及是谁的消息。

解法。 移位密码 $C=P+k\pmod{26}$ 只含一个未知量 $k$。所以只要确定一组正确的明密文字母对应，就可以确定全部位移。此串共67个字母，T出现10次最高；试猜T对应E，得到

$$k=19-4=15\pmod{26}.$$

全文每个字母减15取模，得到

ifweallunitewewillcausetheriverstostainthegreatwaterswiththeirblood

断词为：If we all unite, we will cause the rivers to stain the great waters with their blood. 这段话归于Tecumseh（特库姆塞），可对照其致Osage人的演说转录。

答案。 一组正确的对应字母足以确定密钥；本题 $k=15$。易错点： “猜一个字母足以提出候选”不等于“最高频字母必然是E”，要用全文是否通顺检验。

1.5：四个乘积为什么都得到6

题意。 手算 $15\cdot29$、$2\cdot29$、$2\cdot3$、$(-11)\cdot3$ 模13的结果，并解释关系。

知识与推理。 因为 $15\equiv2\equiv-11\pmod{13}$、$29\equiv3\pmod{13}$，四式都可先替换为 $2\cdot3$。直接核对：

$$435=33\cdot13+6,\quad58=4\cdot13+6,\quad6=0\cdot13+6,\quad-33=-3\cdot13+6.$$

答案：四个最小非负余数均为6。 易错点是负数余数也应规范到0—12，不能把-7当本题要求的最终余数。

1.7：构造环的运算表并判断逆元

题意。 构造 $\mathbb Z_4$ 加法及乘法表，$\mathbb Z_5$、$\mathbb Z_6$ 的加法及乘法表；找出 $\mathbb Z_4,\mathbb Z_6$ 中无乘法逆元的元素，解释为何 $\mathbb Z_5$ 的非零元素均有逆元。

方法。 行标与列标分别取 $a,b$，表项填 $(a+b)\bmod n$ 或 $ab\bmod n$。例如 $\mathbb Z_6$ 中，第4行第5列的乘法表项为 $20\bmod6=2$。

$\mathbb Z_4$ 加法表：

+	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

$\mathbb Z_4$ 乘法表：

×	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	2	0	2
3	0	3	2	1

$\mathbb Z_5$ 加法表：

+	0	1	2	3	4
0	0	1	2	3	4
1	1	2	3	4	0
2	2	3	4	0	1
3	3	4	0	1	2
4	4	0	1	2	3

$\mathbb Z_5$ 乘法表：

×	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

$\mathbb Z_6$ 加法表：

+	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	2	3	4	5	0
2	2	3	4	5	0	1
3	3	4	5	0	1	2
4	4	5	0	1	2	3
5	5	0	1	2	3	4

$\mathbb Z_6$ 乘法表：

×	0	1	2	3	4	5
0	0	0	0	0	0	0
1	0	1	2	3	4	5
2	0	2	4	0	2	4
3	0	3	0	3	0	3
4	0	4	2	0	4	2
5	0	5	4	3	2	1

逆元结论。 有逆元等价于与模数互素。$\mathbb Z_4$ 无逆元者为0、2；$\mathbb Z_6$ 无逆元者为0、2、3、4。5是素数，1—4都与5互素，其逆元分别为1、3、2、4。易错点是0在任何这些非平凡环中都没有乘法逆元。

1.9：模幂与一个离散对数

题意。 求 $3^2\bmod13$、$7^2\bmod13$、$3^{10}\bmod13$、$7^{100}\bmod13$，以及 $7^x\equiv11\pmod{13}$ 的一个指数解。

逐项计算。

1. $3^2=9$，余数9。
2. $7^2=49=3\cdot13+10$，余数10。
3. $3^3=27\equiv1$，所以 $3^{10}=(3^3)^3\cdot3\equiv3$。
4. $7^{100}=(7^2)^{50}\equiv(-3)^{50}=3^{50}=(3^3)^{16}\cdot3^2\equiv9$。
5. 依次乘7并取模：

$x$	0	1	2	3	4	5	6	7	8	9	10	11	12
$7^x\bmod13$	1	7	10	5	9	11	12	6	3	8	4	2	1

最小非负解是 $x=5$；表明7的阶为12，全部整数指数解为 $x\equiv5\pmod{12}$。

答案：9、10、3、9；最后一问可取5。 易错点：已知底数求指数与求模幂不是同一种问题，普通对数不能直接替代模意义的离散对数。

第2章：密钥流与LFSR

2.1(1)(2)：字母表上的序列密码

题意。 用A—Z表示0—25，设计逐字母序列密码；解密bsaspp kkuosp，给定的密钥流在本地版本中印为rsidpy dkawoa。本次只做(1)(2)。

(1) 方案。 每个位置使用一个 $K_i\in\mathbb Z_{26}$，加密 $y_i=(x_i+K_i)\bmod26$，解密 $x_i=(y_i-K_i)\bmod26$。空格只为排版，不占一个密钥字母位置。

(2) 逐字母解密。

位置	1	2	3	4	5	6	7	8	9	10	11	12
密文	B	S	A	S	P	P	K	K	U	O	S	P
数值 $y_i$	1	18	0	18	15	15	10	10	20	14	18	15
印刷密钥	R	S	I	D	P	Y	D	K	A	W	O	A
数值 $K_i$	17	18	8	3	15	24	3	10	0	22	14	0
$(y_i-K_i)\bmod26$	10	0	18	15	0	17	7	0	20	18	4	15
严格按印刷值解密	K	A	S	P	A	R	H	A	U	S	E	P

第一位例如 $1-17=-16\equiv10$，对应K。严格按教材印刷的末字母A，结果是KASPAR HAUSEP。

教材作者的第一版奇数题解答，第4页给出的意图是人名KASPAR HAUSER。要得到末字母R（17），逆算末密钥须满足 $15-K\equiv17\pmod{26}$，得到 $K=24$，即Y。因而把印刷密钥最后的A改为Y，就得到预期人名。

易错点。 这是算术核验与勘误推断，不应默默修改原密钥再宣称印刷值也能解出R。真正的序列密码不能靠姓名识别来代替逐位计算。

2.5：三位LFSR的序列与初态关系

题意。 $c_2=1,c_1=0,c_0=1$；分别从 $(s_2,s_1,s_0)=(1,0,0)$ 和 $(0,1,1)$ 产生序列，并说明二者关系。

约定与递推。 每拍输出右端最旧的 $s_i$，状态写成 $(s_{i+2},s_{i+1},s_i)$，反馈 $s_{i+3}=s_{i+2}\oplus s_i$。

拍号	初态100的状态	输出	初态011的状态	输出
0	100	0	011	1
1	110	0	101	1
2	111	1	010	0
3	011	1	001	1
4	101	1	100	0
5	010	0	110	0
6	001	1	111	1
7	100	重复	011	重复

答案。 第一条是0011101 0011101 ...，第二条是1101001 1101001 ...，均为周期7。第二条从第一条第3拍的状态011开始，故为同一周期序列的相位平移。不是两个不同的反馈多项式，也不是逐位取反。

易错点。 初始向量按 $s_2s_1s_0$ 给出，输出先读 $s_0$，不能把100直接当成输出前三位。

2.8：四位LFSR的全部非零状态环

题意。 对三式 $x^4+x+1$、$x^4+x^2+1$、$x^4+x^3+x^2+x+1$，画出LFSR、计算所有非零初态产生的序列，并判断本原、不可约或可约。

统一电路规则。 状态从左到右写 $(s_{i+3},s_{i+2},s_{i+1},s_i)$，右端为输出；每拍向右移，新位从左进入。下列各式分别指出从哪些单元接到异或反馈端，未列出的系数为0。

多项式	新反馈位	对应抽头
$x^4+x+1$	$s_{i+4}=s_{i+1}\oplus s_i$	最右两个单元
$x^4+x^2+1$	$s_{i+4}=s_{i+2}\oplus s_i$	右起第1、第3单元
$x^4+x^3+x^2+x+1$	$s_{i+4}=s_{i+3}\oplus s_{i+2}\oplus s_{i+1}\oplus s_i$	全部4个单元

公共的移位方向是：

反馈位 b --> [ s(i+3) ] --> [ s(i+2) ] --> [ s(i+1) ] --> [ s(i) ] --> 输出
    ^         从上表选中的单元取线，经过 XOR 后回到 b

下面每行把一个状态环完整列出，末状态再回到首状态。从环中任一个状态开始，就是该环输出串的一个循环移位；这已经覆盖所有初态，无需把同一环重复抄15遍。

(1) $x^4+x+1$：一个15状态环。

0001 → 1000 → 0100 → 0010 → 1001 → 1100 → 0110 → 1011
     → 0101 → 1010 → 1101 → 1110 → 1111 → 0111 → 0011 → 0001

从0001开始，依次读每个状态的最右位，输出周期为100010011010111，长15。全部非零状态位于同一个最大长度环，因此这是本原多项式，同时不可约。

(2) $x^4+x^2+1$：两个6状态环和一个3状态环。

0001 → 1000 → 0100 → 1010 → 0101 → 0010 → 0001
0011 → 1001 → 1100 → 1110 → 1111 → 0111 → 0011
0110 → 1011 → 1101 → 0110

对应首状态的输出周期依次为100010、110011、011，长6、6、3。三环状态数 $6+6+3=15$。因为

$$x^4+x^2+1=(x^2+x+1)^2\quad\text{在}\ \mathrm{GF}(2)\ \text{中},$$

所以它可约，且非本原；不同初态会处在不同长度的环里。

(3) $x^4+x^3+x^2+x+1$：三个5状态环。

0001 → 1000 → 1100 → 0110 → 0011 → 0001
0010 → 1001 → 0100 → 1010 → 0101 → 0010
0111 → 1011 → 1101 → 1110 → 1111 → 0111

对应周期串为10001、01001、11101。它在 $\mathrm{GF}(2)$ 下不可约，但非零状态周期只有5而不是15，所以是不可约但非本原。

答案核对。 三个多项式各自的非零状态环长度总和都是15；全零状态另成一个固定点，不计入题目要求的 $2^4-1$。易错点：这里“所有序列总长度15”说的是不同状态环的周期长度之和，不是每个初态都产生一条独立15长的序列。

第3章：DES位追踪

3.1：用三个输入对验证S1非线性

题意。 对三对输入证明 $S_1(x_1)\oplus S_1(x_2)\ne S_1(x_1\oplus x_2)$。用外侧两位定行、中间四位定列，按教材S1表查值。

$x_1$	$x_2$	$S_1(x_1)$	$S_1(x_2)$	左侧异或	$x_1\oplus x_2$	右侧S1
000000	000001	1110 (14)	0000 (0)	1110 (14)	000001	0000 (0)
111111	100000	1101 (13)	0100 (4)	1001 (9)	011111	1000 (8)
101010	010101	0110 (6)	1100 (12)	1010 (10)	111111	1101 (13)

例如第二行，111111的行号为3、列号为15；100000的行号为2、列号为0；二者异或011111的行号为1、列号为15。查得13、4、8，而 $13\oplus4=9\ne8$。

答案：三对均不满足线性关系。 易错点：异或不是十进制加法，$13\oplus4$ 等于9，不是17。

3.3：明文和密钥全0，求DES首轮

题意。 64位明文与64位密钥均全0，求第一轮输出。这里“首轮输出”指 $L_1\Vert R_1$，尚未执行最终逆置换。

逐步计算。 IP不改变全0，因此 $L_0=R_0=\mathtt{00000000}$。PC-1、移位、PC-2也不改变全0，所以48位 $K_1=0$。E扩展后再异或子密钥，八个S盒输入都为000000。

八个S盒依次输出十六进制 $E,F,A,7,2,C,4,D$，合起来为

$$S=\mathtt{EFA72C4D},\qquad P(S)=\mathtt{D8D8DBBC}.$$

由Feistel关系：

$$L_1=R_0=\mathtt{00000000},\qquad R_1=L_0\oplus P(S)=\mathtt{D8D8DBBC}.$$

答案：$L_1\Vert R_1=\mathtt{00000000D8D8DBBC}$。 易错点：不能对这个中间状态提前执行最终IP逆置换，或多做一次左右交换。

3.4：明文和密钥全1，求DES首轮

题意。 本题的明文和密钥都全1，不是只把明文改成全1。

IP后 $L_0=R_0=\mathtt{FFFFFFFF}$，第一轮子密钥为48个1，E扩展也为48个1，所以

$$E(R_0)\oplus K_1=0.$$

八个S盒输入仍然全0，因此与3.3相同，$S=\mathtt{EFA72C4D}$、$f=\mathtt{D8D8DBBC}$。最终

$$L_1=\mathtt{FFFFFFFF},\qquad R_1=\mathtt{FFFFFFFF}\oplus\mathtt{D8D8DBBC}=\mathtt{27272443}.$$

答案：$\mathtt{FFFFFFFF27272443}$。 它逐位等于3.3首轮输出的补码，也能作为一致性检查。易错点：把S盒输入误设为全1，会漏掉与全1子密钥的异或。

3.5：原明文第57位翻转的首轮传播

题意。 原64位输入只有第57位为1，其余位0，密钥全0；输入要经过IP。与全0输入比较：(1)哪些S盒输入改变？(2)按S盒设计标准，输出最少改几位？(3)首轮结果？(4)实际改几位？

(1) 位的位置。 标准IP把原第57位移到IP输出第33位，即 $R_0$ 的第一位。故 $L_0=0$、$R_0=\mathtt{80000000}$。E扩展把 $R_0$ 的第1位送入S1与S8，所以只有这两个S盒的输入与全0情况不同。

S1输入为010000，输出3；S8输入为000001，输出1；其他六个S盒不变。因此

$$S=\mathtt{3FA72C41},\qquad P(S)=\mathtt{D0585B9E}.$$

(2) 最小保证。 DES S盒的设计标准要求：改变单个输入位，至少改变2个输出位。S1、S8各有一个输入位翻转，所以S盒拼接输出最少改变4位；P只是置换，不改变差异位数。若统计整个 $L_1\Vert R_1$，左半还直接传递了一个变化位，理论下界为5位。

作为辨析，两个S盒各输出4位，故S盒拼接输出的上界是8位、整个首轮状态上界是9位；原题问的是最少，不是最多。

(3) 计算首轮。

$$L_1=R_0=\mathtt{80000000},\qquad R_1=L_0\oplus f=\mathtt{D0585B9E}.$$

(4) 实际汉明距离。 相对3.3，右半差异为

$$\mathtt{D8D8DBBC}\oplus\mathtt{D0585B9E}=\mathtt{08808022},$$

其中有5个1；左半还有1个变化位，合计6位。

答案：S1和S8；按设计标准S盒拼接输出最少4位；首轮为 $\mathtt{80000000D0585B9E}$；实际变化6位。 易错点是把原始第57位直接当作IP后第57位，或把理论下界、上界与本次实际值混在一起。

3.6：原密钥第1位翻转的逐轮影响

题意。 明文不变，原64位密钥在PC-1之前的第1位翻转，问加密、解密各轮的哪些S盒受到该位翻转影响。英文原书第83页问的是“which S-boxes in which rounds”，因此不能只回答首轮。下面先追首轮，再列完整16轮。

加密首轮。 原第1位经PC-1进入 $C_0$ 第8位；首轮循环左移1位，进入 $C_1$ 第7位。PC-2把这个位置选到子密钥第20位。每6位对应一个S盒，20落在19—24，所以直接影响S4。

所有轮次的直接子密钥路径。 每轮移位数为 $1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1$。若累计移位为 $t$，原 $C_0$ 第8位变到 $((8-1-t)\bmod28)+1$。再查PC-2，确定它是否被选入子密钥及所属S盒：

加密轮	累计左移	$C_i$中位置	子密钥中的位号	直接受影响S盒	使用该子密钥的解密轮
1	1	7	20	S4	16
2	2	6	10	S2	15
3	4	4	16	S3	14
4	6	2	24	S4	13
5	8	28	8	S2	12
6	10	26	17	S3	11
7	12	24	4	S1	10
8	14	22	未选入	无直接子密钥翻位	9
9	15	21	11	S2	8
10	17	19	14	S3	7
11	19	17	2	S1	6
12	21	15	9	S2	5
13	23	13	23	S4	4
14	25	11	3	S1	3
15	27	9	未选入	无直接子密钥翻位	2
16	28	8	18	S3	1

解密按逆序读表。 解密第 $j$ 轮使用 $K_{17-j}$。例如解密首轮用 $K_{16}$，累计左移28使该位回到半寄存器第8位，再被PC-2送到子密钥第18位，即S3。

重要边界。 表中记录的是“原密钥第1位通过密钥编排，直接翻转哪一个S盒输入的密钥位”。从首轮以后，前一轮状态变化还会经E扩展影响后面的S盒，因此“第8轮该位没有被PC-2选入”不等于“第8轮所有S盒的实际输入均不变”。不指定完整明文和原密钥，不能把后续状态的实际汉明差分直接写成唯一数值。

答案：加密首轮S4、解密首轮S3；全部轮次的直接影响见表。 易错点：解密要逆序子密钥；原位号、PC-1位置、PC-2输出位置是三个不同的编号系统。

3.9：DES穷尽密钥搜索的最坏与平均次数

题意。 已知一个明密文对，最直接穷尽搜索DES密钥，最不利和平均需检查多少把密钥？

推理。 DES有效密钥为56位，空间 $N=2^{56}$。顺序枚举且正确密钥在列表位置均匀时，最坏检查 $N$ 把，平均位置为

$$\frac{1+2+\cdots+N}{N}=\frac{N+1}2\approx2^{55}.$$

答案：最坏 $2^{56}$，平均 $(2^{56}+1)/2$，通常近似写 $2^{55}$。 一个64位分组检验也可能偶然匹配错误密钥，实际筛选应再用其他不同明密文对确认。不能把64个输入密钥位全部算作有效秘密位。

第4章：有限域手算

4.4：GF(16)的加法

题意。 $P=x^4+x+1$，分别计算 $(x^2+1)+(x^3+x^2+1)$ 和 $(x^2+1)+(x+1)$，并说明不可约多项式的影响。

推导。 系数模2，$1+1=0$。所以第一式的两项 $x^2$、两项常数分别抵消，得 $x^3$；第二式常数抵消，得 $x^2+x$。两者次数均小于4，不需要对 $P$ 约简。

答案：$x^3$；$x^2+x$。 在标准次数小于4的表示下，加法不依赖所选四次不可约多项式。易错点：不能进位，也不是普通整数相加。

4.5：GF(16)的乘法

题意。 同样的 $P=x^4+x+1$，求 $(x^2+1)(x^3+x^2+1)$ 和 $(x^2+1)(x+1)$。

(1) 展开并约简：

$$(x^2+1)(x^3+x^2+1)=x^5+x^4+x^3+1.$$

由 $x^4\equiv x+1$、$x^5\equiv x^2+x$，得

$$(x^2+x)+(x+1)+x^3+1=x^3+x^2.$$

商余核对：原乘积 $=(x+1)P+(x^3+x^2)$。

(2) 展开得 $x^3+x^2+x+1$，次数小于4，无需约简。

答案：$x^3+x^2$；$x^3+x^2+x+1$。 不可约多项式会影响高次项折回后的乘法表示；这次第二式没有高次项，因而结果不受影响。

4.6：AES域中的乘法

题意。 求 $(x^4+x+1)(x^7+x^6+x^3+x^2)$，模 $P=x^8+x^4+x^3+x+1$。

展开。 按右边四项分别乘，再异或同类项：

$$R_0=x^{11}+x^{10}+x^8+x^7+x^4+x^2.$$

逐次消去最高次项：

$$\begin{aligned} R_1&=R_0+x^3P=x^{10}+x^8+x^6+x^3+x^2,\\ R_2&=R_1+x^2P=x^8+x^5,\\ R_3&=R_2+P=x^5+x^4+x^3+x+1. \end{aligned}$$

余式次数小于8，完成。输入字节分别为0x13、0xCC，输出系数为00111011。

答案：$x^5+x^4+x^3+x+1$，即0x3B。 易错点：本题求乘积，不需要查逆元表；普通整数乘法后截低8位不是有限域乘法。

4.7：GF(16)中两个逆元

题意。 $P=x^4+x+1$，求 $x$ 和 $x^2$ 的乘法逆元，并反乘验证。

逆元一。 $P=x(x^3+1)+1$，因此 $x(x^3+1)\equiv1$，得 $x^{-1}=x^3+1$。反乘 $x^4+x\equiv(x+1)+x=1$。

逆元二。 多项式除法：

$$P=x^2\cdot x^2+(x+1),\qquad x^2=(x+1)(x+1)+1.$$

回代：

$$\begin{aligned} 1&=x^2+(x+1)^2\\ &=x^2+(x+1)(P+x^2\cdot x^2)\\ &=(x+1)P+(x^3+x^2+1)x^2. \end{aligned}$$

故 $(x^2)^{-1}=x^3+x^2+1$。验证乘积 $x^5+x^4+x^2\equiv(x^2+x)+(x+1)+x^2=1$。

答案：$x^3+1$；$x^3+x^2+1$。 易错点：这里加减同为异或，回代不能套用整数里未约化的正负系数。

第5章：工作模式与攻击条件

5.1：独立16字节数据库记录的模式选择

题意。 用AES加密大型数据库，每条记录16字节、记录之间无关联，选什么模式并解释。

推理。 AES分组为128位，正好是16字节。一条记录可独立处理，无需沿其他记录的链接解密；独立查询、更新和并行都方便。因此按教材这个效率情境，预期答案是ECB。

边界。 ECB满足同一密钥下 $X_i=X_j\Leftrightarrow C_i=C_j$。记录相互独立并不严格保证不重复，它仍泄露重复值与频率，也不提供完整性。因此答案应写“按题设的独立单分组情境选ECB”，不能写“ECB一般最安全”。

5.2：ECB与CBC的已知明文穷尽搜索

题意。 密钥长 $k$、分组长 $n$、$n>k$；分别分析ECB、已知IV的CBC、未知IV的CBC需要的数据和最坏工作量，并比较难度。

条件	可检验候选密钥的关系	教材通常记的数据量
ECB	$E_{K'}(X_1)\stackrel?=C_1$	一组明密文
CBC，已知IV	$E_{K'}(X_1\oplus IV)\stackrel?=C_1$	一组明密文与IV
CBC，未知IV	$E_{K'}(X_2\oplus C_1)\stackrel?=C_2$	两组连续数据；实需 $X_2,C_1,C_2$

为什么未知IV时不能只用第一组？ 每个 $K'$ 都能配出 $IV'=D_{K'}(C_1)\oplus X_1$，仅靠首组无法排除。第二组的链值是已观察到的 $C_1$，所以可以跳过未知IV。第一组明文 $X_1$ 本身不参与第二组的检验。

三种情况都枚举 $2^k$ 个密钥，最多约 $2^k$ 次底层加密及比较，固定组数下复杂度都是 $O(2^k)$；CBC没有把它变成 $2^{k+n}$。

严格唯一性的补充。 一组 $n$ 位数据下，错误候选的期望数约为 $(2^k-1)2^{-n}<1$。小于1不等于必为0；当 $n=k+1$ 时仍接近 $1/2$。增加不同输入输出对，$t$组下期望数约 $2^{k-nt}$，可降低偶然匹配风险。

答案：ECB一组；已知IV的CBC一组加IV；未知IV的CBC通常两组连续数据；指数搜索难度相同。 易错点：一组数据可用于检验，不保证绝无错误密钥；“IV保密”也不能代替增加密钥长度。

5.3：已知密钥时恢复CBC的IV与文件

题意。 AES-128密钥固定且攻击者已知；IV每天更新、同一天各文件开头共用。截获一个全0xFF文件和一个未知文件，恢复IV与未知内容。

推导。 全FF文件首个完整分组为16个FF字节，记为 $F$，对应密文 $A_1$。从 $A_1=E_K(F\oplus IV)$ 得

$$IV=D_K(A_1)\oplus F.$$

对同日未知文件 $C_1,C_2,\ldots$：

$$X_1=D_K(C_1)\oplus IV,\qquad X_i=D_K(C_i)\oplus C_{i-1}\quad(i\ge2).$$

如果使用填充，最后按既定规则去除填充。第二组起甚至不必等待IV恢复，因为前一密文已经给出了链值。

答案即上述两步公式。 易错点：题目明确密钥已知，不需要破解AES或枚举密钥；IV本身也不是必须保密的密码密钥。

5.5：OFB重复IV会怎样

题意。 同一密钥下每次消息加密的IV都不变，如何攻击OFB？

OFB为 $Z_0=IV,Z_i=E_K(Z_{i-1})$、$C_i=X_i\oplus Z_i$。重复起点会产生同一密钥流，于是

$$C_i\oplus C'_i=X_i\oplus X'_i.$$

若知道 $X_i$，先求 $Z_i=C_i\oplus X_i$，再得 $X'_i=C'_i\oplus C_i\oplus X_i$。若可请求全零消息加密，得到的密文就是这段密钥流。

答案：用密文异或消去复用流，并结合已知或可选择明文恢复另一消息对应区间。 只对复用且对齐的部分成立；仅凭两条密文不保证任意明文可唯一恢复。易错点：同一消息内部仍按OFB递推，不是每个分组都重新取相同 $E_K(IV)$。

5.16：只有输出漂白的DESA

题意。 $C=DES_K(X)\oplus K_1$，已知若干明密文对，证明破解复杂度与单重DES穷举同一数量级。

攻击步骤。

1. 枚举所有56位候选 $K'$。
2. 用第一组反算 $K'_1=C_1\oplus DES_{K'}(X_1)$，这一步不再枚举64位掩码。
3. 用第二组检验 $DES_{K'}(X_2)\oplus K'_1\stackrel?=C_2$，通过后再用额外不同数据确认。

等价地，把两组异或消去掩码：

$$C_1\oplus C_2=DES_K(X_1)\oplus DES_K(X_2).$$

复杂度。 两组检验约需 $2\cdot2^{56}=2^{57}$ 次DES运算，是 $O(2^{56})$，只是单DES穷举的常数倍。理想模型下，第二组检验后的错误候选期望数约 $2^{56-64}=2^{-8}$，可用第三组进一步排除。

答案：输出掩码不能带来额外64位的指数安全提升。 易错点：第一组会为任何候选密钥配出掩码，因此只用一组不能确认正确密钥。

第6章：数量、最大公约数与逆元

6.3：120人的两两对称密钥

题意。 120名员工每一对都要能安全通信，按每对拥有专属对称密钥的模型，需多少不同密钥？

每个人有119个通信对象，直接数 $120\cdot119$ 会把同一对算两遍，因此

$$N=\binom{120}2=\frac{120\cdot119}2=7140.$$

答案：7140把不同密钥，每人持有119把。 易错点：14280是两端都存一份时的密钥副本总数；全公司一把共享密钥不能隔离每一对员工的通信。

6.5：欧几里得算法的每轮与gcd链

题意。 求 $\gcd(7469,2464)$ 与 $\gcd(2689,4001)$，写出每轮和gcd链。

(1)

$$7469=3\cdot2464+77,\qquad2464=32\cdot77+0.$$

因此 $\gcd(7469,2464)=\gcd(2464,77)=\gcd(77,0)=77$。反向核对 $7469=77\cdot97$、$2464=77\cdot32$。

(2) 先交换为较大者在前：

$$\begin{aligned} 4001&=1\cdot2689+1312,\\ 2689&=2\cdot1312+65,\\ 1312&=20\cdot65+12,\\ 65&=5\cdot12+5,\\ 12&=2\cdot5+2,\\ 5&=2\cdot2+1,\\ 2&=2\cdot1+0. \end{aligned}$$

gcd链为 $(2689,4001)\to(4001,2689)\to(2689,1312)\to(1312,65)\to(65,12)\to(12,5)\to(5,2)\to(2,1)\to(1,0)$，每个括号对的gcd相同。

答案：77、1。 易错点：最后一个非零余数才是答案，不是终止时的0。

6.6：扩展欧几里得的系数表

题意。 对198、243和1819、3587求gcd及 $s,t$，验证 $sr_0+tr_1=\gcd(r_0,r_1)$，保持题目给定输入顺序。

共同规则。 保持 $r_i=s_i r_0+t_i r_1$，初始系数为 $(1,0)$、$(0,1)$。每轮用同一商同步更新余数与两组系数。因第一个输入更小，首个商0不代表错误。

(1) 198、243：

$i$	商 $q_i$	$r_i$	$s_i$	$t_i$
0	—	198	1	0
1	—	243	0	1
2	0	198	1	0
3	1	45	-1	1
4	4	18	5	-4
5	2	9	-11	9
6	2	0	27	-22

对应除法为 $198=0\cdot243+198$，$243=198+45$，$198=4\cdot45+18$，$45=2\cdot18+9$，$18=2\cdot9$。

回代 $9=45-2(198-4\cdot45)=9\cdot45-2\cdot198=9(243-198)-2\cdot198$。故 $s=-11,t=9$，验证 $-2178+2187=9$。

(2) 1819、3587：

$i$	商 $q_i$	$r_i$	$s_i$	$t_i$
0	—	1819	1	0
1	—	3587	0	1
2	0	1819	1	0
3	1	1768	-1	1
4	1	51	2	-1
5	34	34	-69	35
6	1	17	71	-36
7	2	0	-211	107

除法链是 $3587=1819+1768$，$1819=1768+51$，$1768=34\cdot51+34$，$51=34+17$，$34=2\cdot17$；最初还有商0的原序步骤。

回代：

$$\begin{aligned} 17&=51-34=51-(1768-34\cdot51)\\ &=35\cdot51-1768=35(1819-1768)-1768\\ &=35\cdot1819-36(3587-1819)\\ &=71\cdot1819-36\cdot3587. \end{aligned}$$

答案：gcd为9与17；对应系数可取 $(-11,9)$、$(71,-36)$。 验证第二式 $129149-129132=17$。易错点：系数并非唯一，但必须对应同一输入顺序；gcd不为1时不能宣称得到了乘法逆元。

6.10：用费马或欧拉定理求逆

题意。 求 $4^{-1}\bmod7$、$5^{-1}\bmod12$、$6^{-1}\bmod13$，必须用费马或欧拉定理。

规则。 先确认互素；然后 $a^{-1}\equiv a^{\varphi(n)-1}$。素数模数 $p$ 时为 $a^{p-2}$。

1. 模7：$4^{-1}\equiv4^5$；$4^2\equiv2$，$4^4\equiv4$，$4^5\equiv16\equiv2$。检查 $4\cdot2=8\equiv1$。
2. 模12：$\varphi(12)=12(1-1/2)(1-1/3)=4$，$5^{-1}\equiv5^3$；$5^2\equiv1$，故余数5。检查 $25\equiv1$。
3. 模13：$6^{-1}\equiv6^{11}$；$6^2\equiv10$，$6^4\equiv9$，$6^8\equiv3$，所以 $6^{11}\equiv3\cdot10\cdot6=180\equiv11$。检查 $6\cdot11=66\equiv1$。

答案：2、5、11。 易错点：12是合数，不能直接使用 $a^{12-2}$；定理的互素条件也必须检查。

第7章：RSA与平方乘

7.1：选择有效指数并求私钥

题意。 $p=41,q=17$；在 $e_1=32,e_2=49$ 中选有效RSA指数，求 $K_{pr}=(p,q,d)$，用扩展欧几里得写步骤。

先算 $n=697$、$\varphi(n)=40\cdot16=640$。$\gcd(32,640)=32$，不合法；对49：

$$640=13\cdot49+3,\qquad49=16\cdot3+1,\qquad3=3\cdot1.$$

故gcd为1。回代

$$1=49-16(640-13\cdot49)=209\cdot49-16\cdot640.$$

所以 $d=209$；反乘 $49\cdot209=10241=16\cdot640+1$。

答案：$e=49$，私钥 $(41,17,209)$，公钥 $(697,49)$。 易错点：逆元的模数为640，不是697；公开指数不要求本身一定为素数。

7.2：两次平方乘的全部二进制前缀

题意。 求 $2^{79}\bmod101$ 和 $3^{197}\bmod101$，写出每轮后中间指数的二进制。

规则。 最高位1直接初始化 $R=x,h=1$；以后每读一位 $b$，先平方使指数变为 $2h$，若 $b=1$ 再乘基数，轮末指数为 $2h+b$。下表指数均为二进制，余数均十进制。

(1) $79=(1001111)_2$。

轮次	读入位	平方后指数	平方余数	轮末指数	轮末余数
初始	1	—	—	1	2
1	0	10	4	10	4
2	0	100	16	100	16
3	1	1000	54	1001	7
4	1	10010	49	10011	98
5	1	100110	9	100111	18
6	1	1001110	21	1001111	42

例如第3轮 $16^2=256\equiv54$，再乘2得108，模101为7。后续平方是 $7^2=49$、$98^2=9604\equiv9$、$18^2=324\equiv21$；每轮读1时再乘2。

(2) $197=(11000101)_2$。

轮次	读入位	平方后指数	平方余数	轮末指数	轮末余数
初始	1	—	—	1	3
1	1	10	9	11	27
2	0	110	22	110	22
3	0	1100	80	1100	80
4	0	11000	37	11000	37
5	1	110000	56	110001	67
6	0	1100010	45	1100010	45
7	1	11000100	5	11000101	15

对应平方依次为 $3^2=9$、$27^2\equiv22$、$22^2\equiv80$、$80^2\equiv37$、$37^2\equiv56$、$67^2\equiv45$、$45^2\equiv5$；第1、5、7轮再乘3。

答案：42、15。 分别需要6次平方加4次乘基数、7次平方加3次乘基数。易错点：0位仍做平方，最高位已经初始化后不能重复处理。

7.3：两组RSA参数加密并解密

题意。 (1) $p=3,q=11,d=7,x=5$；(2) $p=5,q=11,e=3,x=9$。求加密和解密结果。

(1) 先由 $d$ 求 $e$。 $n=33,\varphi(n)=20$。

$$20=2\cdot7+6,\quad7=6+1,\quad1=7-(20-2\cdot7)=3\cdot7-20,$$

故 $e=3$。加密 $y=5^3=125\bmod33=26$。解密指数 $7=(111)_2$：

$$26^2\equiv16,\quad26^3\equiv16\cdot26\equiv20,\quad 26^6\equiv20^2\equiv4,\quad26^7\equiv4\cdot26\equiv5\pmod{33}.$$

(2) 先求 $d$。 $n=55,\varphi(n)=40$，由 $40=13\cdot3+1$ 得 $d\equiv-13\equiv27\pmod{40}$。加密 $9^2\equiv26$，$y\equiv26\cdot9\equiv14\pmod{55}$。

解密 $27=(11011)_2$：

已处理指数（二进制）	操作与余数，模55
1	初始化14
11	$14^2\equiv31$，再乘14得49
110	$49^2\equiv36$
1101	$36^2\equiv31$，再乘14得49
11011	$49^2\equiv36$，再乘14得9

答案：(1) $e=3$、密文26、解密5；(2) $d=27$、密文14、解密9。 易错点：第一组 $\varphi(33)=20$，给定的是私钥指数；两组的逆元模数和消息模数不能混用。

7.11：分解小模数并恢复明文

题意。 密文 $y=1141$，公钥 $(n,e)=(2623,211)$。(1)为何不能简单求解加密式？(2)能否直接用 $d=e^{-1}\bmod\varphi(n)$？(3)分解 $n$ 求私钥及明文，并讨论不少于1024位的模数。

(1) 不是普通开根。 实际关系是 $x^{211}=1141+2623t$，其中整数商 $t$ 未知；不是 $x^{211}=1141$。实数211次根不能恢复模意义的根。本题数字小，直接枚举明文可行，但不是对大模数的通用高效求根法。

(2) 公式正确，但还缺 $\varphi(n)$。 公钥只有 $n,e$，并不给出 $p,q$ 或 $\varphi(n)$。知道 $\varphi(n)$ 就能算 $p+q=n-\varphi(n)+1$，配合 $pq=n$ 还原因子，不能把这个关键未知量当作免费数据。

(3) 先分解。 $\sqrt{2623}<52$，尝试小素数至43，得到

$$2623=43\cdot61,\qquad\varphi(n)=42\cdot60=2520.$$

再求逆元，写出除法链：

$$\begin{aligned} 2520&=11\cdot211+199,\\ 211&=199+12,\\ 199&=16\cdot12+7,\\ 12&=7+5,\\ 7&=5+2,\\ 5&=2\cdot2+1,\\ 2&=2\cdot1. \end{aligned}$$

回代的关键各步为

$$\begin{aligned} 1&=5-2(7-5)=3\cdot5-2\cdot7\\ &=3(12-7)-2\cdot7=3\cdot12-5\cdot7\\ &=3\cdot12-5(199-16\cdot12)=83\cdot12-5\cdot199\\ &=83(211-199)-5\cdot199=83\cdot211-88\cdot199\\ &=83\cdot211-88(2520-11\cdot211)\\ &=1051\cdot211-88\cdot2520. \end{aligned}$$

因此 $d=1051$，检查 $211\cdot1051=221761=88\cdot2520+1$。

最后解密。 $1051=(10000011011)_2$。最高位初始化 $R=1141$，之后逐位平方乘：

轮次	位	平方余数	轮末指数（二进制）	轮末余数
初始	1	—	1	1141
1	0	873	10	873
2	0	1459	100	1459
3	0	1428	1000	1428
4	0	1113	10000	1113
5	0	713	100000	713
6	1	2130	1000001	1432
7	1	2061	10000011	1393
8	0	2052	100000110	2052
9	1	789	1000001101	560
10	1	1463	10000011011	1055

最后一轮可核对 $560^2=119\cdot2623+1463$，$1463\cdot1141=636\cdot2623+1055$。故

$$x=1141^{1051}\bmod2623=1055.$$

重新加密 $1055^{211}\bmod2623=1141$，与截获密文一致。

大模数的限制。 因数分解仍是攻击思路，但这种逐个试除的手算方法不适合由两个约512位素数构成的1024位模数；候选范围可达到约 $2^{512}$ 的数值规模。小例子只需试到43，不代表大模数也能如此便宜地分解。也不能反过来断言所有标称1024位的数都同样难分解，因子的实际大小仍有影响。

答案：$p=43,q=61,\varphi(n)=2520,d=1051,x=1055$。 易错点：求乘法逆元、求模幂和普通开根是三种不同操作。

最后用一张表检查有没有真正会做

类型	下笔前先写什么	算完后怎样检查
字母密码	字母数字映射、密钥定义、是否忽略空格	统一映射全文，逆运算重加密
LFSR	状态顺序、输出端、反馈递推	状态回到初态，所有非零状态不重不漏
DES	原始位号、IP/PC-1后的位号、轮密钥编号	每步位宽、S盒行列、差异位数
有限域	模2系数与不可约多项式	余式次数；逆元反乘余1
模式攻击	攻击者知道的明文、密钥、IV与链值	条件是否足够，是否只恢复一段流
EEA	初始输入顺序与系数不变量	$sa+tb=\gcd(a,b)$
RSA	$n$与$\varphi(n)$分开	$ed\equiv1$，解密回原文、重加密回密文

若时间很紧，先把3.3—3.6的位追踪、4.4—4.7的有限域、6.5—6.10的数论、7.1—7.11的RSA各手抄一遍。能够解释“每一步为什么合法”，再去记最终数字，才不会在改参数的题里失去方法。