密码学基础真题总结

密码学2017~2021真题题型总结

1. 置换密码（难度：★）

出现于2017、2019、2020、2021年第一题，重点在于重合指数的计算。

在确定的文本中，重合指数的定义如下：

重合指数：文本中任选两个字符相同的概率。通过概率论相关知识容易得到其公式为

$$I_c(X)=\frac{\sum_{i=0}^{25}f_i(f_i-1)}{n(n-1)}$$

其中$f_i$为每个密文字符的出现次数，$n$为文本长度。

求逆置换和解密不难，解密根据逆置换分组重排即可。

2. 仿射密码（难度：★）

出现于2018年第一题，重点在于通过加密密钥求出解密密钥。

如果加密密钥为$(a, b)$，它表示对于明文字符$p$和密文字符$c$，有

$$c = ap+b\pmod {26}$$

经过推导容易得出：

$$p = a^{-1}(c-b)\pmod {26}$$

解密密钥为$(a^{-1}, -a^{-1}b)$。

另外注意A对应的数为0不是1。

3. LSFR分析（难度：★★）

出现于2017、2019、2020、2021年第二题，重点在于LSFR生成规则的获取。（今年周期不考）

首先将明文与密文异或得到密钥，题目中会给出LFSR的级数，这也是后面计算的矩阵的行数和列数。为描述方便，以2021年第二题为例讲解。

题中的密钥为001110011011111，级数为5，故以5位单位分组，可以分为3组。设递推公式为

$$a_{5}=c_5a_0\oplus c_4a_1\oplus ...\oplus c_1a_{n-1},c_i\in Z_2,c_5=1$$

将其转换为矩阵形式：

$$a_5=\begin{pmatrix}c_5 & c_4 & c_3 & c_2 & c_1\end{pmatrix} \begin{pmatrix}a_0\\ a_1\\ a_2\\ a_3\\ a_4\end{pmatrix}$$

扩展到第二组全部5位可以得到：

$$\begin{pmatrix}a_5 & a_6 & a_7 & a_8 & a_9\end{pmatrix} =\begin{pmatrix}c_5 & c_4 & c_3 & c_2 & c_1\end{pmatrix} \begin{pmatrix}a_0&a_1&a_2&a_3&a_4\\ a_1&a_2&a_3&a_4&a_5\\ a_2&a_3&a_4&a_5&a_6\\ a_3&a_4&a_5&a_6&a_7\\ a_4&a_5&a_6&a_7&a_8\end{pmatrix}$$

以此来计算$c_i$的值，这里需要计算一次5×5矩阵的模逆矩阵，计算方法与计算一般矩阵的逆矩阵相同，可以使用伴随矩阵法和行列变换法。对于$Z_2$上的模逆矩阵运算，行列变换法较伴随矩阵法更方便，且不易出错。

特征多项式：$f(x)=|xI-T|=x^n-c_1x^{n-1}-...-c_{n-1}x-c_n$
求出特征多项式之后即可在域中计算其周期。按照信数中学习的周期计算方法计算即可。

4. 希尔密码（难度：★★）

出现于2018年第二题，重点在于通过加密密钥求出解密密钥。
在已知一组明文和密文的情况下，求密钥很简单。

需要注意的是，如果密钥矩阵的长度为m，则需要m组明文-密文对，把它们组成一个方阵，计算逆矩阵即可求解。如果方阵奇异，则需要重新选择明文-密文对组成方阵。

技巧：求26的模逆矩阵，对2阶和3阶方阵使用伴随矩阵法更方便。考虑到计算量，考试应该不会考高于3阶方阵的模26逆矩阵。

5. 求密码体制的熵、信息量、互信息、完善保密性等（难度：★★★★）

出现于2017、2018、2019、2020年第三题。要牢记熵、信息量、互信息的概念和有关公式，当公式记不清楚的时候通过概念可能可以推出来。这一部分难点在于对公式的灵活运用。

完善保密性相关定理：

定义：一个密码体制具有完全保密性，如果对于任意$x\in P$和$y \in C$，都有$Pr[x|y]=Pr[x]$，即密文字符随机变量与明文字符随机变量独立（或说明文x的后验概率等于其先验概率）

定理1：假设移位密码的26个密钥以相同概率随机使用，对于任意的明文概率分布，移位密码都具有完善保密性。

定理2：假设密码体制$(P,C,K,E,D)$满足$|K|=|C|=|P|$（$|K|\ge |C|\ge |P|$是完全保密的必要条件）。这个密码体制是完善保密的，当且仅当每个密钥被使用的概率相等，均为$\frac{1}{|K|}$，且对于任意$x\in P,y\in C$，均存在唯一密钥$k$，使得$e_k(x)=y$。

判定定理1：对密码体制$(P,C,K,E,D)$，若对于任意$x\in P,y\in C$，有$\sum_{k:x=d_k(y)}Pr[k]=\frac{1}{|P|}$，则该密码完善保密。

判定定理2：对于密码体制$(P,C,K,E,D)$，$K$等概率选取，若对于任意的$x\in P,y\in C,|{k:x=d_k(y)}|=\frac{|K|}{|P|}$，则该密码体制完善保密。（可以由判定定理1推导出）

判定定理3：对于密码体制$(P,C,K,E,D)$，$|P|=|C|$，$K$等概率选取，当且仅当对于任意的$x\in P,y\in C,|{k:x=d_k(y)}|=\frac{|K|}{|P|}$，该密码体制完善保密。（可以由判定定理4推导出）

判定定理4：对于密码体制$(P,C,K,E,D)$，$|P|=|C|$，且明文$|P|$等概率选取。当且仅当对于任意$x\in P,y\in C$，有$\sum_{k:x=d_k(y)}Pr[k]=\frac{1}{|P|}$，该密码体制完善保密。

自信息量：

如果信源发出消息$x_i$的概率为$p(x_i)$，则其能提供的自信息量（自信息）为：

$$I(x_i)=\log_2\frac{1}{p(x_i)}=-\log_2p(x_i)$$

（式中的底数可以换，这里由于使用比特作为信息媒介，因此使用2作为底数。如果使用10进制数字，则就应使用10作为底数，即底数由1位信息媒介的可能取值数决定）

联合自信息量：

$$I(x_1x_2...x_n)=-\log_2p(x_1x_2...x_n)$$

当这些变量均独立时，$I(x_1x_2...x_n)=I(x_1)+I(x_2)+...+I(x_n)$

条件自信息量：
类比条件概率
后验概率：$I(x_i|y_j)=-\log_2p(x_i|y_j)$
信道转移概率：$I(y_j|x_i)=-\log_2p(y_j|x_i)$
$I(x_iy_j)=-\log_2p(y_j|x_i)p(x_i)=I(x_i)+I(y_j|x_i)=I(y_j)+I(x_i|y_j)$

互信息量：

$$I(x_i;y_j)=I(x_i)-I(x_i|y_j)=\log_2\frac{p(x_i|y_j)}{p(x_i)}=\log_2\frac{p(x_iy_j)}{p(x_i)p(y_j)}$$

即先验不确定度$-$后验不确定度

熵

即信息量的期望。

$$H(X)=E[I(x)]=-\sum_{x\in X}p(x)(\log_2p(x))$$

条件熵：

$$H(X|Y)=-\sum_{x\in X}\sum_{y\in Y}p(xy)\log_2p(x|y)$$

注意上面的式子是条件熵，下面的不是！

$$H(X|y)=-\sum_{x\in X}p(x|y)\log_2p(x|y)$$

定理1：随机变量$X$的概率分布为$p_1,p_2,...,p_n$，则$H(X)\le \log_2n$，当且仅当$p_i=\frac{1}{n}$时等式成立（使用Jensen不等式证明）

定理2：$H(XY)\le H(X)+H(Y)$，当且仅当$X$和$Y$统计独立时等号成立

定理3：$H(XY)=H(Y)+H(X|Y)$

定理4：$H(X|Y)\le H(X)$，当且仅当$X$和$Y$统计独立时等号成立。

平均互信息量

即互信息量的期望

$$I(X;Y)=E[I(x;y)]=\sum_{x\in X}\sum_{y\in Y}p(xy)I(x;y)\\ =H(X)-H(X|Y)=H(Y)-H(Y|X)=H(X)+H(Y)-H(XY)$$

性质：$I(X;Y)=I(Y;X)\le \min\{H(X),H(Y)\}$，当X,Y存在有一一对应关系时，$I(X;Y)=H(X)=H(Y)$

平均条件互信息量：$I(X;Y|Z)=I(X;YZ)-I(X;Z)$

上图中：
绿+紫=$I(X;Y)$；蓝+紫=$I(Y;Z)$；青+紫=$I(X;Z)$
绿=$I(X;Y|Z)=\sum_{x\in X}\sum_{y\in Y}\sum_{z\in Z}p(xyz)\log_2\frac{p(z)p(xyz)}{p(xz)p(yz)}$；
蓝=$I(Y;Z|X)=\sum_{x\in X}\sum_{y\in Y}\sum_{z\in Z}p(xyz)\log_2\frac{p(x)p(xyz)}{p(xy)p(xz)}$；
青=$I(X;Z|Y)=\sum_{x\in X}\sum_{y\in Y}\sum_{z\in Z}p(xyz)\log_2\frac{p(y)p(xyz)}{p(yx)p(yz)}$；
红=$H(X|YZ)$；橙=$H(Y|XZ)$；黄=$H(Z|XY)$
紫=$I(X;Y;Z)=\sum_{x\in X}\sum_{y\in Y}\sum_{z\in Z}p(xyz)\log_2\frac{p(xy)p(yz)p(zx)}{p(x)p(y)p(z)p(xyz)}$
红+青=$H(X|Y)$；橙+蓝=$H(Y|X)$；
红+绿=$H(X|Z)$；黄+蓝=$H(Z|X)$；
橙+绿=$H(Y|Z)$；黄+青=$H(Z|Y)$；
除黄所有=$H(XY)$；除红所有=$H(YZ)$；除橙所有=$H(XZ)$
青+紫+蓝=$I(XY;Z)$；绿+紫+蓝=$I(XZ;Y)$；绿+紫+青=$I(YZ;X)$
红+绿+橙=$H(XY|Z)$；红+青+黄=$H(XZ|Y)$；橙+蓝+黄=$H(YZ|X)$

由上图可知以下结论：
$I(X;Y;Z)=I(X;Z)-I(X;Z|Y)=I(X;Y)-I(X;Y|Z)=I(Y;Z)-I(Y;Z|X)$
$H(X|Y)-H(X|YZ)=I(X;Z|Y)$
$H(Y|Z)-H(Y|ZX)=I(Y;X|Z)$
$H(Z|X)-H(Z|XY)=I(Z;Y|X)$
$I(X;Y)+I(Z;Y|X)=I(XZ;Y)$
$I(Y;Z)+I(X;Z|Y)=I(XY;Z)$
$I(Z;X)+I(Y;X|Z)=I(XZ;Y)$

定理2.10
设$(P,C,K,E,D)$是一个密码体制，那么有$H(K|C)=H(K)+H(P)-H(C)$
即截获密文后，密钥的熵等于明文的熵加密钥的熵减密文的熵（密钥含糊度）

一般密码体制与熵有关的性质

1. $|P|\le|C|$（从明文空间到密文空间必为单射）
2. $H(P|KC)=H(C|KP)=0$（见定理2.10证明部分）
3. $H(PK)=H(P)+H(K)$（见定理2.10证明部分）
4. 定理2.10结论
5. $H(P)\le H(C)\le H(P)+H(K)$（$H(K|C)\le H(K)$，由定理2.10推出）
6. $H(P|C)\le H(K|C)$

推论：若$|P|=|C|$，且P随机等概率分布，则C一定随机等概率分布。此时$H(K|C)=H(K)$
对于完善保密体制，还有下面的性质：

7. $H(P|C)=H(P)$
8. $|P|\le |C|\le |K|(Pr[y|x]=Pr[y]>0)$
9. $H(P)\le H(C)\le H(K)$

注意：密码体制之中有三个随机变量：明文P、密文C和密钥K，三者之间有一定关系：
明文与密钥独立，故二者的互信息量$I(P;K)$为0。
当明文与密钥确定后，密文唯一确定，故条件熵$H(C|PK)=0$，同理当密文与密钥确定后，明文唯一确定，故$H(P|CK)=0$
另外，互信息不可能为负（上面定理4可知条件熵小于熵），因此下图的$S3\ge S1,S2\ge S1$
在完善保密密码体制中有$H(P|C)=H(P)$，因此$I(P;C)=0$（明密文独立）


如果上面的结论记不住，可以用熵的定义来计算，就是比较费时间，但一般题目中计算量也不高，注意别算错了就行。

完善保密性的证明：使用定义、使用四个判定定理

6. Rabin密码体制（难度：★★）

掌握加密和解密方法。出现于2021年第四题

Rabin加密需要3个参数参与：n,p,q，其中p和q为私钥且均为4k+3型素数，n=pq为公钥。
加密算法：cipher = (plaintext ^ 2) mod n
解密算法：$plaintext = \sqrt{cipher} \mod n$（在知道密钥的情况下，将其拆成两个式子$\sqrt{cipher} \mod p$和$\sqrt{cipher} \mod q$计算。由于p、q均为4k+3型素数，故其解很好求：$\sqrt{cipher}\equiv cipher^{\frac{p+1}{4}}\pmod p,\sqrt{cipher}\equiv cipher^{\frac{q+1}{4}}\pmod q$，然后使用中国剩余定理）

7. RSA密码体制加解密（难度：★★）

掌握加密和解密方法，出现于2020年第四题，2017、2018年第五题

通过n解出p和q的值，计算$c^d\mod n$即可（$ed\equiv 1\pmod {\varphi(n)}$）

8. 有限域字节代换（难度：★★）

出现于2018、2020年第六题，2017年第七题，重点在于逆元的计算。

两题都给了’00’的替换值，通过这个值可以直接获得C的值，然后逐位计算即可。

9. 原理题（难度：★★★）

出现于2017年第七题，2018、2019、2021年第八题，这种题范围广泛，需要我们对各种加密函数、散列函数、密码分析原理等有一定的理解。

需要能说得出基本原理的名词解释，可按照下面列表进行自测：

• 古典密码加密原理
  • 移位密码
  • 代换密码
  • 仿射密码
  • 维吉尼亚密码
  • 希尔密码
  • 置换密码
• 古典密码分析原理
  • 移位密码的唯密文攻击原理（暴力破解）
  • 代换密码的唯密文攻击原理（字频分析）
  • 仿射密码的唯密文攻击原理（字频分析）
  • 维吉尼亚密码的唯密文攻击原理（Kasiski测试法、重合指数法）
  • 希尔密码的已知明文攻击原理（矩阵计算）
• 四种密码攻击方式
• 流密码
  • LSFR的工作原理
  • LSFR的变换矩阵、特征多项式分析原理（已知明文攻击）
• 唯一解距离和乘积密码体制
  • 伪密钥的概念
  • 自然语言的熵和冗余度
  • 自然语言的唯一解距离
  • 乘积密码和幂等密码
• 线性密码框架
  • SPN网络的加密过程
  • Feistel结构的加密过程
• 线性密码分析
  • 线性逼近分析原理与过程
  • 差分分析原理与过程
• 几种线性密码
  • AES基本流程
  • DES基本流程
• 分组密码的五种工作模式原理与区分
  • ECB（电子密码本）
  • CBC（密码分组链接）
  • CFB（密码反馈）
  • OFB（输出反馈）
  • CTR（计数器）
• CTS（密文挪用）
• Hash函数
  • Hash函数三个安全性问题
  • 生日攻击原理
  • MD5基本流程
  • SHA1基本流程
  • SHA3基本流程
  • SM3基本流程
  • MAC校验码
    • HMAC
    • CBC-MAC
    • CCM
  • 彩虹表攻击原理与优势
• 公钥密码体制
  • 中国剩余定理加速解密RSA
  • Montgomery算法原理
  • DH密钥交换的实现及中间人攻击原理
  • 素性检测算法
    • 伪素数
    • Solovay-Strassen算法
    • Miller-Rabin算法
  • 共模攻击与小加密指数攻击原理
  • 小解密指数的Wiener攻击原理
  • ElGamal密钥交换原理
  • 数字签名的基本概念与作用
  • ElGamal数字签名算法原理
  • DSA数字签名算法原理
  • PGP基本结构

原理简述：

• 古典密码加密原理
  • 移位密码：将明文全部字母按序号向后移动替换固定位数得到密文，如A向后1位为B，向后2位为C等。移位密码每位移动的数值为密钥，明文和密文均在模26的整数群中。
  • 代换密码：将明文字母与密文字母组成一一对应关系，将明文中所有字母按照这个关系替换为对应的字母，顺序不变，得到密文。
  • 仿射密码：将明文字母与密文字母形成模26的线性关系$p=ac+b\mod 26$，按照此线性关系替换明文中的所有字母为密文字母，输出密文。
  • 维吉尼亚密码：需要一个长度为k的密钥，将明文按照密钥长度进行分组，对于每一个分组，其中的每一个字母进行移位，移位位数为密钥中对应位置字母的序号。
  • 希尔密码：需要一个行数和列数均为k的矩阵作为密钥，将明文按照k长度分组，对于每一个分组，将明文行向量与矩阵进行乘积计算得到密文分组。
  • 置换密码：以某种方式将明文中的字母重新排列，多进行分组。
• 古典密码分析原理
  • 移位密码分析：由于移位密码的密钥只有26个，因此当明文具有特定意义时可以通过暴力求解。当明文不具有特定含义与标识时，由于无法确认26个解密结果中哪一个是明文，无法进行解密。
  • 代换密码分析：对于一段有含义的英文文本，代换前后的字母频率不变，如英文中字母e的出现频率最高，那么在经过代换密码加密后的密文中出现频率最高的几个字母中很可能就有一个是由e代换而来。因此通过对密文中的字频分析对几个字母的代换关系进行猜解。
  • 仿射密码分析：同字频分析，但由于仿射密码中明文字母与密文字母具有特定线性关系，因此只需要对两个字母的对应关系进行猜解就可以计算出密钥a和b的值，以计算出来的值带回到密文中尝试还原。
  • 维吉尼亚密码的Kasiski测试法：测试密钥的长度使用的方法。在密文中找到相同的长度为3及以上的串，获取它们的起始位置，求差后取最大公因数，则最大公因数很可能就是密钥的长度。
  • 维吉尼亚密码的重合指数法：测试密钥的长度与破解使用的方法。重合指数指的是一段文本中任取两个字母相同的概率。尝试不同的密钥长度，计算使用同一个字母序号唯一加密的字母组的重合指数（如尝试密钥长度为5，则应选取第1/6/11…位计算重合指数），每一组计算出的重合指数应该与英文自然语言文本的重合指数相差不大。找到密钥长度之后对26个不同的偏移量还原出的文本计算其与明文的重合指数：$M_g=\sum_{i=0}^{25}p_i\times \frac{f_{i+g}}{n'}$，其中$p_i$为英文中不同字母出现的概率，$\frac{f_{i+g}}{n'}$为还原文本中不同字母出现的频率。
  • 希尔密码分析：如果密钥长度为k，已知k组明密文对，则可以将明密文对分别组成两个矩阵进行计算，直接求出密钥矩阵。
• 四种密码攻击方式
  • 唯密文攻击：仅得知密文并由此分析出原文的攻击方式。通过这种攻击方式可以破解的密码有：移位密码（明文有特定含义的绝大多数情况下）、仿射密码（明文有特定含义且有足够长度的情况下）、代换密码（明文有特定含义且有足够长度的情况下）、为吉尼亚密码（明文有特定含义且有足够长度的情况下，一般其需要的密文长度大于前面三种）
  • 已知明文攻击：得知特定密文及其对应明文，从而获取密钥的攻击方式。通过这种攻击方式可以破解的密码有：希尔密码（需要知道加密矩阵的维数）、基于LSFR的流密码（需要知道特征表达式的次数或变换矩阵的维数）、SPN网络的线性分析（需要一定量的明密文对）
  • 选择明文攻击：攻击者可以自行选择明文获取其密文，据此获取密钥的攻击方式。通过这种攻击方式可以破解的密码有：SPN网络的差分分析
  • 选择密文攻击：攻击者可以自行选择密文获取其明文，据此获取密钥的攻击方式
• 流密码
  • LSFR的工作原理：LSFR（线性反馈移位寄存器）是一种根据前几位输出决定下一位输出的周期性的序列发生器。通常是前面几位的异或值得到下一位的值。递推公式为$a_{n}=c_na_0\oplus c_{n-1}a_1\oplus ...\oplus c_1a_{n-1},c_i\in F_q,c_n=1$
  • LSFR分析原理：LSFR的变换矩阵的行数等于参与计算下一位的最前面的一位与该位的位置之差。如$x_n=x_{n-1}\oplus x_{n-3}\oplus x_{n-5}$，则变换矩阵的行数为5。特征多项式$f(x)=|xI-T|=x^n-c_1x^{n-1}-...-c_{n-1}x-c_n$。如果已知长度为2n的明密文对应序列，可以分析出变换矩阵与递推公式。即在模2整数群中计算矩阵逆与乘法运算。
• 唯一解距离和乘积密码体制
  • 伪密钥的概念：解密后存在多个密钥使明密文满足加解密函数时不是真正密钥的称为伪密钥。（如移位密码中26个密钥的解密结果中有不止一个结果具有含义）
  • 自然语言的熵和冗余度：自然语言中有意义的明文串中每个字母的平均信息量。英文的熵为$1.0\le H_L\le 1.5$，通常取1.25（注意：如果按照英文文本中字母出现概率来计算，熵应该为4.19左右，但由于相邻字母之间的出现会有很大的概率影响，取值并非独立，因此是将文本按照若干字母一组的形式计算熵，再除以每一组的字母数量得到单字母的平均熵）。语言的冗余度可以理解为相对于所有字母随机选取的情况，其熵减少的比例：$$R_L=1-\frac{H_L}{\log_2|P|}=\frac{H_0-H_L}{H_0}$$
  • 自然语言的唯一解距离：使得伪密钥出现数量的期望值为0需要的最短分组数量。（能够唯一计算出密钥的密文的平均长度），通过计算$H(K|C^P)=0$求出。

  $$n_0=\frac{\log_2|K|}{R_L\log_2|P|}$$

  • 乘积密码：使用两种密码进行加密，第一种密码加密原明文，第二种密码加密第一种加密算法输出的密文。
  • 幂等密码：某加密体制A，有A²=A，称A为幂等密码体制。即加密一次和两次的明文空间、密文空间、密钥空间、加解密算法均相同。
• 线性密码框架
  • SPN网络加密原理：代换-置换网络。SPN网络在一次迭代中会进行异或、分组代换与置换。异或是输入与流密钥进行异或，分组代换即将异或后的结果分为几组，使用提前确定的代换表进行逐一代换，代换后组合再进行置换输出。
  • Feistel结构的加密过程：每一轮迭代只会加密输入的一半，使用另一半与流密钥的函数（非线性函数，无需可逆）与这一半异或以加密这一半，另一半保留至下一次迭代加密。其加密算法与解密算法相同，密钥逆序使用。
• 线性密码分析
  • 线性逼近分析原理：首先根据代换表画出线性逼近表（通常为16×16，它表示取明文中某些位与密文中某些位异或后结果为0的明密文对数，其值应该为0~16之间的偶数），根据线性逼近表找到偏差较大的几组带入到SPN网络中进行线性逼近分析，追踪受到影响的比特位，选择偏差最大的明密文对进行分析，根据堆积引理计算出输入明文中某些位与输出密文中某些位的异或值的偏差。这是一种已知明文攻击方法，需要较多的明密文对。
  • 差分分析原理：明文选择两个值，这两个值的异或值固定，如果选择的值为4比特位，那么可以选择16个明文对，这16个明文对代换后产生16对输出。我们要研究的是这16对输出的异或值分布情况。如果16对输出中有6对及以上输出的异或值都相等，这就是明显的差分特征，说明输入的差分特征很好地传递给了输出的某个异或值。其中这个值出现的频率称为扩散率。差分链的构建与线性分析类似。
• 几种线性密码
  • AES基本流程：AES的加密流程分为加密和密钥编排两部分。
    • 加密：明文首先与轮密钥进行异或，之后进行若干次迭代。迭代完成之后，再进行一次字节代换、行移位变换、与轮密钥异或后输出密文。一轮迭代中共有四步：字节代换、行移位变换、列混合变换、与轮密钥异或。
    • 密钥编排：将密钥排列成4×4的字节矩阵，每一次编排产生一个新的密钥矩阵作为轮密钥使用。具体方法是：对于新轮密钥的第一列，首先需要当前轮密钥最后一列循环上移1位，之后字节代换与当前轮密钥第一列异或得到。后面的3列则是其前面第一列与其前面第四列异或得到。
  • DES基本流程：DES的加密流程分为加密和密钥编排两部分。
    • 加密：首先进行初始置换，然后需要迭代16次，最后进行逆置换输出密文。一轮迭代中，输入的右半部分直接作为输出的左半部分，输出的右半部分是输入右半部分与轮密钥输入到函数f中后再与输入左半部分异或得到。在函数f中，输入的左半部分从32位经函数E扩展到48位，之后与轮密钥异或，以6位为单位分为8组分别进行代换，最终再进行一次置换后输出。
    • 密钥编排：将64位密钥首先进行置换压缩到56位，然后分为左右两部分进行循环移位，最后压缩置换到48位输出为轮密钥。
• 分组密码的五种工作模式原理与区分
  • 优缺点衡量标准：安全性、错误是否会传播、计算繁简程度、是否可以并行计算或离线计算等
  • ECB：电子密码本模式（Electronic CodeBook），对每一个分组进行分别加密，加密后组合得到密文。每一个分组之间没有任何联系。计算方便，不会产生错误传播，可以并行计算，但安全性低。
  • CBC：密码分组链接模式（Cipher Block Chaining），每一个分组的加密结果与上一个分组的密文有关（本组明文与上组密文异或，因此实际上加密的不是这一组的明文）。会产生错误传播，不能并行计算，安全性较ECB高，可以并行解密。
  • CFB：密码反馈模式（Cipher FeedBack），可以用于实时加密字节级别的数据，存在一个移位寄存器，将移位寄存器中的值与密钥加密之后取与明文长度相同的一块与明文异或得到密文，将密文的一部分或密文本身（如果密文仅为1字节）放入移位寄存器中，移位寄存器移位变换。CFB与CBC的区别是CFB是先加密后异或，CBC是先异或后加密。不能并行计算，会产生错误传播，可以并行解密。
  • OFB：输出反馈模式（Output FeedBack），与CFB类似，不同之处是放入移位寄存器的不是异或之后的密文而是密钥加密之后还没有与明文异或的部分K_i。不能并行计算，不会产生错误传播，可以离线工作（生成移位寄存器的值序列），密钥序列最终会重复。
  • CTR：计数器模式（Counter），将加密的计数与密钥放入加密函数中加密，然后与明文异或得到密文。
• CTS：密文挪用（CipherText Stealing），一种分组密码的填充方式。设分组长度为G，明文长度为kG+a（a<G），加密第k块，也就是最后一个完整块得到C_k，提取其中的后G-a位补充到明文最后面，这样可以和剩下的a位明文凑齐一组再加密一组得到C_k+1。密文的第k个完整块实际上应为C_k+1，后面跟上C_k的前a位，使得密文长度和明文长度相等。在解密时首先解密第k个完整块得到C_k的后G-a位，接到C_k的前a位上解密C_k。
• Hash函数
  • 三个安全性问题
    • 原像问题：给定摘要值y，能否通过某种方式找到x使得y是x的摘要。
    • 第二原像问题：给定消息x，能否通过某种方式找到另一个x₀使得二者的摘要值相等。
    • 碰撞问题：任意选择两个消息能够通过某种方式找到两个摘要值相等。
  • 生日攻击：对于一个输出空间大小为M的随机函数，只需要计算大约$\sqrt M（\sqrt{2M\ln\frac{1}{1-\varepsilon}}）$个函数值就能够以一个不可忽略的概率发现一个碰撞。（$\varepsilon$为成功概率）
  • MD5基本流程：将明文按512字节分为若干组，不够的padding。定义4个魔数，每一组进行64次迭代计算更新这四个数，最终的输出结果就是这四个数的拼接。
  • SHA1基本流程：与MD5类似，不过需要定义5个数，每一块迭代计算80次，且为大端序（MD5为小端序）
  • SM3基本流程：与MD5类似，不过需要定义8个数，每一块迭代计算64次，且为大端序
  • SHA3基本流程：基于Keccak算法的海绵结构，可以接受任意长度的输入，产生任意长度的输出。每一轮迭代需要进行5种计算：$\theta,\rho,\pi,\chi,\iota$。
  • HMAC：报文校验码
    ipad = 3636…36
    opad = 5c5c…5c
    HMAC_K(x)=SHA-1((K$\oplus$opad)||SHA-1((K$\oplus$ipad)||x))【||表示连接】
  • CBC-MAC：基于密码分组链接的校验码。将明文分为等长的段，进行CBC模式加密，将最后一组的加密结果作为校验码。
  • CCM：CTR+CBC-MAC，加密+校验
    T_i=ctr+i mod 2^m，x=x₁||…，y_i=e_k(T_i)$\oplus$x_i
    temp = CBC-MAC(x, K)，y’ = T₀$\oplus$temp，y=y₁||y₂||…||y’
  • 彩虹表：以时间换空间的方法。如果需要暴力破解一个Hash值，常规方法需要存储大量的哈希值，存储空间巨大。彩虹表需要一个从Hash值空间到口令空间均匀分布的函数R，彩虹表由多个链表组成，每一个链表的开头是一个明文，后面接上其对应的Hash值，然后通过这个Hash值输入到R中获得另外一个明文，后面接上这个明文对应的Hash值，如此进行下去。存储时只需要存储一个链中的第一个明文和最后一个明文。给定一个需要破解的Hash值，交替输入到函数R和Hash中，将每一次R的输出结果与每一个链的最后一个明文进行比较，如果存在相等，则彩虹表中某一个链中一定存在明文的哈希值等于给定哈希值。设定彩虹表中每一条链的长度为n，那么只需进行最多n次比较。
• 公钥密码体制
  • 使用中国剩余定理加速解密RSA：解密需要计算$c^d\mod n=m$，拆成$m\equiv c^d\equiv x\mod p,m\equiv c^d\equiv y\mod q$，使用中国剩余定理：$m\equiv xq(q^{-1}\mod p)+yp(p^{-1}\mod q)\mod n$。（不要忘了中国剩余定理）
  • Montgomery算法原理：这是一种不使用除法就能完成的大整数模乘运算。现在需要计算$ab\mod n$，我们需要找到一个大于n的最小的R，使得R是2的k次幂，然后求出$a'\equiv aR\mod n,b'\equiv bR\mod n$这两个数。计算$X_1=a'b'R^{-1}\equiv abR\mod n$，设$a'b'=X$，由此我们只需要计算$X_1R^{-1}\mod n$即可。蒙哥马利算法的关键也就在于如何约简$X_1R^{-1}\mod n$的计算。不难发现由于R是2的幂且与n互素，因此计算$X_1R^{-1}$不需要进行除法运算，只需要右移即可，但为了避免低位因为右移而被截断消失，我们计算$(X_1+mn)R^{-1}\mod n$，其中$X_1+mn$是R的倍数，这样就能保证移位前后值严格相等。现在问题就转化为如何寻找这个m。由扩展欧拉定理可以算出$RR'-NN'=1(0<N'<R,0<R'<N<R)\Rightarrow N'=-N^{-1}$。$X_1+mn\equiv 0\mod R\Rightarrow X_1N'+mNN'\equiv 0\mod R\Rightarrow X_1N'\equiv m\mod R$。这样就求出了m。
    示例：使用蒙哥马利算法计算$56\times78\mod 101$
    容易得到$R=2^7=128,a'=56\times 128=7168,b'=78\times128=9984,X=a'b'\equiv45\mod 101$
    计算$-n^{-1}\equiv19\mod 128$
    $X_1=XR^{-1}\equiv69\mod 101$
    故有$m\equiv69\times19\equiv31\mod 128$
    $X_1+mn=69+31\times101=3200$
    $(X_1+mn)R^{-1}\equiv 25\mod 101$
    计算结果为：25
  • DH密钥交换的实现及中间人攻击：常规的DH密钥交换基于离散对数难题，不难理解，详见PPT。
  • 素性检测算法
    • 伪素数：由欧拉定理已知对于任意素数p和小于p的正整数a都有$a^{p-1}\equiv 1\mod p$。因此对于奇合数n和a如果满足这样的关系，则称n是对于基a的伪素数。又容易知道若p为素数，则$a^{\frac{p-1}{2}}\equiv (\frac{a}{p})\mod p$，因此对于奇合数n和a如果满足这样的关系则称n是对于基a的Euler伪素数。又有Fermat素性检测：若n为奇合数，$n-1=2^st$，t为奇数。有整数a与n互素，且满足$a^t\equiv 1\mod n$，或者存在一个r（0≤r<s）有$a^{2^rt}\equiv -1\mod n$则称n为基b的强伪素数。
    • Solovay-Strassen算法：反复选取a验证n是否是伪素数。验证错误概率不超过1/2。
    • Miller-Rabin算法：反复选取a验证n是否是强伪素数。验证错误概率不超过1/4。
  • 共模攻击原理：在课本RSA密码体系中，如果两个人拥有相同的公钥n，不同的e和d，则一个人发送的加密消息可以被另一个人轻易破解。攻击方M拥有其自己的e、d、密文c、对方A的e、n，其中$c=m^e\mod n$，由RSA加密体系定义可知$e_Ad_A\equiv 1\mod\varphi(n),e_Md_M\equiv 1\mod\varphi(n)$，因此如果有$e_Ad_A\equiv 1\mod(e_Md_M-1)(*)$，则一定有$e_Ad_A\equiv 1\mod\varphi(n)$，其中(*)式可以计算出一个d值用于解密A的消息，这个d不一定等于A本身的d，但一定可以进行解密。如果攻击者是第三者M，A和B具有相同的n，同样可以进行解密：二者加密相同的明文m得到$c_1=m^{e_1}\mod n,c_2=m^{e_2}\mod n$，在e₁、e₂互素的情况下，可以找到r和s使得re₁+se₂=1，那么很容易得到$c_1^rc_2^s\equiv m\mod n$，解出明文。
  • 小加密指数攻击：当e很小的时候，通过Coppersmith算法可以在log(n)的时间之内破解出较小的d（具体算法不要求）。因此建议使用的e最小应为65537，且短消息加密时应该首先进行填充。
  • 小解密指数Wiener攻击：适用于$3d<n^{\frac{1}{4}}$且$q<p<2q$的情况，由于没有讲连分数相关定理与性质，只需要知道$|\frac{e}{n}-\frac{t}{d}|<\frac{1}{3d^2}$，据此算出t（$ed-t\varphi(n)=1$），然后根据$pq=n,(p-1)(q-1)=\varphi(n)$计算q和p的值。
  • ElGamal加解密原理：常规的ElGamal加密中有一个随机数参与，能够有效抵御重放攻击。定义在一个模p的乘法群，选定本原元$\alpha$和其a次方的值$\beta$，a为私钥不可公开。加密选择随机数r，发送$c_1=\alpha^r,c_2=x\beta^r$，x为密文。解密即计算$c_2c_1^{-a}$即可。实际上就是利用了a不可计算的特性，r无论选择什么都没有影响。
  • 数字签名的基本概念与作用：只有信息的发送者才能产生的别人无法伪造的一段数字串，能够证明签名的文本属于所有者发送，没有被修改。
  • ElGamal数字签名原理：与ElGamal加密方式类似，在模p乘法群中，本原元$\alpha$和$\alpha^a=\beta$，a为私钥。发送方计算数字签名$\gamma=\alpha^r\mod p,\delta=(x-a\gamma)r^{-1}\mod p-1$，验证只需要验证$\beta^\gamma\gamma^\delta\equiv\alpha^x\mod p$。这里的r为随机数，将左式中的$\gamma^\delta$中的底数换成$\alpha^r$就很容易发现r可以被消去。
  • DSA数字签名原理：只能用于数字签名的一种算法。在模p乘法群中给定一个阶为q（素数）的元素$\alpha$，和$\beta=\alpha^a$，k为随机数。$$sig_K(x,k)=(\gamma, \delta), \gamma=(\alpha^k\mod p)\mod q,\delta=(\operatorname {SHA-1}(x)+a\gamma)k^{-1}\mod q\
    e_1=\operatorname {SHA-1}(x)\delta^{-1}\mod q,e_2=\gamma\delta^{-1}\mod q\
    ver_K(x,(\gamma,\delta))=true\Leftrightarrow(\alpha^{e_1}\beta{e_2}\mod p)\mod q=\gamma$$
  • PGP：安全协议。由一个对称算法EC/DC/Ks（密钥）、一个非对称加密算法EP/DP/KU（公钥）/KR（私钥）、一个压缩算法Z、哈希函数H。
    • 如果只需要对消息进行认证，则对消息取哈希值之后进行签名（使用私钥与非对称加密算法），将签名附在消息后面，以函数Z压缩发送。认证时首先进行解压缩，使用公钥进行认证即可
    • 如果只需要对消息进行加密，首先对消息进行压缩，使用密钥进行对称加密，使用公钥非对称加密密钥，组合后发送。接受者使用私钥获得对称加密的密钥，然后使用该密钥进行解密。
    • 如果既需要加密又需要认证，则首先进行认证步骤获得一个压缩后的文本，再进行加密。
    • 注：可供选择的对称加密算法：AES、DES、SM4；可供选择的非对称加密算法：RSA、ECC、ElGamal、Rabin、SM2；可供选择的哈希函数：MD5、SHA-x、SM3
    • 安全性分析：信息安全的三个要点是：机密性、完整性、可鉴别性。其中机密性指的是不能从密文直接得知明文；完整性指的是能够发现对密文的恶意修改。一般从机密性和完整性两个方面分析PGP的安全性。首先无论是需要加密还是认证，完整性都是必须要保证的。对于只进行消息认证的PGP，由于添加了数字签名，使得无论是对明文还是对签名进行修改都能够被发现（因为签名是基于明文产生的）；对于只进行加密的PGP，其没有进行数字签名操作，修改加密密钥和密文都会导致明文解密错误，但攻击者可以伪造一条消息并进行加密。对于二者都有的PGP，由于首先就进行了数字签名，因此明文与数字签名无法被修改，而由于对称加密的密钥由公钥加密，因此攻击者也无法获得私钥解密出明文与数字签名。

10. 椭圆曲线密码 ECC

重点在于计算离散椭圆曲线密码的加和与乘积。

对于椭圆曲线方程$y^2\equiv x^3+ax+b\mod m$，计算两个点$P,Q$的加和：
过两点的直线的斜率：$\lambda=\frac{3x^2+a}{2y}(P=Q),\frac{y_Q-y_P}{x_Q-x_P}(P\ne Q)$
其和横坐标$x=\lambda^2-x_P-x_Q$，纵坐标$y=\lambda(x-x_P)+y_P$
（虽然上面的公式在往年椭圆曲线的题目中都会给出，但最好还是记住，其中和的纵坐标不需要记，这就是计算直线上已知横坐标的某点的纵坐标，以点斜式代入直线即可算出。过两点直线的斜率可以通过求导算出，计算量也不大。重点是横坐标公式，需要记忆）

计算加速技巧：① 写出模域中各个元素的方根，然后进行计算对照即可。如计算$y^2=x^3+x+1\mod 19$中某个点的4倍，可以先写出1~18所有数模19的平方根。② 使用类似于平方重复法的方式运算。如计算某个点的16倍，不需要加16次，只需要加4次即可：A+A=2A，2A+2A=4A，4A+4A=8A，8A+8A=16A。以此来获得A的$2^k$倍的值。