现代密码学速通

发表于 2025-06-03 更新于 2025-06-05 分类于 UESTC 阅读次数：本文字数： 18k

UESTC 软件学院互联网安全方向信息现代密码学速通。

现在是 2025 年 6 月 3 日北京时间 20:18，距离 6 月 5 日 16:20 现代密码学考试还有 44 小时 2分钟。

注：如果实在没有时间，可以直接到最后一章的做题环节，但是密码学考的概念非常多，只会计算的话并不能拿到很多分数。

根据复习 PPT，最核心的知识为：

接下来就按照每一章 PPT 的核心知识复习吧。

第一章引言

密码学的基本概念

什么是密码？

密码是指采用特定变换的方法对信息等进行加密保护、安全认证的技术、产品和服务。

什么是密码学？

密码学是研究编制密码和破译密码的技术科学。

密码学的分类

研究密码变化的客观规律，应用于编制密码以保护通信秘密的，成为密码编码学。

应用于破译密码以获取通信情报的，成为密码分析学或破译学。

密码体制攻击的四种类型

唯密文攻击：密码分析者只知道一些密文

已知明文攻击：密码分析者知道一些明文和相对应的密文

选择明文攻击：密码分析者可以选择一些明文，并得到相对应的密文

选择密文攻击：密码分析者可以选择一些密文，并得到相对应的明文

（从上到下攻击强度逐渐增大）

保密系统的安全性分析

保密系统应该满足下述要求：

系统即使达不到理论是不可破的，也应当为实际上不可破的。就是说，从截获的密文或某些已知明文密文对，要决定密钥或任意明文在计算上是不可行的。
系统的保密性不依赖于对加密体制或算法的保密，而依赖于密钥。（Kerckhoff 原则）
加密和解密算法适用于密钥空间中的所有元素。
系统便于实现和使用。

Kerckhoff 假设：假定密码分析者和敌手知道所使用的密码系统。即密码体制的安全性仅依赖于对密钥的保密，而不应依赖于算法的保密。
假设敌手知道：

所使用的加密算法
知道明文的概率分布规律
知道密文的概率分布规律
知道所有可能的破译方法
敌手能够拿到加密装置，可以对其进行能量消耗分析等。

无条件安全

无论截获多少密文，都没有足够信息来唯一确定明文，则该密码是无条件安全的，即对算法的破译不比猜测有优势。

计算上安全

使用有效资源对一个密码系统进行分析而未能破译，则该密码是强的或计算上安全的。

计算上安全的密码算法要满足的准则

破译密文的代价超过被加密信息的价值
破译密文所花的时间超过信息的有用期

单表代替密码

这一部分涉及计算，比较简单，但是需要你会求逆元（拓展欧几里得算法）。

看 PPT 应该直接能看懂。

多表代替密码

这里不单单需要你知道乘法逆元，还需要你复习一下线性代数的知识：求逆矩阵，逆矩阵存在的条件（注意均在模意义下）

$A$ 的逆矩阵存在：$ |A| = 0$

模意义下不要用高斯消元求逆矩阵，因为消元过程中需要进行相当多的除法，都需要求逆元，计算量非常大。

伴随矩阵：$A^* = [(-1)^{i+j}M_{i,j}]^T$（$M_{i,j}$ 就是除去第 $i$ 行，第 $j$ 列的矩阵的行列式）

求逆矩阵：$A^{-1} = \frac{A^*}{|A|} = A^*|A|^{-1}$

一定要求转置，一定要求转置，一定要求转置！！！

严格来说转置在伴随矩阵那里求，但是对于答案来说在哪里求转置没影响，只要记得求转置就行了。

第二章流密码

流密码的基本思想

流密码，又叫序列密码，是一种将明文信息按字符或比特逐位加密的加密方法。

流密码的基本思想是，利用一个密钥 $k$ 产生一个密钥流 $z = z_0z_1z_2...$，并使用如下规则对明文串 $x=x_0x_1x_2...$ 加密：$y = y_0y_1y_2...=E_{z_0}(x_0)E_{z_1}(x_1)E_{z_2}(x_2)...$。

密钥流是由一个密钥流生成器 $z_i = f(k,\sigma_i)$ 产生的，$\sigma_i$ 是加密器中的记忆元件在时刻 $i$ 的状态。

同步流密码：内部记忆元件的状态 $\sigma_i$ 独立于明文字符的叫做同步流密码，否则叫做自同步流密码。对于 $z_i = f(k,\sigma_i)$，由于其与明文字符无关，因此密文字符 $y_i = E_{z_i}(x_i)$ 也不依赖于此前的明文字符。因此，可将同步流密码的加密器分成密钥流产生器（求 $z_i$）和加密变换器（进行 $E_{z_i}(x_i)$ 操作）两个部分。

伪随机序列要满足的条件

一些概念，周期、游程、自相关函数，看 PPT 即可。

Golomb 伪随机公设

在序列的一个周期内，0 与 1 的个数相差至多为 1。（说明 $\{a_i\}$ 中 0 与 1 出现的概率基本上相同）
在序列的一个周期内，长为 $i$ 的游程占游程总数的 $\frac{1}{2^i}$，且在等长的游程中 0 的游程个数和 1 的游程个数相等。（说明 0 与 1 在序列中每一位置上出现的概率相同）
异相自相关函数是一个常数（意味着通过对序列与其平移后的序列做比较，不能给出其他任何信息）

除了 Golomb 伪随机公设，伪随机序列还应该满足：

周期 $p$ 要足够大，如大于 $10^{50}$
序列 $\{a_i,i\ge 1\}$ 产生易于高速生成
当序列 $\{a_i,i\ge 1\}$ 的任何部分暴露时，要分析整个序列，提取产生它的电路结构信息，在计算上是不可行的，称此为不可预测性。（决定了密码的强度，是流密码理论的核心。包含了流密码要研究的许多主要问题，如线性复杂度、相关免疫性、不可预测性等）

线性反馈移位寄存器序列的基本概念

如下图，简单说就是输出 $a_1$，计算新的 $a_{i+n}$ 是线性运算。它是构造密钥流生成器最重要的部件之一。

LFSR 的性质

总是假定 $c_1,c_2,...,c_n$ 中有一个不为 0，否则 $f(a_1,a_2,...,a_n) \equiv 0$
总是假定 $c_n = 1$
LFSR 输出序列的性质完全由其反馈函数决定
$n$ 级 LFSR 状态数：最多有 $2^n$ 个
$n$ 级 LFSR 状态周期：$\le 2^n - 1$ （排除掉全 0 状态）
输出序列的周期 = 状态周期 $\le 2^n - 1$

下面特征多项式 +1 主要是因为把 $a_{n+k}$ 移到一起去了，系数为 1，这样代表所有元素的关系 $p(x) = 0$。

m 序列的定义

选择合适的反馈函数可使序列的周期达到最大值 $2^n - 1$，周期达到最大值的序列称为 $m$ 序列。

判断 m 序列

本原多项式的定义：若 $n$ 次不可约多项式 $p(x)$ 的阶（使 $p(x)\mid (x^p - 1)$ 成立的最小正整数 $p$ ，也叫周期）为 $2^n - 1$，则称 $p(x)$ 是 $n$ 次本原多项式。

$\{a_i\}$ 的周期定理：设 $p(x)$ 是 $n$ 次不可约多项式，周期为 $m$，序列 $\{a_i\}\in G(p(x))$，则 $\{a_i\}$ 的周期为 $m$。

$n$ 级 LFSR 产生的序列有最大周期 $2^n - 1$ 的必要条件：其特征多项式是不可约的。

$\{a_i\}$ 为 $m$ 序列的充要条件：设 $\{a_i\}\in G(p(x))$，$\{a_i\}$ 为 $m$ 序列的充要条件是 $p(x)$ 为本原多项式。

对于任意的正整数 $n$，至少存在一个 $n$ 次本原多项式。所以对于任意的 $n$ 级 LFSR，至少存在一种连接方式使其输出序列为 $m$ 序列。

m 序列的伪随机性

$m$ 序列满足 Golomb 的 3 个随机性公设。

$GF(2)$ 上 $n$ 长 $m$ 序列 $\{a_i\}$ 具有如下性质：

在一个周期内，0、1 出现的次数分别为 $2^{n-1} - 1$ 和 $2^{n - 1}$
在一个周期内，总游程数为 $2^{n - 1}$；对于 $1\le i\le n - 2$，长为 $i$ 的游程有 $2^{n - i - 1}$ 个，且 0、1 游程各半；长为 $n - 1$ 的 0 游程一个，长为 $n$ 的 1 游程一个
$\{a_i\}$ 的自相关函数为：

\[ R(\tau)=\left\{\begin{array}{ll} 1, &\tau=0\\ -\frac{1}{2^{n}-1}, &0<\tau\leq 2^{n}-2 \end{array}\right. \]

求 $m$ 序列的递推关系式

第三章分组密码

分组密码的设计准则

基本概念

每一组长为 $n$，加密成每一组长度为 $m$ 的密文。

安全性设计原则：

混淆原则：将密文、明文、密钥三者之间的统计关系和代数关系变得尽可能复杂，使得敌手即使获得了密文和明文，也无法求出密钥的任何信息；即使获得了密文和明文的统计规律，也无法求出明文的新的信息。可进一步理解为：明文、密钥都不能由已知的明文，密文及少许密钥比特代数地或统计地表示出来
扩散原则：应将明文的统计规律和结构规律散射到相当长的一段统计中去。也就是说让明文中的每一位影响密文中的尽可能多的位，或者说让密文中的每一位都受到明文中的尽可能多位的影响。

分组密码算法应满足的要求

分组长度 $n$ 要足够大，防止明文穷举攻击法奏效
密钥量要足够大，尽可能消除弱密钥并使所有密钥同等地好，以防止弱密钥穷举攻击奏效
由密钥确定置换的算法要足够复杂，充分实现明文与密钥的扩散和混淆，没有简单的关系可循，要能抗击各种已知的攻击
加密和解密运算简单，易于软硬件高速实现
一般无数据扩展
差错传播尽可能小，一个密文分组的错误尽可能少的影响其他密文分组的解密

分组密码的分类

按照加密结构分类

Feistel 结构：将明文块分为左右两半，通过多轮轮函数 $F$ 交换和混合，如 DES。
SPN 结构：通过多轮的代换（S 盒）和置换（P 盒）操作混淆和扩散明文，如 AES。
Lai-Massey 结构：类似 Feistel 结构，但使用加法模运算而非异或。

按密钥长度分类

固定密钥长度：DES
可变密钥长度：AES（128 / 192 / 256）

分组密码的五种工作模式

先记住：有反馈，就是先加密再异或。

电码本模式（Electronic Code Book， ECB）

用相同的密钥分别对明文分组单独加密。

优点：每个数据块独立加密，可并行加密，实现简单。

缺点：相同明文会产生相同密文，不能隐蔽明文分组的统计规律和结构规律，不能抵抗替换攻击。

应用：用于随机数的加密保护、用于单分组明文的加密。

密文分组链接模式（Cipher Block Chaining，CBC）

加密算法的输入是上一个密文分组和下一个明文分组的异或。初始向量（IV）用于第一个块的加密。

优点：

每个密文块的加密依赖前一个密文块，具备数据完整性保护，明文块的统计特性得到了隐蔽。
具有有限的错误传播特性（一个密文块的错误将导致两个密文块不能正常解密）
具有自同步功能（密文出现丢块和错块不影响后续密文块的解密，若从第 $t$ 块起密文块正确，则第 $t + 1$ 个明文块就能正确求出）

缺点：错误传播、不适合并行处理。

密文反馈模式（Cipher Feedback，CFB）

将前一个密文块作为输入进行加密，生成一个密钥流，再与当前明文块进行异或运算得到加密块。

CBC 和 CFB 的区别是前者是先异或后加密，后者是先加密后异或（流密码的方法）。

特点：

按和 CBC 模式加密一样，改变 IV 同样会导致相同的明文输入得到不同的加密输出。IV 无需保密（虽在某些应用中 IV 须是不可预测的）
链接依赖性：类似 CBC 加密，链接机制致使密文组依赖于当前明文组和其前面的明文组，因此，重排密文组会影响解密
错误的传播：一个或多个比特错误出现在任一个 $r$ 比特的密文组会影响这个组和后续 $\lceil \frac{n}{r}\rceil$ 个密文组的解密
错误恢复：CFB 和 CBC 类似，也是自同步的，但它需要有 $\lceil \frac{n}{r}\rceil$ 个密文组才能还原

输出反馈模式（Output Feedback，OFB）

将前一个加密算法的输出作为输入进行加密，生成一个密钥流，再与当前明文块进行异或运算得到加密块。

特点：

相同明文：和 CBC 及 CFB 一样，改变 IV 同样会导致相同的明文输入得到不同的加密输出
链接依赖性：密钥流是独立于明文的
错误传播：有一个或多个比特错误的任一密文字符仅会影响该字符的解密，密文字符的某比特位置出错将致使还原明文的相应位置也出错
错误恢复：OFB 模式能从密文比特错误中得以恢复，但在丢失密文比特后就无法实现自同步了，这是因为丢失密文比特会破坏密钥流的编排

计数器模式（Counter，CTR）

每一个明文分组都与一个经过加密的计数器异或。对每个后续的分组，计数器 +1。

优点：并行处理、随机访问、不受错误传播影响

缺点：计数器必须唯一、密钥流和明文相关性较弱

DES 算法的主要原理及参数

分组长度：64 bits（8 bytes）
密文分组长度：64 bits
密钥长度：64 bits，有 8 bits 奇偶校验（第 8，16，24，...，64 位），有效密钥长度为 56 bits
算法主要包括：初始置换 $IP$、16 轮迭代的乘积变换、逆初始置换 $IP^{-1}$ 以及 16 个子密钥生成器

接下来先通过下图宏观理解一下，再分步讲解。

明文通过初始置换后进行 16 轮迭代，每一轮迭代都是 Feistel 结构，将明文分为左右两组 $L_i,R_i$ ，每一轮都进行 \[ \left\{\begin{array}{ll} L_i = R_{i-1}\\ R_i = L_{i-1}\oplus F(R_{i-1},K_i) \end{array}\right. \] 其中 $F$ 是加密函数，$K_i$ 通过子密钥生成器生成。迭代后进行逆置换。注意最后一轮迭代后得到的 $L_{16},R_{16}$ 要互换。

在分组之前，由于加密消息的长度是随机的，最后一组消息长度可能不足 64 位，需要填充到 64 的倍数。通常用最后一个字节代表填充指示符，它的十进制表示填充了多长。

首先是 $IP$ 置换和逆置换，就是通过表进行一个映射关系，把本来第 $i$ 个数据，放在第 $IP_i$ 位。比如一组 64 位大小分组中，本来在第一位的数据是 0 ，按照下表，就应该第 58 位数据是 0，本来第二位的数据是 1，置换后第 50 位的就是 1。

接下来讲解 $F$ 函数，它是一个轮函数（就是 $F(F(x, y)) = (x, y)$）。

第一步是扩展，将 32 位的数据（因为分为左右两半，每一半都是 32 位）扩展到 48 位。

在选择扩展置换中，首先构造一个表，将 1 到 32 bit 用 4 行 8 列的矩阵按顺序写出，然后往左右两边进行扩展，左边是原矩阵最左边一列减去 1（0 要变成 32），右边是原矩阵最右边一列加上 1（33 要变成 1）。

继续扩展，可以看作我们把这半组 32 bit 又分成了 8 个小组，4 bit 一组，将每一个小组扩展成 6 bit，具体规则为：根据我们构造的置换表，第 1、2、3、4 位所在的组就在左边增加第 32 位的数据，在右边增加第 5 位的数据；第 5、6、7、8 位所在的组就在左边增加第 4 位的数据，在右边增加第 9 位的数据。（其实就是把每一小组的数据都变成扩展表的位置的数据）

接下来，将我们扩展的 48 位明文与 48 位密钥进行异或运算。

然后，我们再用 8 个 S 盒压缩处理得到 32 位数据，具体过程为：将 48 位输入等分为 8 块，每块 6 位输入压缩为 4 位输出，S 盒的使用方法如下：我们把每组数据（6位）拆成两个数：首尾一组组合 $a$，中间四位组合 $b$，将二进制转化为看成十进制。然后我们选择 S 盒行号为 $a$，列号为 $b$ 的数，这个数一定在 0～15 之间，因此就压缩成了 4 位。（下图只展示了 3 组的 S 盒，每一组都有专门的 S 盒）

轮函数的最后一步是 P 盒置换（原理跟 $IP$ 置换一致，都是改变元素的位置），将 S 盒所得结果再经过 P 盒置换。至此，一次轮函数操作完毕，与 $L_{i-1}$ 异或后就是 $R_i$。

接下来讲解密钥生成的过程。

首先去掉 8 位奇偶校验位（8、16、24、32、40、48、56、64），将剩余 56 位进行通过 $PC-1$ 进行置换（不用自己去掉，表中不存在奇偶校验位），然后分为左右两组，通过移位次数表进行循环左移（第 $i$ 次迭代，这一整组一起循环左移相应的迭代次数），再通过置换选择 $PC-2$ 得到 $K_i$。

AES 算法的主要原理及参数

分组长度：明文分组固定长度为 128 比特，密钥长度可变 128、192、256位。不同密钥长度，迭代次数不一样，分别为 10、12、14 轮。
下面均以 128 比特的密钥为例
AES 的轮函数分为 3 层：线性混合层（确保多轮之上的高度扩散）、非线性层（将具有最优的“最坏情况非线性特性”的 S 盒并行使用，确保混淆特性）、密钥加层（单论子密钥简单的异或到中间状态上，实现一次性掩盖）

还是先看一看整体的过程，有一个把握。

明文经过初始变换后，进行 10 轮迭代，除了最后一轮迭代，都是依次进行字节代换、行移位、列混合、轮密钥加，而最后一轮迭代是没有列混合的。

首先，明文分组 128 位，也就是 16 个字节，我们把这 16 个字节填充进一个矩阵，按照从上到下，从左至右的顺序填充（注意是一列一列填充），密钥也同样处理。

初始变换就是将两个矩阵相异或。

然后就是 9 轮循环。

第一步操作是字节代换，通过 S 盒进行代换，如下图，比如 19 就代换为第 1 行第 9 列的数据 d4。这样得到一个新的矩阵。

然后是行移位，第一行不变，第二行循环左移 1 个字节，第三行循环左移 2 个字节，第四行循环左移 3 个字节。

接着是列混合，将输入的数据左乘一个给定的 $4\times 4$ 矩阵（模 $x^4+1$ 可逆），注意这里的矩阵乘法和正常矩阵乘法有区别，是定义在 $GF(2^8)$ 上的，规则如下（把相乘相加改为相乘相异或，同时相乘也不是正常相乘，见下图，最高位为 0 直接左移一位，否则左移一位的结果还要异或上一个常数\[(00011011)_2\]）：

最后就是轮密钥加，就是将得到的矩阵异或子密钥矩阵。

然后讲解一下轮密钥矩阵的产生。

首先是密钥扩展，将初始 16 个字节填充的密钥矩阵扩展，规则见图片，不是 4 的倍数的话就是简单的前一列和前面第四列异或；否则前面第四列还要额外进行一次 $T$ 函数后异或前面第四列。

$T$ 函数包括三步：字循环（就是把那一列循环上移一位）、字节代换（使用 S 盒进行一次代换）、轮常量异或（常量是给定的，共 10 个，将前两步的结果同轮常量进行异或）。这样一定可以得到 10 个轮密钥。

SM4 算法参数设置

SM4 （又叫 SMS4）是我们国内官方公布的第一个商用密码算法
它是一个分组密码算法，分组长度和密钥长度均为 128 比特
加密算法与密钥扩展算法都采用 32 轮非线性迭代结构
非线性变换中使用的 S 盒是一个具有很好密码学特性的、有 8 比特输入产生 8 比特输出的置换，在设计原理上，SM4 比 AES 的 S 盒设计多了一个仿射变换
SM4 有很高的灵活性，它所采用的 S 盒可以灵活地被替换，以应对突发性的安全威胁
算法的 32 轮迭代采用串行处理，这与 AES 中每轮使用代换和混淆并行地处理有很大不同

算法整体流程如下：32 轮迭代 + 1 次反序变换（得到的 $x_{32},x_{33},x_{34},x_{35}$ 变成 $x_{35},x_{34},x_{33},x_{32}$），还有生成 32 个轮密钥的算法。

然后讲一下轮函数 $F$，$F(x_{i+4}) = x_i\oplus T(x_{i+1}\oplus x_{i+2}\oplus x_{i+3}\oplus rk_{i})$，生成新的密文依赖于前面的密文，因此这是一个串行的算法。

$T$ 函数如下，就是一个非线性变换 $\tau$（查 S 盒置换，每组 128 位也就是 16 个字节，再分成 4 组，每组对应一个 S 盒，因此共四个 S 盒，类似 AES 的 S 盒置换过程）和线性变换 $L$（自身异或上循环左移 2、10、18、24 位的结果），

密钥生成好像没有特别要求，这里就不写啦。

AES 和 SM4 的 S 盒构造的区别

二者选取的不可约多项式不相同（SM4 未公开）
二者构造方式不相同：在设计原理上，SM4 比 AES 的 S 盒设计多了一个仿射变换（AES 只有一次，SM4 有两次）
SM4 有很高的灵活性，它所采用的 S 盒可以灵活地被替换，以应对突发性的安全威胁

第四章公钥密码

公钥密码的基本思想

传统对称密码算法的缺陷

密钥分配问题：通信双方加密通信前要通过秘密的安全信道协商加密密钥，这种安全信道很难实现；对这个信道安全性的要求比正常传送消息信道的安全性要高
密钥管理问题：多用户网络中，任何两个用户之间都需要有共享的秘密钥，共 $n*(n-1)/2$ 个，系统开销非常大
没有签名功能：当主体 A 收到主体 B 的电子文档时，无法向第三方证明此电子文档确实来源于 B，传统单钥加密算法无法实现抗抵赖的需求

公钥密码体制：每个用户生成一个密钥对：一个公钥 $pk$ 和一个对应的私钥 $sk$，公钥在系统内被公开，由系统中其他用户使用，私钥由用户本人保管，由用户本人使用。公钥密码体制也被称为非对称密码体制。
公钥密码算法应该满足的要求（一生成、两个计算容易、两个计算不可行）：

接收方产生密钥对在计算上是容易的。
发送方对消息 $m$ 加密以产生密文 $c$，即 $c = E_{pk}(m)$ 在计算上是容易的。
接收方用自己的私钥解密信息，即 $m = D_{sk}(c)$ 在计算上是容易的。
敌手由 $pk$ 求 $sk$ 在计算上是不可行的。
敌手由密文 $c$ 恢复明文 $m$ 在计算上是不可行的。

RSA 算法原理及相关安全性分析

算法过程参见上学期的信息安全数学基础，这里不多说了（但是需要你会计算）。

解密还需要你掌握快速幂算法和中国剩余定理（CRT）算法

RSA 的安全性：基于分解大整数的困难性。
直接确定 $\varphi(n)$ 等价于对 $n$ 分解

为了保证算法的安全性，还对 $p,q$ 提出以下要求：

$\mid p - q\mid$ 要大
$p,q$ 的长度相差不多
$p - 1$ 和 $q- 1$ 都应该有大素因子
$\gcd(p-1,q-1)$ 应该很小

对 RSA 的攻击

下面的选择密文攻击就是能够选择一个明文 $m$ 构造一个新的密文 $c_2 = c_1m^e$，发送给接收方让它解密得到 $m_2$，我们要求密文 $m_1$ 就可以 $m_1 = m_2m^{-1}$

El Gamal 算法原理及相关安全性分析

信息安全数学基础也学过。

特点：

安全性基于有限域上离散对数的难解性
加密算法是概率算法
不能抵抗选择密文攻击
存在密文扩张

El Gamal 安全性
参数要求：$p$ 应该为 150 位以上十进制数，500 位以上的二进制数，$p - 1$ 应该有大素数因子。
随机数 $k$ 必须是保密的且必须是一次性的。

选择密文攻击

RSA 的：

El Gamal 的：

第五章 MAC 和 Hash 函数

消息认证码的定义及构造

消息认证码：指消息被一密钥控制的公开函数作用后产生的用作认证符的固定长度的数值，或称为密码校验和。需要通信双方 A、B 共享一密钥 $K$，如果仅收发双方知道 $K$，且 B 计算得到的 MAC 与接收到的 MAC 一致，则这就实现了：接收方相信发送方发来的消息未被篡改，接收方相信发送方不是冒充的。
表示形式为：$M \mid\mid C_K(M)$，其中 $\mid\mid$ 代表连接，指需要传入明文和明文的加密进行验证
认证码生成

具体流程如图。首先将明文分组，计算奇偶校验码，然后开始利用 CBC（密文分组链接模式）加密明文和其校验码，最后得到的 $c_{n+1}$ 就是认证码。如果仅需对明文认证,而不需加密时, 则传送明文 $m$ 和认证码 $C_{n+1}$ ，此时也可仅保留 $C_{n+1}$的 $t$ 个比特作为认证码；当既需对明文认证，又需要加密时，传送密文 $C$ 和认证码 $C_{n+1}$

认证码校验

当仅需对明文认证而不需加密时，此时验证者仅收到明文 $m$ 和认证码 $C_{n+1}$，他需要：首先产生明文 $m$ 的校验码 $r$，然后利用共享密钥使用 CBC 模式对 $(m,r)$ 加密，将得到的最后一个密文分组与接收到的认证码 $C_{n+1}$ 比较，二者一致时判定接收的明文无错；二者不一致时判定明文出错。

当既需对明文认证,又需要加密时，他首先利用共享密钥解密密文 $C$ 得到明文，然后再计算明文的校验码，最后用 CBC模式对 $(m,r)$ 加密，将得到的最后一个密文分组与接收到的认证码 $C_{n+1}$ 比较，二者一致时判定接收的明文无错；二者不一致时判定明文出错。

这样就能判定在传输过程中完整性是否被破坏。

杂凑函数的定义及性质

Hash 函数是将任意长的消息 $M$ 映射为较短的、固定长度的一个值 $H(M)$，$H$ 一般是公开的
Hash 函数也被称为哈希函数、散列函数、压缩函数、杂凑函数、指纹函数等。其函数值 $H(M)$ 为哈希值、散列值、杂凑码、指纹、消息摘要等。
Hash 函数的目的是为需认证的数据产生一个“指纹”，应满足以下条件：

Hash 函数的输入可以是任意长
Hash 函数的输出是固定长
易于在硬件和软件实现

同时，Hash 函数为了实现安全认证，需要满足如下安全条件（它们是安全性依次增强的，后者一定包含前者）：

单向性：已知 $x$，求 $H(x)$ 较为容易；但是，已知 $h$，求使得 $H(x) = h$ 的 $x$ 在计算上是不可行的
抗弱碰撞性：已知 $x$，找出 $y\ne x$ 且 $H(y) = H(x)$ 在计算上是不可行的
抗强碰撞性：找出任意两个不同的输入 $x,y$，使得 $H(x) = H(y)$ 在计算上是不可行的

杂凑函数设计的一般模式

大多数经典杂凑函数（如 MD5、SHA-1、SHA-2）采用 Merkle-Damgård（MD）结构，分为以下步骤：

消息填充：将输入消息长度填充至满足分块要求（如 512 位或 1024 位的倍数）。方法为附加一个 1 比特，后接若干 0 比特。最后附加消息长度的二进制表示（64 位或 128 位）。比如 SHA-256 中，原始消息长度 $L$ 比特，填充后为 $K\times 512$ 比特。
分块处理：将填充后的消息分割为固定大小的块
初始化向量（IV，initial vector）：设置初始哈希值 $H_0$ ，是一个固定常量
压缩函数：迭代处理每个消息块 $M_i$，更新哈希值 $H_i = F(H_{i-1},M_i)$
输出哈希值：最终哈希值为最后一轮的输出 $H_N$

压缩函数的设计方法

基于分组密码，依赖于分组密码的抗碰撞性
自定义非线性运算

SHA-1 的分组长度、填充、摘要长度、迭代轮数

SHA-1 算法的输入：小于 $2^{64}$ 比特长的任意消息，分为 512 比特长的分组
SHA-1 算法的输出：160 比特长的消息摘要
抗碰撞性：SHA-1 已被证明不具备抗碰撞性（实际复杂度低于理论值），不推荐用于安全场景（如证书签名），可用 SHA-256 或 SHA-3 替代。
基本过程如下：

首先是分组，每组 512 位，最后一组可能没有达到 512 位，需要一个填充，是 448 + 64 的结构（448 包含最初的消息，后面添加一个 1，再全补 0 补到 448 位，剩余的 64 位是表示原始消息的长度，因此输入小于 $2^{64}$）。然后每组是一个 80 轮的迭代，得到一个 160 位的数，并且参与下一组的迭代。最终生成一个 160 位的消息摘要。

有闲心的话可以记一下 80 轮迭代中的一些基本逻辑函数

SM3 的分组长度、填充、摘要长度、迭代轮数

SM3 是一类密码杂凑函数，可用于生成数字签名及验证、消息认证码生成及验证、随机数生成。
SM3 分组长度、填充和 SHA-1 完全相同。
SM3 摘要长度为 256 比特。
SM3 迭代轮数为 64 轮
迭代过程如下（相当复杂，感觉没必要看）：

HMAC 算法

HMAC（Hash-based Message Authentication Code），是一种结合散列函数和密钥，使用密钥对消息进行哈希运算，生成固定长度的哈希值。它使用的单向散列函数不止一种，任何高强度的单向散列函数都可以被用于 HMAC。
HMAC 的设计目标：

可不经修改而使用现有的哈希函数
其中镶嵌的哈希函数可易于替换为更快或更安全的哈希函数
保持镶嵌的哈希函数的最初性能
以简单方式使用和处理密钥
在对镶嵌的哈希函数合理假设的基础上，易于分析 HMAC 用于认证时的密码强度

计算方法

函数为：$H(\text{opad}\oplus key \mid\mid H(ipad\oplus key\mid\mid \text{message}))$，就是进行两次哈希，每次哈希的内部都是 xxx 异或 key 之后连接一个 message。外层的 xxx 是 opad（0x5c 循环到位数足够），内部是 ipad （循环 0x36 到位数足够），message 外层用内层加密的值，内层就是消息。

看图即可理解。

第六章数字签名

数字签名应具有的特性

数字签名是用于对数字信息签名，以防消息的伪造或篡改，也可用于通信双方的身份鉴别。
数字签名应该具有的特性：

签名是可信的：任何人可验证签名的有效性
签名是不可伪造的：除合法签名者外，其他人伪造签名是困难的
签名是不可复制的：一消息的签名不能复制为另一消息的签名
签名的消息是不可改变的：经签名的消息不能被篡改
签名是不可抵赖的：签名者事后不能否认自己的签名（注意 MAC 是可以否认的）

RSA 数字签名体制的原理、弱点及改进

数字签名都是三步：密钥生成、签名算法、验证算法

用私钥加密，将消息和密文发给别人，别人用公钥验证是否匹配。

RSA 签名体制的缺点

由于公钥是公开的，任何人都可以计算 $x = y^e\pmod n$，任何人都可以伪造对随机消息 $x$ 的签名（尽管不能匹配）
如果消息 $x_1,x_2$ 的签名分别为 $y_1,y_2$，则知道 $x_1,y_1,x_2,y_2$ 的人可伪造对消息 $x_1x_2$ 对签名 $y_1y_2$
签名的消息 $x\in Z_n$，所以每次只能对 $\lfloor\log_2 n\rfloor$ 位长的消息进行签名（大小不能超过 $n$ ，长度就取对数），签名速度慢。

克服缺陷的方法：签名之前先求消息的 Hash 值。（针对第 2 点和第 3 点，因为 $H(x_1x_2)\ne H(x_1)H(x_2)$）

El Gamal 数字签名体制

不同于 RSA，使用 El Gamal 的加密和签名的计算过程是不一样的，需要着重记忆，还要注意 $s$ 的模数是 $p - 1$。

签名为： \[ \left\{\begin{array}{ll} r = g^k\pmod p \\ s = (H(m) - rx)k^{-1}\pmod {p-1} \end{array}\right. \] 然后把 $\{r, s, H(m)\}$ 都发出去，别人验证 $y^rr^s$ 是否等于 $g^{H(m)} \pmod p$。

还要注意不能用同一个 $k$ 做两次签名，可以求出 $k,x$，因为是一个二元一次方程组： \[ \left\{\begin{array}{ll} H(m_1) = rx + ks_1 \pmod{p-1} \\ H(m_2) = rx + ks_2\pmod{p - 1} \end{array}\right. \]

还有个引申的 Schnorr 签名，看看就好

第七章密码协议

快结束啦，加油！

Diffle-Hellman 密钥交换原理及安全性

主要是解决对称密码体制中，通信的双方需要使用同一个密钥的共享方案

很简单，就是两边协商一个素数 $p$，各自选择一个随机数 $x$ 计算 $p^x$ 发给对面，再把接收到的数用自己的随机数求一个幂，这样两边的密钥都是一样的了。

安全性上，存在中间人攻击，就是有一个中间人 C 拦截 A、B 的消息，并用自己的随机数加密发给对面，这样 AC 之间共享一个密钥，BC 之间共享另一个密钥，中间人 C 可以获得 AB 之间互传的信息。

Shamir 门限方案

门限方案的一般概念：将秘密 $s$ 分为 $n$ 个部分，每个部分称为 shadow，由一个参与者持有，使得由 $k$ 个或多于 $k$ 个参与者所持有的部分信息可重构 $s$，由少于 $k$ 个参与者所持有的部分信息则无法重构 $s$。我们把这样的方案称为 $(k, n)$ 秘密分割门限方案，$k$ 成为门限值。
如果少于 $k$ 个参与者所持有的部分信息得不到 $s$ 的任何信息，称该门限方案是完善的。
门限方案由份额分配算法和恢复算法构成。
Shamir 门限方案

首先我们需要了解一下基本原理，是多项式的知识：$k-1$ 次多项式需要由 $k$ 个点唯一确定（两点确定一次函数，三点确定二次函数）。

有了这样的知识，门限值为 $k$ 的话，我们就设一个 $k-1$ 次函数 $y = a_1x^{k-1} + a_2x_{k-2} + ... + a_{k-1}x + S$，其中 $S$ 是我们的秘密，$a_i$ 是随机参数。然后我们在这个函数上取 $n$ 个不同的点分给 $n$ 个人，这样一来，只要 $k$ 个人都分享出自己得到的坐标，就能唯一确定这个函数，即可知道秘密 $S$。

但是为了防止穷举攻击，我们把上述函数定义在有限域上，由于取模的存在，这样的话画出来的图像就不是光滑的曲线了，就将有规律、可穷举的普通多项式变成了无规律、难穷举的循环多项式。

而在有限域上，为了解出这个多项式，需要使用拉格朗日插值法（你都速通了就别了解原理了，直接背下面的公式，看一下例子吧）。

例子是：$y = ax^2 + bx + S \pmod{23}$，分成 4 份，$(1,7),(2,16),(3,6),(4,0)$ ，现在通过三份秘密 $(1,7),(3,6),(4,0)$ 求出 $S$。

计算基多项式，把 $x$ 代成 0。

然后计算秘密 $S$，按照公式，把我们求出的三份（$i = 1,3,4$）代入公式即可，不需要管 $i=2$。

然后可以看一下 PPT 上的严谨一些的定义和例子。

Kerberos 协议

Kerberos 协议是 MIT 开发的一种身份鉴别服务，提供了一个集中式的认证服务器结构，实现用户与其访问的服务器间的相互鉴别。Kerberos 建立的是一个实现身份认证的框架结构，其实现采用的是对称密钥加密技术，而未采用公开密钥加密。
Kerberos 的设计目标：

安全性：能够有效防止攻击者假扮成另一个合法的授权用户
可靠性：分布式服务器体系机构，提供相互备份
对用户透明性
可伸缩：能够支持大数量的客户和服务器

Kerberos 的基本思路：使用一个（或一组）独立的认证服务器（AS，Authentication Server），来为网络中的用户（C）提供身份认证服务；用户口令保存由 AS 保存在数据库中，AS 会与每个服务器（V）共享一个唯一保密密钥 $K_V$。

一次性口令协议

前几章提到的“密码”并不是我们日常生活中“账号密码”中的“密码”，日常生活中的“密码”在密码学中叫做“口令”。

一次性口令：在登录过程中加入不确定因素，使得每次登录过程中传送的信息都不相同。这样可以避免重放攻击（有的系统会将认证信息进行简单加密后进行传输，如果攻击者无法用第一种方式推算出密码，可以使用截取 / 重放方式，需要的是重新编写客户端软件以使用加密口令实现系统登录）
不确定因素的方法：

口令序列
挑战 / 回答
时间戳

口令序列

根据下面的描述看图理解一下吧。

有两个角色：客户端和 S/KEY 服务器，客户端生成并存储口令序列，S/KEY 服务器验证客户端提交的口令，并维护下一个预期口令 $x_{n+1}$。

生成初始口令序列是先产生一个随机数，通过一个单向函数 $f$，依次计算 $x_1,x_2,...,x_n$，客户端完整存储，而服务器仅存储最后一个值 $x_{n+1}$（初始时未使用）。

然后客户端将 $x_1$ 通过安全信道发送给服务器，服务器存储 $x_1$ 作为验证起点。

认证的流程是：客户端取出存储的口令 $x_n$，计算 $x^\prime_n = f(x_n)$ 并发送给服务器，服务器收到 $x^\prime_n$ 后与本地存储的 $x_{n+1}$ 比较，比较成功即认证成功，否则拒绝。

该方法体现一次性的地方（下图没有）：认证成功后，服务器将 $x_{n}$ 作为新的预期口令，即 $x_{n+1} \leftarrow x_{n}$，下次认证时，客户端需要使用 $x_{n-1}$，序列用尽后需重新初始化。

挑战 / 回答

客户端输入口令后，先给服务器发送登录的请求，服务器给客户端返回一个随机数 $R$，客户端将口令 $PW$ 加上 $R$ 之后进行哈希 $h = f(PW + R)$，再把 $h$ 发送给服务器。服务器通过本地存储的密码进行验证，求 $h^\prime = f(PW^\prime + R)$，若 $h = h^\prime$ 则认证成功。

时间戳

就是把上面的随机数换成用户名 + 时间戳做哈希。

知识点结束啦，恭喜🎉🎉🎉！！！

还有时间的话看看做题吧。

最爱的做题环节

其实知识点那里写了很多做题方法了，这里把题目集中一下吧。

题型：分值没写，综合题改成 1 题 30 分了好像。

2022级真题：可以看到还是概念题居多。

下面绝大部分都是计算题，概念题可以去 MOOC 看看。

乘法密码需要与 26 互素，根据欧拉公式，$26 = 2\times 13,\varphi(26) = (2 - 1)\times(13 - 1) = 12$，因此乘法可以选择 12 个 $a$。

加法取 $b\in [0, 25]$ 均可，共 26 个数，因此 $a,b$ 组合共有 $12\times26 = 312$ 个。

回顾：求乘法逆元、逆矩阵（伴随矩阵法）。

下面的做法对于伴随矩阵没求转置，而是放在最后转置了。所以伴随矩阵是错的，答案是对的。

给出特征多项式，一个规律是次数高的反而对应着下标更小的 $a_m$，且每一组 $a_{m}x^c$ 的 $m + c$ 应该是一个定值。

那么 $p(x) = x^3 + x^2 + 1$ 中，最低次 $1 = x^0$ 是我们要求的，设常数为 $3 + k$（随便设，最后得到的递推关系调整下下标就行了），那么 $x^3$ 对应 $a_{(3 + k) - 3} = a_k$，$x^2$ 对应 $a_{(3 + k) - 2} = a_{k + 1}$，那么最终的递推式就是 $a_{3+k} = a_{k}\oplus a_{k+1}$。

再举个例子：设常量为 $k + 4$，同样的方法可以得到 $a_{4 + k} = a_{k} \oplus a_{k +3}$，调整一下下标就是 $a_{k} = a_{k - 4}\oplus a_{k-1}$。