考研复习 Day 41 | 密码学--第四章 分组密码（下）
注：以下内容参考《新编密码学》范九伦 张雪锋 侯红霞 编著
第4章 分组密码（下）
4.6 分组密码的工作模式
实际应用中待加密消息的长度通常大于分组长度，需要将长消息分成连续的分组进行处理。工作模式不仅增强算法的不确定性，还可实现密文长度与明文长度不对等、控制错误传播等。常用的工作模式有五种：ECB、CBC、CFB、OFB、CTR。
定义以下符号：
E(x)：分组加密过程
D(y)：分组解密过程
n：分组长度
P1,P2,…,Pm：明文分组序列
C1,C2,…,Cm：密文分组序列
LSBn(A)：A的最低n位
MSBn(A)：A的最高n位
A∥B：A与B的链接
1) ECB模式（电码本）
加密：Ci←E(Pi)
解密：Pi←D(Ci)
每个明文分组独立加密，相同明文产生相同密文。
优点：可并行，速度快；一个密文错误只影响当前分组。
缺点：不隐藏明文模式，安全性差。
适用：短数据（如加密密钥）。
2) CBC模式（密码分组链接）
加密：C₀←IV，Ci←E(Pi⊕C(i−1))
解密：Pi←D(Ci)⊕C(i−1)
IV是随机初始向量，需随密文一起发送。
每个密文分组依赖于所有之前的明文分组。
优点：隐藏明文模式，适合长消息。
缺点：不能并行，错误会传播到后续分组。
3) CFB模式（密码反馈）
设分组长度为s（1≤s≤n）。
加密：
I₁←IV,Ii←LSB(n−s)(I(i−1))∥C(i−1)
Oi←E(Ii),Ci←Pi⊕MSBs(Oi)
解密：公式相同，将Ci与Oi异或恢复Pi。
优点：可预处理，可加密小于分组长度的数据。
缺点：不能并行，错误传播。
4) OFB模式（输出反馈）
加密/解密：
I₁←IV,Ii←O(i−1)
Oi←E(Ii),Ci←Pi⊕Oi
加密和解密过程相同。
优点：可预处理，错误传播小（1比特错误只影响1比特明文）。
缺点：不能并行，需双方同步。
5) CTR模式（计数器）
加密/解密：
Ci←Pi⊕E(Ctri),Pi←Ci⊕E(Ctri)
计数器从IV开始递增。
优点：可并行，可预处理，加解密相同，安全性好。
缺点：需保持同步。
各种模式特点对比（表4-13）
| 模式 | 优点 | 缺点 |
|---|---|---|
| ECB | 可并行，速度快 | 不隐藏明文模式，抗攻击能力弱 |
| CBC | 隐藏明文模式，适合长消息 | 不能并行，错误传播 |
| CFB | 可预处理，支持短数据 | 不能并行，错误传播 |
| OFB | 可预处理，错误传播小 | 不能并行，需同步 |
| CTR | 可并行，可预处理，加解密相同 | 需同步 |
4.7 分组密码的安全性
常见攻击方法：
穷尽搜索攻击：暴力枚举密钥。
差分密码分析：分析明文对差值对密文对差值的影响，恢复密钥（Biham & Shamir, 1990）。数据复杂度高，但适用于评估安全性。
线性密码分析：寻找明文、密文、密钥之间的线性近似关系，通过大量已知明文-密文对猜测密钥位（Matsui, 1993）。
相关密钥攻击。
习题4 解答
4-1 证明：DES算法的解密过程是加密的逆过程。
证明：
DES是Feistel网络结构。对于Feistel网络，加密过程为：
Li=R(i−1),Ri=L(i−1)⊕f(R(i−1),Ki)
解密时，将密文作为输入，使用相同的子密钥但逆序：
R(i−1)=Li,L(i−1)=Ri⊕f(Li,Ki)
将加密最后一轮的输出(Ln,Rn)代入解密第一轮：
R(n−1)=Ln,L(n−1)=Rn⊕f(Ln,Kn)
由加密过程知Ln=R(n−1)，Rn=L(n−1)⊕f(R(n−1),Kn)。代入得：
L(n−1)=[L(n−1)⊕f(R(n−1),Kn)]⊕f(R(n−1),Kn)=L(n−1)
R(n−1)=R(n−1)
因此一轮解密恢复出上一轮的状态。依此类推，经过16轮后恢复出原始明文。所以解密是加密的逆过程。
4-2 证明：在DES算法中，每一个子密钥的第一个24位来自初始密钥的同一个28位子集，而每一个子密钥的第二个24位来自初始密钥的一个不相交的28位子集。
证明：
DES初始密钥56位（忽略奇偶校验位）。密钥生成时：
先通过置换选择1（PC-1）将56位分成两个28位：
C₀：包含原密钥的第57, 49, …, 4位（共28位）
D₀：包含原密钥的第63, 55, …, 7位（共28位）
C₀和D₀不相交，且覆盖全部56位。
每轮对C(i−1)和D(i−1)分别循环左移，得到Ci和Di。
通过置换选择2（PC-2）从56位（Ci∥Di）中选取48位作为子密钥：
前24位来自Ci的14, 17, 11, 24, 1, 5, 3, 28, 15, 6, 21, 10, 23, 19, 12, 4, 26, 8, 16, 7, 27, 20, 13, 2
后24位来自Di的41, 52, 31, 37, 47, 55, 30, 40, 51, 45, 33, 48, 44, 49, 39, 56, 34, 53, 46, 42, 50, 36, 29, 32
由于PC-2只从Ci取前24位、从Di取后24位，且Ci始终是C₀的移位，Di始终是D₀的移位，因此每个子密钥的前24位来自C₀对应的28位子集，后24位来自D₀对应的28位子集，且这两个子集不相交。
4-3 在DES和AES算法中找出代换密码和置换密码的部分。
解答：
| 算法 | 代换密码（Substitution） | 置换密码（Permutation） |
|---|---|---|
| DES | S-盒（8个S-盒，6位输入→4位输出） | IP初始置换、IP⁻¹逆初始置换、E-盒扩展、P-盒置换、PC-1、PC-2 |
| AES | ByteSubs（S-盒） | ShiftRows、MixColumns（部分置换性质） |
4-4 证明：y′=c(y)，其中y=DES(x,k)，y′=DES(c(x),c(k))，c(⋅)表示按位取反。
证明：
DES的加密由IP初始置换、16轮Feistel操作、IP⁻¹逆初始置换组成。
IP和IP⁻¹是线性置换，不影响取反性质，即IP(c(x))=c(IP(x))。
每轮Feistel操作：
轮函数f(R,K)中包含E-盒扩展（线性）、与子密钥异或、S-盒替换、P-盒置换。
S-盒的输入是E(R)⊕K，输出记为S(E(R)⊕K)。
当R和K都取反时，E(c(R))⊕c(K)=c(E(R))⊕c(K)=c(E(R)⊕K)。
可以验证：对于DES的S-盒，有S(c(x))=c(S(x))（补码性质）。
因此f(c(R),c(K))=c(f(R,K))。
Feistel轮变换：
加密：Li=R(i−1)，Ri=L(i−1)⊕f(R(i−1),Ki)
当输入和子密钥都取反时，输出也取反（异或性质）。
归纳可得：DES(c(x),c(k))=c(DES(x,k))，即y′=c(y)。
4-5 设AES-128密钥（十六进制）为：2B7E151628AED2A6ABF7158809CF4F3C，要求根据以上密钥构造出完整的密钥编排方案。
解答：
密钥长度128位，轮数N=10，需生成44个字w[0]∼w[43]。
步骤1：初始字
将16字节密钥按列排列：
w[0]=2B7E1516,w[1]=28AED2A6,w[2]=ABF71588,w[3]=09CF4F3C
步骤2：生成w[4]∼w[43]
对于i=4到43：
若imod 4≠0：w[i]=w[i−4]⊕w[i−1]
若imod 4=0：先计算temp=SubWord(RotWord(w[i−1]))⊕RCon[i/4]，然后w[i]=w[i−4]⊕temp
轮常数RCon[j]（十六进制）：
RCon[1]=01000000, RCon[2]=02000000, RCon[3]=04000000, RCon[4]=08000000,
RCon[5]=10000000, RCon[6]=20000000, RCon[7]=40000000, RCon[8]=80000000,
RCon[9]=1B000000, RCon[10]=36000000
计算示例：
i=4：
RotWord(w[3]) = 09CF4F3C → CF4F3C09
SubWord(CF4F3C09)：查AES S-盒得 8A 84 EB 01 → 8A84EB01
异或RCon[1]=01000000 → 8B84EB01
w[4] = w[0] ⊕ 8B84EB01 = 2B7E1516 ⊕ 8B84EB01 = A0FAFE17
类似继续计算，可得全部44个字。完整结果可查阅AES标准附录。
4-6 通过式(4-1)计算对应x=01010011的输出序列y。
解答：
x=01010011（二进制）= 0x53。
首先求x在GF(28)中的乘法逆元。查表或计算：0x53的逆为0xCA（二进制11001010）。
令b=11001010，应用仿射变换：
y=A⋅b⊕b₀
其中b₀=[0,1,1,0,0,0,1,1]^T（转置）。
计算A⋅b后异或b₀，得到y=0xED（二进制11101101）。
所以输出y=11101101。
4-7 已知DES算法中明文消息x和密钥k，试计算加密过程中的L₁和R₁。
解答：
这是一道计算量较大的题，需按DES步骤计算。
步骤1：初始置换IP
将64位明文按IP表重排，得到L₀和R₀各32位。
步骤2：生成子密钥K₁
将64位密钥去掉奇偶校验位，得56位。
PC-1置换得C₀和D₀各28位。
循环左移1位得C₁,D₁。
PC-2压缩置换得48位K₁。
步骤3：计算f(R₀,K₁)
E-盒扩展：32位→48位
与K₁异或
8个S-盒：48位→32位
P-盒置换得32位结果
步骤4：计算L₁,R₁
L₁=R₀,R₁=L₀⊕f(R₀,K₁)
由于手工计算繁琐，建议使用编程验证。最终结果为L1和R1各32位二进制数。
4-8 证明DES算法中S-盒4的性质。
解答：
(1) S-盒4的第一行和第二行已知。取第一行任意4位(x₁,x₂,x₃,x₄)，映射为(x₂,x₁,x₄,x₃)⊕(0,1,1,0)，可验证结果等于第二行对应位置的值。
(2) S-盒4的每行之间都存在类似的线性变换关系，可以通过列置换和位异或实现互变。具体可逐行验证。
4-9 已知IDEA算法中明文消息x和密钥k，试计算加密过程中第一轮的输出和第二轮的输入。
解答：
IDEA第一轮操作（参考教材图4-19）：
64位明文分成4个16位子分组：X₁,X₂,X₃,X₄。
使用前6个子密钥进行乘、加、异或操作，经过MA盒处理。
输出4个16位子分组，交换中间两个作为下一轮输入。
因计算过程较复杂，需分步进行。
4-10 在GF(2⁸)中，m(x)=x⁸+x⁴+x3+x+1，a(x)=x⁶+x⁴+x²+x+1，b(x)=x⁴+1，求a(x)⋅b(x)mod m(x)。
解答：
首先计算乘积：
a(x)⋅b(x)=(x⁶+x⁴+x²+x+1)(x⁴+1)
展开：
=x¹⁰+x⁸+x⁶+x5+x⁴+x⁶+x⁴+x²+x+1
合并：
=x¹⁰+x⁸+(x⁶+x⁶)+x⁵+(x⁴+x⁴)+x²+x+1=x¹⁰+x⁸+(x⁶+x⁶)+x⁵+(x⁴+x⁴)+x²+x+1
模m(x)化简，利用x⁸≡x⁴+x³+x+1：
x¹⁰=x²⋅x⁸≡x²(x⁴+x³+x+1)=x⁶+x⁵+x³+x²
代入：
(x⁶+x⁵+x³+x²)+x⁸+x⁵+x²+x+1
x⁵+x⁵=0,x²+x²=0
得：
x⁶+x³+x⁸+x+1
再用x⁸≡x⁴+x³+x+1：
x⁶+x³+(x⁴+x³+x+1)+x+1=x⁶+x⁴+(x³+x³)+(x+x)+(1+1)=x⁶+x⁴
所以结果为x⁶+x⁴，对应二进制01010000，十六进制0x50。
4-11 在GF(2⁸)上，(01)的逆是什么？
解答：
(01)在GF(28)中表示多项式1。1 × 1 = 1，所以逆是自身。
答案：01。
4-12 为了保证分组密码算法的安全强度，对分组密码算法的要求有哪些？
解答：
足够大的密钥空间，抵抗穷举搜索。
混淆与扩散特性好，满足雪崩效应。
抵抗已知攻击（差分分析、线性分析等）。
无弱密钥或半弱密钥。
轮函数具有高非线性。
加解密速度快，适合软硬件实现。
4-13 什么是雪崩效应？
解答：
雪崩效应：明文或密钥中任意1位发生变化，密文中平均约有一半（50%）的位发生变化。这确保了密文与明文、密钥之间无统计相关性。
4-14 什么是Feistel密码结构？实现Feistel密码结构所依赖的主要参数有哪些？
解答：
Feistel结构是一种迭代分组密码结构，每轮将输入分为左右两半，右半经轮函数处理后与左半异或，然后交换左右。
主要参数：
分组大小（2L位）
轮数（n）
子密钥生成算法
轮函数F
密钥大小
4-15 什么是分组密码的操作模式？有哪些主要的分组密码操作模式？其工作原理是什么？各有何特点？
解答：
操作模式是处理长消息时，重复应用分组密码的方法。
主要模式：
ECB：独立加密每个分组。可并行，但不隐藏模式。
CBC：前一分组密文与当前明文异或后加密。隐藏模式，但有错误传播。
CFB：将前一分组密文作为加密输入，输出与明文异或。支持短数据。
OFB：加密IV生成密钥流，与明文异或。错误不传播，需同步。
CTR：加密计数器值与明文异或。可并行，可预处理。
工作原理与特点见教材表4-13。
注：以上内容的理解和计算，如果有任何错误，希望各位读者和大佬指出改正，非常感谢！！！