【密码学——基础理论与应用】李子臣编著第三章分组密码课后习题

免责声明

这里都是自己搓或者手写的。
里面不少题目感觉有问题或者我的理解有偏颇，请大佬批评指正！
不带思考抄作业的请自动退出，我的并非全对，仅仅提供思维！

题目

逐题解析

3.9

做这题需要有置换和错排的知识储备（见参考文献）。

解： $2^n$ 个元素的置换有 $2^n!$ 种方式（不妨记为a）
其中，错排的数量为 $2^n! \sum_{k=0}^{2^n} \frac{(-1)^k}{k!}$ 个。（不妨记为b）
因此，S上具有不动点的置换个数是a-b个。

3.10

如果我没理解错题意，那么就是书上的证明。动手举个例子去试一下，理解不难。

3.11

解：DES的密钥为56bit，每个bit对应0或者1，双重DES则有112个密钥。因此

$P= \frac{1}{2^{112}}$

3.12

解：101010对应的横坐标是10（即2），纵坐标对应的是0101（即5）。
100010对应的横坐标是10（即2），纵坐标是0001（即1）。

我们并不知道是哪个盒子，因此要讨论。

		S1	S2	S3	S4	S5	S6	S7	S8
（2,5）	数值	6	4	15	11	13	8	3	12
（2,5）	二进制	0110	0100	1111	1011	1101	1000	0011	1100
（2,1）	数值	1	14	6	6	2	14	4	11
（2,1）	二进制	0001	1110	0110	0110	0010	1110	0100	1011

3.13

解：同上理，这是一个逆向过程。对于每个盒子，输入的数字都不一定一样。
（每一个点对应的输入值请自己翻译，表格太长写不下。。。）

	S1	S2	S3	S4	S5	S6	S7	S8
1010 (十进制为10)	(0,9)	(0,15)	(0,0)	(0,7)	(0,5)	(0,2)	(0,13)	(0,8)
	(1,8)	(1,11)	(1,7)	(1,13)	(1,11)	(1,10)	(1,7)	(1,4)
	(2,13)	(2,4)	(2,13)	(2,0)	(2,4)	(2,11)	(2,8)	(2,10)
	(3,12)	(3,2)	(3,1)	(3,4)	(3,12)	(3,7)	(3,6)	(3,5)
0010 (十进制为2)	(0,4)	(0,10)	(0,14)	(0,9)	(0,0)	(0,5)	(0,2)	(0,2)
	(1,5)	(1,5)	(1,8)	(1,10)	(1,2)	(1,3)	(1,12)	(1,15)
	(2,6)	(2,14)	(2,10)	(2,13)	(2,1)	(2,4)	(2,15)	(2,7)
	(3,3)	(3,7)	(3,14)	(3,14)	(3,6)	(3,2)	(3,13)	(3,0)

3.14（待填坑）

这题需要用到多项式乘法逆元的知识。
学了AES我才知道大二上学的离散真的是一坨，密码学核心的循环群、环、域全部不用讲。
但是期末又把群论考的群难得一批。
然后有限域多项式的乘法完全把我搞蒙b了......现在也还在消化过程中。

解：
第一步求解逆元。
由题， $(a_7a_6a_5a_4a_3a_2a_1a_0)(b_7b_6b_5b_4b_3b_2b_1b_0) \equiv 1 \ mod \ m(x)$
用扩展欧几里得算法算出 $(b_7b_6b_5b_4b_3b_2b_1b_0)$ 。但是我还不会算，等待填坑
第二步仿射变换。
仿射变换简单亿点点。

3.15

这个就是异或运算。

解：

$A(x) \oplus B(x) \\ =(1b \oplus ac) x^3+(03 \oplus 00) x^2+(dd \oplus f0) x^1+(a1 \oplus 2d) x^0 \\ =b7x^3+03 x^2+22 x^1+8c x^0$

3.16（待填坑）

AES的列变换矩阵（记为P）如下：

$\begin{pmatrix} 02 & 03 & 01 & 01 \\ 01 & 02 & 03 & 01 \\ 01 & 01 & 02 & 03 \\ 03 & 01 & 01 & 02 \end{pmatrix}$

课本也给出了逆矩阵P'如下：

$\begin{pmatrix} 0E & 0B & 0D & 09 \\ 09 & 0E & 0B & 0D \\ 0D & 09 & 0E & 0B \\ 0B & 0D & 09 & 0E \end{pmatrix}$

那么

$(t_{ij})_{4*4}= P' (s_{ij})_{4*4}$

代码有空更新，这是16进制的，目前我还不会搞。

3.17

解：xtime(b)公式如下：
若b7=0，则字节内左移一位。
若b7=1，则字节左移一位之后与4D（01001101）的按位模2实现。
推导：

$x^8=x^6+x^3+x^2+1\\ xtime(b)\\ =b_7x^8+b_6x^7+b_5x^6+b_4x^5+b_3x^4+b_2x^3+b_1x^2+b_0x^1+0\\ =(b_6\oplus 0)x^7+(b_5\oplus 1)x^6+(b_4\oplus 0)x^5+(b_3\oplus 0)x^4+\\(b_2\oplus 1)x^3+(b_1\oplus 1)x^2+(b_0\oplus 0)x^1+(0\oplus 1)\\$

0x6D·0xD5计算结果：0xBA
过程：

参考文献

置换：近世代数笔记与题型连载第八章（置换群）_轮换与对换的关系-CSDN博客

错排：彻底搞懂错排公式-CSDN博客

【组合数学】错排问题 ( 递推公式 | 通项公式 | 推导过程 ) ★-CSDN博客

有限域：密码编码学与网络安全--原理与实现--（第八版）第5章 ------有限域_密码编码学与网络安全第八版答案-CSDN博客

有限域、域内运算、不可约多项式、本原多项式【这篇一定能让你看懂！！】-CSDN博客