《密码学导论》复习笔记
针对北京理工大学2025-2026-1密码学导论课程的复习
密码学导论
一、理论基础
符号规则
- 密钥生成：$Gen$
- 加密：$Enc_k(m) = c$，其中 $k$ 是密钥，$m$ 是明文，$c$ 是密文。
- 解密：$Dec_k(c) = m$。
- 定义概率：$Pr[A]$，形式上不同于概率论的 $P{A}$，其中 $A$ 代表事件或条件。例如：$Pr[M=m]$ 代表明文 $M$ 为 $m$ 的概率。
定义攻击实验
\(PrivK^{type}_{A, \pi} (n)\)
其中：
- type 指的是攻击类型
- $A$ 代表攻击者
- $\pi$ 代表加密方案
- $n$ 代表安全参数
- $PrivK^{type}_{A, \pi} (n) = 1$ 代表以 type 类型的攻击成功了，为 0 则代表失败。
- ${0,1}$ 是一个均匀概率选择器，可以理解为抛硬币，其保证概率均匀地返回 0 或者 1。
科尔霍夫原则（Kerckhoffs’s Principle）
密码系统的安全性并不依赖加密算法的保密，而是依赖于密钥的安全性。
无条件安全
即使攻击者有无限的资源，也无法攻破密码体制，那这个密码体制就是无条件安全的。无条件安全又被称为完善保密（Perfect Secrecy）。这类算法的特点是在指数时间下也无法破解。 即无法从密文获得明文的任何信息。
无条件安全有如下等价定义：
- 无条件安全的加密方案：明文空间为 $\mathcal{M}$ 的加密方案 $\Pi = (Gen, Enc, Dec)$ 是无条件安全的，如果对于 $\mathcal{M}$ 的任意概率分布，任意明文 $m \in \mathcal{M}$ 和任意密文 $c \in \mathcal{C}$ 且 $Pr[C=c] > 0$，均满足： \(Pr[M=m | C=c] = Pr[M=m]\)
- 等价推导： \(Pr[M=m | C=c] = Pr[M=m] \iff Pr[C=c | M=m] = Pr[C=c]\)
不可区分性
- 完美不可区分：加密方案 $\Pi = (Gen, Enc, Dec)$ 是完美不可区分（perfectly indistinguishable）的，如果对所有敌手 $A$，
\(Pr[PrivK^{eav}_{A, \Pi} = 1] = \frac{1}{2}\)
$\Pi = (Gen, Enc, Dec)$ 是完善保密的当且仅当它是完美不可区分的。
即对这种密码体系各种攻击成功的概率等于随意猜测的概率。通俗来说，就是一顿操作猛如虎，愕然发现还不如不操作，瞎猜和操作成功的概率是一样的。
香农定理
通俗理解是要实现完善保密（无条件安全），那么密钥的长度一定要大于等于明文的长度。
计算安全
攻击者具有有限的资源，很难攻破密码体制，那我们就称这个为计算安全的。
- 有限的计算资源指敌手是概率多项式时间（PPT）的算法。
- 很难攻破密码体制指敌手成功的概率是一个可忽略函数（negligible function）。
- 与完善保密（无条件安全）的区别是攻击者能力有限，且虽然攻破密码体制很难，但也不是完全没有可能。
计算安全定义：加密方案 $\Pi = (Gen, Enc, Dec)$ 在唯密文攻击下是计算安全的，如果对所有 PPT 敌手 $A$， \(Pr[PrivK^{eav}_{A, \Pi} = 1] \le \frac{1}{2} + negl(n)\)
典型攻击类型
密码学中常见的攻击模型有：唯密文攻击（COA）、已知明文攻击（KPA）、选择明文攻击（CPA）、选择密文攻击（CCA）。核心区别在于攻击者拥有的信息或能力不同，强度从弱到强排序为： 唯密文攻击 < 已知明文攻击 < 选择明文攻击 < 选择密文攻击
- 唯密文攻击（COA）：攻击者仅获取到若干密文，无明文、无密钥，也无法干预加解密过程，目标是恢复密钥或破解出对应的明文。特别地，EAV 是窃听者模型，在这里等同于唯密文攻击。
- 已知明文攻击（KPA）：攻击者拥有若干明文-密文对应关系，目标是通过这些对应关系推导密钥，进而破解其他密文。
- 选择明文攻击（CPA）：攻击者可以主动选择任意明文，并通过被允许的查询手段获取对应的密文，目标是通过自定义的明文-密文关系推导密钥。
- 选择密文攻击（CCA）：攻击者可以主动选择任意密文，并通过被允许的查询手段获取对应的明文，目标是推导密钥或破解目标密文。
二、古典密码
代换密码
核心是把一个字母代换成另一个字母。
- 移位密码：密钥空间是 26，特例是凯撒密码（密钥为 3）。攻击手段是词频分析法。
- 单字母代换：
- 维尼吉亚密码：攻击方式可以是唯密文攻击，需要知道密钥长度，可以通过 Kasiski 测试法获取，然后用重合指数法。攻击方式也可以是已知明文攻击、选择明文、选择密文。
Q: 代换密码一定是无条件安全的吗？ A: 单表代换一定不是无条件安全的，多表代换有可能是无条件安全的。当不知道密钥长度时，多表代换是无条件安全的；知道密钥长度时，多表代换不是无条件安全的。
置换密码
只更换现有字符的位置，而不产生新的字符。
三、流密码
其加密过程可以概括为：将密钥扩展到与明文等长，加密算法采用异或操作，其安全性主要在于密钥扩展后的随机性。密钥扩展依赖伪随机数发生器，一般定义这个伪随机数函数为 $G$。
随机数的性质：应该在给定范围内均匀地分布。每个随机数的生成应该是独立的，即前一个随机数的值不应该对后续随机数的生成产生影响。无法通过已知的信息或模式来推测下一个随机数的值。
选择明文攻击下的不可区分性实验
流密码在唯密文攻击下是安全的，但是若随机数生成器是确定的，则在选择明文攻击下是不安全的。具体来说，确定性加密算法（Deterministic Encryption）一定不是 CPA 安全的，一般用 IND-CPA 实验（Indistinguishability under Chosen-Plaintext Attack，选择明文攻击下的不可区分性实验）来证明：
定义一个实验：
\[PrivK^{CPA}_{A, \pi} (n)\]敌手 $A$ 向对面发送无数次明文 $m$ 并获得无数次密文 $c$，最终敌手发送长度为 $k$ 的等长明文 $m_0$ 和 $m_1$，对面使用 ${0,1} \to b$ 返回一个密文 $c = Enc_k(m_b)$，敌手猜测是 $m_0$ 还是 $m_1$，如果猜对了，$PrivK^{CPA}_{A, \pi} (n) = 1$，否则为 0。
显然，如果这里的密钥 $k$ 以 $G: {0,1}^n \to {0,1}^{l(n)}$ 生成，即确定性加密，只要输入一样输出就一定一样的话，敌手在第一次攻击时发送任意 $m \in {0,1}^{l(n)}$，显然会得到 $c=Enc_k(m)$，之后构造等长密文时，可以直接令 $m_0=m$，这样由于确定性加密，$c_0=Enc_k(m_0)=Enc_k(m)=c$，敌手就可以通过上一次的结果判断是否为 $m_0$，这样的概率显然不是均匀的，猜对的概率明显上涨，不可忽略，所以说基于确定性加密的流密码是 CPA 不安全的。而基于此，可以证明，任何基于确定性加密的密码都是 CPA 不安全的。
所以，要实现选择明文攻击安全，就必须要引入随机数，使得一次一密。 伪随机数发生器是希望用 $2^n$ 个伪随机数来模拟 $2^{l(n)}$ 个随机数。
序列密码
序列密码产生的核心是生成随机数，生成的核心是反馈位移寄存器，有线性的和非线性的。需要注意的是，线性反馈位移寄存器是有周期的，所以是伪随机。 如果选择了合适的反馈函数使序列的周期达到最大值 $2^n - 1$，则周期达到最大值的序列称为 m序列。 线性反馈移位寄存器（LFSR）的输出序列作为密钥流容易被代数方法攻击，所以需要引入非线性性。
ZUC 密码
祖冲之密码（ZUC）是国密算法的一种，它是一种同步序列密码，在实际应用中可以用来替换 RC4 算法。长度可以是 128 位或者 256 位。
- 上层为 LFSR：线性驱动部分首次采用素域 $GF(2^{31}-1)$ 上的 $m$ 序列作为源序列；
- 中层为比特重组 BR：衔接上层 LFSR 和下层非线性函数；
- 下层为非线性函数 F：借鉴了分组密码的设计思想，采用性质良好的线性变换和 S 盒。
ZUC 算法整体结构及设计理念：
- 密钥载入：种子密钥 SK 和初始向量 IV 载入到 LFSR 的寄存器 $s_0, s_1, \dots, s_{15}$ 作为其初始状态。运行初始化模式过程 32 次，完成密钥载入。
- 密钥流生成：密钥载入之后，进行一次（不输出密钥字的）迭代过程，然后进入密钥字输出过程：算法每迭代 1 次，输出一个 32 比特的密钥字 $z$。
四、分组密码
分组密码：
- 将明文分割成等长的分组（比如 64 比特，128 比特），定义一个二元函数 $F(\cdot, \cdot)$，密钥 $k$ 作为其中一输入定义了一个映射 $F(k, \cdot) = F_k(\cdot)$，将每个明文分组在这个映射下对应的像作为密文。
- 算法一般交替使用混乱和扩散技术，以实现伪随机函数。
- 伪随机函数用于生成伪随机数，类似伪随机数发生器，但不需要扩展。
- “分组密码算法的安全性依赖函数分布 ${F_k(\cdot)}_{k \gets {0,1}^n}$ 的伪随机性。”
在此处，我们说伪随机数函数共有 $2^n$ 种映射，真正的随机函数有 $2^{n \cdot 2^n}$ 中映射，可以与前文流密码进行对比着说，希望用 $2^n$ 个伪随机数来模拟 $2^{n \cdot 2^n}$ 个随机数。
如何形式化定义？
- $f: {0,1}^n \to {0,1}^n$ 共有 $2^{n \cdot 2^n}$ 种
- 需要 $n \cdot 2^n$ 比特来刻画一个函数 $f$
- 甚至不能在 $n$ 的多项式时间内读取！
- $\star$ 令区分器可以访问函数的应答器（oracle/预言机）用以区分函数。
从而可以定义分组密码方案（构造方案 4.1）： 令 $F$ 是伪随机函数，定义一个消息长度为 $n$ 的对称加密方案如下：
- Gen: 输入：安全参数 $n$，输出：$k$， $k$ 是一个 ${0,1}^n$ 均匀分布中随机取出的一个整数
- Enc: 输入：$(k, m)$，输出：$c = (c_1, c_2) \leftarrow (r, F_k(r) \oplus m), r \gets {0,1}^n$
- Dec: 输入：$(k, (c_1, c_2))$，输出：$m \leftarrow F_k(c_1) \oplus c_2$
定理：如果 $F$ 是一个伪随机函数，则构造方案 4.1 是对定长消息的选择明文攻击安全（CPA-secure）的加密方案。
这里的 $r$ 是一串随机生成的二进制串，并且每次调用都会重新生成。
分组密码 CPA 安全
对于上述 CPA 安全的证明图示（略），核心结论是：
\[Pr[PrivK^{CPA}_{A, \pi} 1^n = 1] = Pr[b=b'] = \frac{1}{2} + negl(n)\]对于上面来说，如果 $b=0$，则说明没猜对，由于此时我们认为 $y=f(r)$ 是完全随机的，也就是做到了一次一密；如果 $b=1$，则说明至少有两次情况下，敌手获得了有迹可循的加密方案，比如至少两次敌手获得了不一样的 $r$。在这种情况下，我们设之前的一次请求 $c=Enc \ r, y \oplus m$，如果出现了 $c^* = Enc \ r, y \oplus m^*$，即两次 $r$ 一样，那么我们可以由异或运算规则：
\[\begin{cases} f(r) \oplus m = c \\ f(r) \oplus m^* = c^* \end{cases} \to c \oplus c^* \oplus m = f(r) \oplus m \oplus f(r) \oplus m^* \oplus m = m^*\]我们直接解出了第二条密文。所以此时我们认为 $y=F(r)$ 不安全。
实际应用
分组密码构造方法有两种，分别是 代换-置换网络（SPN） 和 菲斯特尔网络（Feistel）。
- 雪崩效应：明文或者密钥的某一比特发生变化，会导致密文的很多比特发生变化。加密算法要引起雪崩效应，才能说明算法构造完成。
- 分组加密算法例子：DES、AES、SM4。其中 AES 是 SPN 结构的；DES、SM4 是 Feistel 结构的。
工作模式
- 电子密码本（EBC， Electronic Codebook）
- 密文分组链接（CBC， Cipher Block Chaining）
- 密文反馈（CFB， Cipher Feedback）
- 输出反馈（OFB， Output Feedback）
- 计数器（CTR， Counter）
Q: 哪些在解密时不需要加密子算法可逆？ A: CFB, OFB, CTR。这三种模式本质上都是流密码的构造方式。
Q: 四种加密模式哪些可以并行加密或者解密？ A:
| 模式 | 并行加密 | 并行解密 |
|---|---|---|
| ECB | 可以 √ | 可以 √ |
| CBC | 不行 × | 可以 √ |
| CFB | 不行 × | 可以 √ |
| OFB | 不行 × | 不行 × |
| CTR | 可以 √ | 可以 √ |
五、消息验证码与散列函数
本章讨论完整性，即保证消息接收方可以验证收到的消息的确由合法的发送方发送，且中途没有被改变。完整性的实现是通过消息认证码（MAC）。
消息认证码算法包括三步：
- 生成密钥；
- 对消息生成 MAC 标签；
- 验证标签。
消息验证码的安全性实验（选择消息攻击）：先获取一大堆消息和与之对应的 MAC 标签，然后试试看能不能自己生成一个没出现过的消息和与之对应的 MAC 标签，若成功生成，则攻击成功。（这里是存在性伪造，与之对应的还有选择性伪造）
消息认证码的安全性 消息认证码方案 $\Pi = (Gen, Mac, Vrfy)$ 是安全的，如果对所有 PPT 敌手 $A$ \(Pr[Mac\text{-}forge_{A, \Pi}(n) = 1] \le negl(n)\)
消息认证码方案只保证了消息的确是从拥有密钥 $k$ 的一方发送的。控制了通信信道的攻击者仍然可以重放、乱序或删除消息。可以通过时间戳、序列号等方式在一定程度上解决。
CBC-MAC
这是一种基于 CBC 的消息验证码，依赖分组加密。
128-EIA3
基于祖冲之算法（ZUC）的 MAC。 认证算法的初始化阶段根据机密性密钥 IK 以及其他输入参数构造祖冲之算法的种子密钥 $SK$ 以及初始变量 $IV$。128 比特的认证性密钥 IK 直接用作种子密钥 $SK$。
六、散列函数 (Hash Functions)
散列函数是一种单向函数，最重要的特性是 $y=f(x)$ 是定长度的。
HASH 函数性质：
- 单向性 (One-way / Pre-image resistance)：
- 把猪肉做成香肠很容易，但把香肠还原成猪肉是不可能的。
- 任意给定 $y$，很难找到 $x$ 使得 $y = H(x)$。即给出 Hash 值，要求输入在计算上是不可行的。
- 抗弱碰撞性 (Second pre-image resistance)：
- 如果你有一张指纹，很难找到另一个人的指纹和它一模一样。
- 给定消息 $M$ 和其 Hash 值 $H(M)$，很难找到另一个 $M’ \ne M$，使得 $H(M’) = H(M)$。
- 这条性质可用于防止伪造。
- 抗强碰撞性 (Collision resistance)：
- 很难随便在大街上抓两个人，发现他们的指纹是一样的。
- 很难找到任意一对 $(M, M’)$，使得它们的 Hash 值相同。
- 这条性质保证了对生日攻击的防御能力。
生日攻击
本质是强碰撞。 “生日攻击”问题： 多少个人的生日会出现重合的概率会大于 0.5？
- $Q(365, k)$ 表示 $k$ 个人中没有出现相同生日的概率
- $P(365, k)$ 表示 $k$ 个人中出现相同生日的概率 \(Q(365, k) = \frac{365 \times (365-1) \times \dots \times (365-k+1)}{365^k} = \frac{365!}{(365-k)! 365^k}\) \(P(365, k) = 1 - Q(365, k)\)
- $P(365, k) \approx 0.5$ 时，$k$ 等于多少？（答案约为 23）
Merkle-Damgård 结构
首先，要明白 M-D 结构是为了解决什么问题。现实需求是我们要 Hash 的消息（Message）长度是无限的、不固定的。可能是只有两个字，也可能是一部 10GB 的高清电影。我们在密码学底层，只有一个压缩函数（Compression Function，记作 $f$）。这个函数一次只能处理固定长度的数据。
想象你经营着一家“哈希面包厂”。你的目标是把客户送来的一列超长火车（代表消息 $m$），浓缩成唯一的一块饼干（Hash 值）。你的核心设备只有一台揉面机（压缩函数 $f$）。这台机器每次操作必须放入两样东西：
- 一团旧面团（上一轮的结果）。
- 一箱新原料（消息的一个片段）。 机器轰隆一声，会把这两样东西死死地揉在一起，变成一团新面团。
第一步：切分与填充（Padding & Blocking） 火车太长了，机器吃不下。
- 切分：你拿着大刀，把火车切成一节一节等长的车厢（比如每节 512 bit）。我们将这些车厢称为 $m_1, m_2, \dots, m_n$。
- 填充：切到最后一节，发现货物不满怎么办？必须用泡沫（无意义数据，通常由 1 和 0 组成）把它填满。
- 防伪标签：这点最关键！在最后一节的末尾，你塞了一张纸条，写着“这列火车原本的总长度是多少”。这是为了防止敌人搞破坏（长度扩展攻击），是 M-D 结构安全性的灵魂。
第二步：启动机器（IV - Initialization Vector） 第一节车厢来了，但揉面机需要“旧面团”才能启动，可现在是第一轮，哪来的旧面团？于是，作为厂长，你拿出了祖传的“老面引子”。在密码学里，这叫 IV（初始向量）。它是固定的、公开的常数。
第三步：链式加工（Chaining）
- $H_0 = IV$
- $H_i = f(H_{i-1}, m_i)$
- …
第四步：出炉（Output） 当最后一节车厢被扔进去，并和之前的面团混合处理完后，机器吐出的最终面团，就是我们要的 Hash 值。
M-D 结构最牛的地方在于有一个数学证明：如果压缩函数 $f$ 是抗碰撞的，那么整个 M-D 结构造出来的长 Hash 函数也是抗碰撞的。这意味着我们不需要去设计复杂的长消息处理机制，只需要专心把那个小的压缩函数设计得无懈可击就行了。
安全的 HASH 算法
- SHA-1 算法：美国；摘要长度 160 bit（注：OCR识别为256bit有误，SHA-1通常是160bit，SHA-256才是256bit）。
- SM3：中国；基于 MD 结构。摘要长度 256 bit。
利用杂凑函数构造 MAC
杂凑函数实际上是翻译遗留问题，英文为 Hash Function，所以叫它散列函数、哈希函数、杂凑函数都可以。 在这里定义一种数学符号，若字符串 $M_1 = ‘ab’, M_2 = ‘cd’$，则 $M_1 || M_2 = ‘abcd’$，即连接两个字符串。
大概有三种构造方式，其中 $k$ 是密钥，或者说是 IV：
-
朴素构造方式：$MAC(k, m) = hash_k(k m)$。注：这种方式容易受到长度扩展攻击。* - NMAC 的方式：$NMAC(k, m) = hash_{k_2}(hash_{k_1}(m))$。
-
HMAC 的方式：$HMAC(k, m) = hash( (k \oplus o) \ \ hash( (k \oplus i) \ \ M ) )$
选择密文攻击安全的加密方案
MAC 算法的另一个伟大用途是抵抗选择密文攻击（CCA）。通俗来说，先找一个能抵抗选择明文攻击（CPA）的加密方案，然后对这个方案进行略微修改，即在原先的密文后面加一个密文的 MAC 值。 这样攻击者就无法创造密文（为什么攻击者无法创造密文了？因为创造密文的 MAC 值需要用到私钥，攻击者没有私钥），直接把攻击者发送密文的能力废掉，使攻击者的能力降低为选择明文攻击。
若方案是 CCA 安全的，且攻击者无法制造密文，则称此方案为认证加密方案。 认证加密模式有 OCB 和 GCM。
七、数学基础
多项式与字节对应关系
多项式的幂次对应二进制的位置，例如：
\[x^7 + x + 1 \iff 10000011\]多项式相加等于二进制异或：
\[\begin{aligned} & x^6 + x^4 + x^2 + x + 1 + x^7 + x + 1 \\ \iff & 01010111 \oplus 10000011 = 11010100 \\ \iff & x^7 + x^6 + x^4 + x^2 \end{aligned}\]多项式乘法在 $GF(2^8)$ 域上，多项式默认系数模 2：
- $GF(2^8)$ 域上的多项式相乘，对一个不可约多项式 $m(x) = x^8 + x^4 + x^3 + x + 1$ 取余。
扩展欧几里得算法求逆
辗转相除法，又称欧几里得算法，是用来求两个数的最大公约数（greatest common divisor, gcd）的经典算法。扩展的欧几里得算法将每个余数都表示成开始两个数的线性组合。
\[\begin{cases} R_i = S_i \times R_0 + T_i \times R_1 \\ R_{i-1} = R_i \times Q_i + R_{i+1} \\ S_{i+1} = S_{i-1} - Q_i \times S_i \\ T_{i+1} = T_{i-1} - Q_i \times T_i \end{cases}\]其中，$R_0, R_1$ 即为两个数。
欧拉函数
欧拉函数 $\phi(n)$ 表示小于 $n$ 且与 $n$ 互素的正整数个数。规定 $\phi(1) = 1$。
- 对于任意一个素数 $p$，$\phi(p) = p - 1$。
- 假定 $p, q$ 是两个不同的素数，$n = pq$，则有： \(\phi(n) = \phi(pq) = \phi(p)\phi(q) = (p-1)(q-1)\)
中国剩余定理 (CRT)
假定 $m_1, \dots, m_r$ 为两两互素的正整数，又假定 $a_1, \dots, a_r$ 为整数，那么同余方程组 $X \equiv a_i \pmod{m_i}, (1 \le i \le r)$ 有模 $M = m_1 \times m_2 \times \dots \times m_r$ 的唯一解： \(X \equiv \sum_{i=1}^r a_i M_i y_i \pmod M\) 其中，$M_i = M/m_i$，且 $y_i = M_i^{-1} \pmod{m_i}, 1 \le i \le r$。
解题的标准步骤：
- 先求大模数 $M = m_1 \times m_2 \times \dots \times m_k$
- 算基础分量，对第 $i$ 个方程，算出除去它自己模数以外的所有模数之积：$M_i = M/m_i$
- 算逆元，使用扩展欧几里得算法，求 $y_i$：$M_i \times y_i \equiv 1 \pmod{m_i}$ 即求 $y_i \equiv M_i^{-1} \pmod{m_i}$
- 最后加权求和就是 $x$ 的结果：$x = \sum a_i \times M_i \times y_i \pmod M$
八、公钥密码学
在公钥密码学中 EAV 和 CPA 的强度是一样的，因为公钥是公开的。
RSA 密码体制
RSA 密码体制描述如下：
RSA 密码体制 设 $n = p*q$，其中 $p$ 和 $q$ 为素数。设 $\mathcal{M} = \mathcal{C} = \mathbb{Z}_n$，密钥空间 $\mathcal{K} = {(n, p, q, e, d) : ed \equiv 1 \pmod{\phi(n)}}$。定义：
- 加密：$Enc_K(x) = x^e \pmod n$
- 解密：$Dec_K(y) = y^d \pmod n$
- 公钥：$n, e$；私钥：$p, q, d$。
RSA 参数生成算法
- 生成两个大素数，$p$ 和 $q$，$p \ne q$（使用蒙特卡洛算法生成，如 Miller-Rabin）。
- $n \leftarrow pq$，且 $\phi(n) \leftarrow (p-1)(q-1)$。
- 选择一个随机数 $e (1 < e < \phi(n))$，使得 $gcd(e, \phi(n)) = 1$。
- $d \leftarrow e^{-1} \pmod{\phi(n)}$（利用扩展欧几里得算法）。
- 公钥为 $(n, e)$；私钥为 $(p, q, d)$。
加解密过程要在多项式时间内解出需要用到快速幂算法或者平方-乘算法。
蒙特卡洛算法和拉斯维加斯算法
- 蒙特卡洛算法：一定能得到解，但解不一定正确。
- 拉斯维加斯算法：不一定能得到解，但得到的解一定正确。
- 偏是的蒙特卡洛算法：当回答是的时候：解一定正确；当回答否的时候：解不一定正确。
- Miller-Rabin 算法：对于合数是一种偏是的蒙特卡洛算法。因为当 Miller-Rabin 回答一个数是合数的时候，那说明它就找到了那个数的一个因子，所以这个数就一定是合数。但是 Miller-Rabin 对于素数来说是一种偏否的蒙特卡洛算法。
RSA 攻击
- 选择密文攻击
- 低加密指数攻击：如果 $e$ 太小（如 $e=3$），且发送相同的消息 $m$ 给多个接收者（不同的 $n$），攻击者可以通过中国剩余定理求解出 $m^e$，然后直接开方得到 $m$。
- 公共模数攻击：如果两个用户使用相同的 $n$ 但不同的 $e_1, e_2$，且 $gcd(e_1, e_2)=1$，攻击者截获两个密文后，可以通过扩展欧几里得算法找到 $r, s$ 使得 $re_1 + se_2 = 1$，从而计算 $c_1^r c_2^s \equiv m \pmod n$。
Rabin 密码体系
设 $n = p, q$，其中 $p$ 和 $q$ 为素数，且 $p, q \equiv 3 \pmod 4$。设 $\mathcal{P} = \mathcal{C} = \mathbb{Z}_n^*$。
- 加密：$e_k(x) = x^2 \pmod n$
- 解密：$d_k(y) = \sqrt{y} \pmod n$
- $n$ 为公钥，$p$ 和 $q$ 为私钥。
Rabin 解密能得到多个结果（4个）。显然，除非明文中包含足够的冗余信息，否则解密方不能区分这四个可能的明文中哪一个是正确的。
Q: 为什么非对称加密算法比对称加密算法慢？ A: 这是因为对称加密主要的运算是位运算，速度非常快，如果使用硬件计算，速度会更快。但是非对称加密计算一般都比较复杂，比如 RSA，它里面涉及到大数乘法、大数模等等运算。
Diffie-Hellman
Diffie-Hellman 解决的问题是：两个从未见过面的人，如何在所有人都监听的互联网上，协商出一个只有他俩知道的“秘密密码”？
颜色混合比喻：
- 公开初始颜色：大家都同意使用黄色作为底色。（Eve 听到了，记下了黄色）。
- 各自选私密颜色：
- Alice 偷偷选了红色（这是她的私钥）。
- Bob 偷偷选了蓝色（这是他的私钥）。
- 混合并交换：
- Alice 把（黄+红）混合，变成了橙色，大喊着发给 Bob。（Eve 听到了，记下了橙色）。
- Bob 把（黄+蓝）混合，变成了绿色，大喊着发给 Alice。（Eve 听到了，记下了绿色）。
- 最后的魔法：
- Alice 收到 Bob 的绿色，往里面加入自己的私密红色。结果 = 黄 + 蓝 + 红 = 棕色。
- Bob 收到 Alice 的橙色，往里面加入自己的私密蓝色。结果 = 黄 + 红 + 蓝 = 棕色。
- 结局：Alice 和 Bob 手里都得到了棕色。这就是他们协商出的“共享密钥”。
- 偷听者 Eve 怎么样了？ Eve 手里有：黄色、橙色、绿色。但这没用！因为她没有红色或蓝色，她没办法只把这三种拼在一起弄出棕色。
Diffie-Hellman 问题
- 离散对数问题 (Discrete Logarithm, DLP)：已知一个乘法群 $(G, \cdot)$，一个 $n$ 阶元素 $\alpha \in G$ 和元素 $\beta \in G$，计算 $s = \log_\alpha \beta$。
- 计算 Diffie-Hellman 问题 (CDH, Computational Diffie-Hellman)：已知一个乘法群 $(G, \cdot)$，一个 $n$ 阶元素 $g \in G$ 和两个元素 $g^x, g^y \in G$（这里 $x, y$ 均未知），计算 $g^{xy} \in G$。
- 判定 Diffie-Hellman 问题 (DDH, Decisional Diffie-Hellman)：已知一个乘法群 $(G, \cdot)$，一个 $n$ 阶元素 $g \in G$ 和元素 $g^x, g^y, g^z \in G$（这里 $x, y, z$ 均未知），判定 $g^{xy} = g^z$ 是否成立。
- 我们说 DDH 问题是困难的，如果对任意概率多项式时间的算法 $D$，有
ElGamal 体制的解密等价于求解 CDH 问题。
ElGamal 密码体制
- 经典 ElGamal：基于 DLP（离散对数问题）。
- ECC-ElGamal：基于 ECDLP（椭圆曲线离散对数问题）。
- ECDLP 比 DLP 难得多。所以 ECC 可以用更短的密钥（比如 256 位）达到和 RSA（3072 位）一样的安全强度。
$\mathbb{Z}_p^*$ 上的 ElGamal 密码体制
设 $p$ 是一个素数，使得求解离散对数问题是困难的。令 $\alpha$ 是一个阶为 $q$ 的元素，$q$ 的最大素因子足够大。令
\[\mathcal{P} = \mathbb{Z}_p^*, \mathcal{C} = \mathbb{Z}_p^* \times \mathbb{Z}_p^*\]定义
\[\mathcal{K} = \{(p, \alpha, s, \beta) : \beta \equiv \alpha^s \pmod p\}\]则 $p, \alpha, \beta$ 是公钥，$s$ 是私钥。
-
对 $K = (p, \alpha, s, \beta)$，以及一个（秘密）随机数 $k \in \mathbb{Z}_{p-1}$，定义
\[e_K(x, k) = (y_1, y_2) = (\alpha^k \pmod p, x\beta^k \pmod p)\] -
对于 $y_1, y_2 \in \mathbb{Z}_p^*$，定义
\[d_K(y_1, y_2) = y_2(y_1^s)^{-1} \pmod p\]
ECC-ElGamal 密码体制
选择一个大素数 $p$ 和两个参数 $a, b$，定义椭圆曲线方程： \(E: y^2 \equiv x^3 + ax + b \pmod p\) 其中，必须满足 $4a^3 + 27b^2 \not\equiv 0 \pmod p$。选择曲线上的一点 $G$ 作为基点，公开参数 $(E, p, G)$。
- 私钥：随机的一个整数 $d (1 < d < N)$。
- 公钥：$Q = dG$。
- 加密：明文被编码为曲线上的点 $M$，选取一个随机整数 $k$，计算 $C_1 = kG$, $C_2 = M + kQ$，密文输出 $(C_1, C_2)$。
- 解密：计算 $S = dC_1$，明文为 $M = C_2 - S$。
椭圆曲线中的加法计算： 先定义一个点 $O$，说这个点是无穷远点，定义 $P + O = O + P = P$。如果存在点 $P(x_1, y_1), Q(x_2, y_2)$，求 $R = P + Q, Q(x_3, y_3)$。
- 当 $x_1 \ne x_2$： \(\lambda = \frac{y_2 - y_1}{x_2 - x_1} \pmod p\) \(x_3 = \lambda^2 - x_1 - x_2\) \(y_3 = \lambda(x_1 - x_3) - y_1\)
- 当 $x_1 = x_2, y_1 = -y_2$： \(NULL\) (即结果为无穷远点 $O$)
- 当 $x_1 = x_2, y_1 = y_2$ (即点倍乘)： \(\lambda = \frac{3x_1^2 + a}{2y} \pmod p\) \(x_3 = \lambda^2 - 2x_1\) \(y_3 = \lambda(x_1 - x_3) - y_1\)
注意：椭圆空间上，除法是求逆元。比如 $\frac{13}{14} \pmod{11}$ 即 $13 \times 14^{-1} \pmod{11}$。
九、数字签名与数字整数
数字签名算法包括三个子算法：
- 生成密钥 (KeyGen)
- 签名 (Sig)
- 验证 (Ver)
攻击类型：
- 唯密钥攻击
- 已知消息攻击：攻击者拥有一些消息的签名。
- 选择消息攻击：攻击者可以自由选择一些消息的签名。
攻击目标：
- 选择性伪造：可以创造出任何消息的签名。
- 存在性伪造：可以伪造出一个消息的签名，但是这个伪造出来的签名可能没什么用。
能够抵抗选择消息攻击的定义 (EUF-CMA)： 攻击者可以自由选择一些消息的签名，但是无法伪造出没有查询过的消息的签名。 数字签名是为了保证不可抵赖性，所以数字签名算法都是用发送者的私钥进行签名，由接收方用公钥进行验证，这点与公钥加密正好相反。
各种签名方案
1. RSA 签名
- KeyGen: $K = {(n, p, q, a, b) : n=pq, p, q \text{是素数}, ab \equiv 1 \pmod{\phi(n)}}$，公钥 $(n, b)$，私钥 $(p, q, a)$。
-
Sig: 对于消息 $x$，用私钥计算 $x$ 的签名
\[y = Sig_K(x) = x^a \pmod n\] -
Vrfy: 给定消息 $x$ 和签名 $y$，用公钥验证
\[Vrfy_K(x, y) = 1 \iff x = y^b \pmod n\]
伪造签名：
- 选择 $y \leftarrow \mathbb{Z}_n$ 并计算 $x = y^b \pmod n$，则 $y$ 是 $x$ 的有效签名。（存在性伪造）
- 已知合法消息签名对 $(x_1, y_1), (x_2, y_2)$，可以构造消息 $x_1 x_2$ 的签名为 $y_1 y_2$。（乘法同态性质）
2. ElGamal 签名方案
- KeyGen: 设 $\alpha \in \mathbb{Z}_p^*$ 是一个生成元。$p, \alpha, \beta$ 是公钥，$s$ 是私钥。$\beta \equiv \alpha^s \pmod p$。
- Sig: 对于消息 $x$，选择一个秘密随机数 $k \in \mathbb{Z}_{p-1}^*$，计算 \(\gamma = \alpha^k \pmod p, \quad \delta = (H(x) - s\gamma)k^{-1} \pmod{p-1}\) 定义签名为 $(\gamma, \delta)$。
- Vrfy: 对于给定签名 $(\gamma, \delta)$ 和消息 $x$，验证 \(\beta^\gamma \gamma^\delta \equiv \alpha^{H(x)} \pmod p\)
注意：随机数 $k$ 不能暴露，也不能重复使用，否则会泄露私钥。
3. 数字签名算法 (DSA)
-
Sig: 对于消息 $x$，和秘密随机数 $k$，
\[\gamma = (\alpha^k \pmod p) \pmod q\] \[\delta = (SHA\text{-}1(x) + s\gamma)k^{-1} \pmod q\] -
Vrfy:
\[e_1 = SHA\text{-}1(x)\delta^{-1} \pmod q\] \[e_2 = \gamma\delta^{-1} \pmod q\] \[Vrfy = 1 \iff (\alpha^{e_1} \beta^{e_2} \pmod p) \pmod q = \gamma\]
4. Schnorr 签名算法
- KeyGen: $p, q, \alpha, \beta$ 是公钥，$s$ 是私钥。$\beta \equiv \alpha^s \pmod p$。
-
Sig: 对于消息 $x$，和秘密随机数 $k \in \mathbb{Z}_q^*$，
\[\gamma = H(x || \alpha^k \pmod p)\] \[\delta = k + s\gamma \pmod q\] -
Vrfy:
\[H(x || \alpha^\delta \beta^{-\gamma} \pmod p) = \gamma\]
5. 椭圆曲线数字签名算法 (ECDSA)
-
Sig:
\[kG = (u, v)\] \[\gamma = u \pmod q\] \[\delta = (SHA\text{-}1(x) + s\gamma)k^{-1} \pmod q\] -
Vrfy:
\[w = \delta^{-1} \pmod q\] \[i = w \cdot SHA\text{-}1(x) \pmod q\] \[j = w\gamma \pmod q\] \[(u, v) = iG + jQ\] \[Vrfy = 1 \iff u \pmod q = \gamma\]
数字证书将一个人的公钥与一个人的身份信息绑定在了一起。
- 数字证书管理：证书注册；证书更新；证书存放；证书撤销；证书验证；证书状态查询。
- 数字证书的安全性：
- 任何拥有权威机构（CA）公钥的人都可以验证数字证书的有效性。
- 除了权威机构（CA）外，任何人都不能够伪造数字证书。
- 因此，数字证书的安全性依赖于权威机构（CA）私钥的保密性。
数字证书应用： 现有持证人甲向持证人乙传送数字信息。为了保证信息传送的机密性、完整性和不可否认性，需要对要传送的信息进行数字加密和数字签名。
- 乙收到甲传送过来的密文和加密的 AES 密钥，先用自己的私钥（SK）对加密的 AES 密钥进行解密，得到 AES 密钥。
- 乙然后用 AES 密钥对密文进行解密，得到明文的数字信息。
- 乙获得甲的证书，并用 CA 证书验证及检查证书撤销列表验证甲证书是否有效、过没过期、是否符合用途。
- 乙用甲的公钥（PK）（来自证书）对甲的数字签名进行解密，得到信息摘要。
- 乙用相同的 hash 算法对收到的明文再进行一次 hash 运算，得到一个新的信息摘要。
- 乙将收到的信息摘要和新产生的信息摘要进行比较，如果两个结果一致，说明收到的信息没有被修改过。
十、实体认证协议
本章需要学会判断协议是否安全。 如何定义协议的安全性： 如果一个敌手可以攻破此协议，那么这个敌手就可以攻破此协议中的算法。但是因为之前已经证明过算法安全，故敌手不可以攻破此协议，即协议安全。
理解“挑战-应答”的本质：
- 为什么要由 r (随机数)？ 防重放。
- 为什么要由 ID？ 防反射/中间人。
- 为什么最后要加密/签名？ 证明我知道私钥/密钥。
基本假设：可信权威机构 TA 向其他实体颁发证书；任何知道 TA 的验证密钥 $ver_{TA}$ 的用户都可以验证其他用户的证书。
十一、密钥分配与密钥协商
- 密钥分配：
- Diffie-Hellman KPS
- Needham-Schroeder
- Kerberos (基于 KDC)
- Bellare-Rogaway
- 密钥协商：
- Diffie-Hellman KAS
- MTI/A0 KAS
- TLS 协议
- HTTP 协议
- 群组密钥分配/协商：
- 逻辑密钥树 (Stateful)
- Steiner 树 (Stateless)
- GDH 及其变形
- BD 及其变形
长期密钥 (Long Lived Key)：指预先计算并安全存储的密钥。或者说，长期密钥可以根据需要由安全存储的秘密信息非交互地计算出来。 会话密钥：会话密钥指在特定的会话中，一对用户经常使用的秘密的短期会话密钥，当会话结束时就会把该会话密钥丢弃。
身份标识防止反射攻击，随机数防止重放攻击。
十二、杂项（高级协议）
1. 基于身份的密码 (IBE)与双线性对
双线性对 (Pairing)：设 $G_1$ 和 $G_2$ 是两个乘法群，$\hat{e}: G_1 \times G_1 \to G_2$ 称为一个可计算的双线性配对，满足：
- 双线性：$\hat{e}(g^a, h^b) = \hat{e}(g, h)^{ab}$
- 非退化：$\hat{e}(g, g) \ne 1_{G_2}$
配对上的密码学难题假设：
- BDH (Bilinear Diffie-Hellman): 已知 $aP, bP, cP \in G_1$，求 $\hat{e}(P, P)^{abc} \in G_2$。
- DBDH (Decisional BDH): 判定 $\hat{e}(P, P)^{abc}$。
第一板块：证明“你是你”，但别泄密 —— 认证与零知识
- 实体认证 (第十章)
- 核心逻辑：挑战-应答 (Challenge-Response)。
- 我给你一个随机数 $r$（挑战）。
- 你用私钥对 $r$ 签名或加密发回来（应答）。
- 我看对不对。
- 考点（必背）：
- 重放攻击：为什么要有随机数（Nonce）或时间戳？是为了防止坏人录下昨天的消息今天重发。
- 并行会话攻击：A 发给 B 挑战，C 截获并发回给 A，诱导 A 自己解开。防御方法是加入 ID 绑定。
- Schnorr 身份识别：（重点算法）记住 $x = g^r, y = r + se$ 这个结构。
- 核心逻辑：挑战-应答 (Challenge-Response)。
- 零知识证明 ZKP (第十四章-4)
- 一句话解释：我要向你证明我知道秘密 $x$，但绝对不告诉你 $x$ 是多少。
- 三个性质 (死记硬背)：
- 完备性 (Completeness)：真的假不了（真的能通过验证）。
- 可靠性 (Soundness)：假的真不了（不知道秘密的人骗不过去）。
- 零知识性 (Zero-Knowledge)：验证者除了“他是真的”以外，学不到任何关于秘密的信息。
- 具体协议：
- Fiat-Shamir (基于二次剩余，扔硬币模型)。
- Schnorr 协议 (基于离散对数，还是那个 $y = r + se$)。
- 注：Schnorr 既可以用作身份认证，也可以看作零知识证明，它俩本质是一个东西。
第二板块：更灵活的加密 —— 谁能解密？
- 基于身份加密 (IBE)
- 解决痛点：传统公钥需要证书（CA），太麻烦。
- 核心：用你的邮箱/手机号直接当公钥。
- 考点：
- 双线性配对 (Pairing)：这是实现 IBE 的数学工具。不用深究数学细节，但要知道 $\hat{e}(aP, bQ) = \hat{e}(P, Q)^{ab}$ 这个性质。
- PKG (私钥生成中心)：有个中心服务器掌握主密钥，给你发私钥。缺点是密钥托管问题（PKG 知道所有人的私钥）。
- 基于属性加密 (ABE)
- 解决痛点：我要把文件发给“所有计算机系的老师”，而不是具体的某个人。
- 两大分类 (高频考点，必考区别)：
- KP-ABE (密钥策略)：锁在密文里，钥匙上有规则。密文标记属性（如“学生”），你的私钥里写着规则（“学生” OR “老师”）。
- CP-ABE (密文策略)：规则在密文里，钥匙上有属性。密文写着“（计算机系 AND 老师）能开”，你的私钥代表你的属性（“计算机系”、“老师”）。这个更常用，像门禁系统。
- 可搜索加密 (Searchable Encryption)
- 解决痛点：数据加密上传到云盘后，怎么搜索关键词（比如搜 “Salary”）？总不能把数据全下载下来解密再搜吧？
- 核心：带关键词的陷门 (Trapdoor)。
第三板块：搞点“不可思议”的操作 —— 协议原语
- 比特承诺 (Bit Commitment)
- 场景：“密封信封”。我想预测股市，写在纸上封进信封给你。一个月后打开验证。
- 两个性质 (死记硬背)：
- 隐藏性 (Hiding)：我不给钥匙，你看不见信封里写的啥。
- 绑定性 (Binding)：信封在你手里，我想赖账改里面的字也不行。
- Pedersen 承诺：基于离散对数，记得它有加法同态性。
- 不经意传输 (OT - Oblivious Transfer)
- 场景：“不管部长的秘密”。我有 10 个秘密，你有钱买 1 个。你挑第 3 个拿走，但我不知道你买走了哪一个，你也不知道其他 9 个是什么。
- 地位：它是安全多方计算的基石。
- 安全多方计算 (MPC)
- 场景：“姚氏百万富翁问题”。两个富翁想比谁钱多，但都不想说自己具体有多少钱。
- 核心：在不泄露各自隐私输入的前提下，共同计算一个函数 $f(x, y)$。
- 秘密共享 (Secret Sharing)
- 场景：“集齐七颗龙珠”。把核武器发射密码拆成 $n$ 份，必须凑齐 $t$ 个人才能恢复密码。
第四板块：现实世界的标准 —— 别光吹牛，怎么用？
模型进化史： BR 模型 -> CK 模型 -> eCK 模型（越来越强，考虑了更多泄密情况）。
工业标准：
- TLS：上网用的（HTTPS）。握手协议是核心。
- ISO 9798：通用的认证框架。
- 3GPP (3G/4G/5G)：手机入网认证。
- AKA 协议：用到了 SIM 卡里的共享密钥。