密码学复习

常用缩写

缩写	全称	解释	考点提醒
DES	Data Encryption Standard	数据加密标准	56位密钥，64位分组，Feistel结构（现已不安全）。
AES	Advanced Encryption Standard	高级加密标准	128位分组，128/192/256位密钥，SPN结构（目前标准）。
IV	Initialization Vector	初始化向量	保证同样明文加密出不同密文的“随机第一步”。
ECB	Electronic Codebook	电子密码本模式	最简单、不安全。明文块与密文块一对一，泄露模式。
CBC	Cipher Block Chaining	密码分组链接模式	像链条一样，前一密文块影响后一明文块。需填充(Padding)。
CTR	Counter	计数器模式	把块密码变流密码。高性能、可并行，不需要填充。
CPA	Chosen Plaintext Attack	选择明文攻击	安全等级：即便坏人能选明文加密，也猜不出其他密文。
CCA	Chosen Ciphertext Attack	选择密文攻击	更高级安全：坏人能选密文解密（除了目标密文），也猜不出目标。

---

二、 哈希与消息认证 (Hash & MAC)

这一部分关乎数据的完整性（Integrity）和真实性（Authenticity）。

缩写	全称	解释	考点提醒
MAC	Message Authentication Code	消息认证码	核心：带密钥。证明消息没被改过，且确实是发件人发的。
HMAC	Hash-based MAC	基于哈希的MAC	用哈希函数（如SHA256）构造MAC的方法。防范长度扩展攻击。
MD	Merkle-Damgård	MD变换	绝大多数哈希函数（MD5, SHA1/2）的构建结构：填充+迭代。
CR	Collision Resistance	抗碰撞性	找两个不同的 $m_1,m_2$ 使得 $H(m_1)=H(m_2)$ 在计算上不可能。
OWF	One-Way Function	单向函数	给 $y$ 算不出 $x$；但给 $x$ 很容易算出 $y$。哈希的基础。
AE / AEAD	Authenticated Encryption (with Associated Data)	认证加密	加密+MAC的合体。如 GCM 模式，同时保证私密性和不被篡改。

---

三、 数论与公钥密码 (Number Theory & PKE)

公钥密码学（PKE）基于复杂的数学难题。

缩写	全称	解释	考点提醒
PKE	Public Key Encryption	公钥加密	两个密钥：公钥加密，私钥解密。
RSA	Rivest-Shamir-Adleman	RSA算法	基于大整数分解难题。$N=pq$，$e$是公钥，$d$是私钥。
DH	Diffie-Hellman	DH密钥交换	基于离散对数难题(DLP)。让两人在不安全信道协商出相同密钥。
DLP	Discrete Logarithm Problem	离散对数问题	已知 $g^a\mathrm{mod}p$，很难算出 $a$。DH和ElGamal的基础。
CRT	Chinese Remainder Theorem	中国剩余定理	考试常用于加速RSA解密或执行共模/小指数攻击。
ECC	Elliptic Curve Cryptography	椭圆曲线密码	相比RSA，用更短的密钥达到同样的安全性（如256位 vs 3072位）。

---

四、 协议与基础设施 (Protocols & PKI)

缩写	全称	解释	考点提醒
PKI	Public Key Infrastructure	公钥基础设施	管理公钥的一整套体系。
CA	Certificate Authority	证书颁发机构	密码学的“警察局”，负责给公钥签发证书，证明“这个公钥确实是某某的”。
MITM	Man-in-the-Middle	中间人攻击	坏人拦截通信，分别欺骗双方。DH协议最怕这个。
DSS/DSA	Digital Signature Standard/Algorithm	数字签名标准	保证不可否认性。私钥签名，公钥验签。

---

1. 基础与完善保密性

• 密码学基础与历史：Kerckhoffs原则，古典密码及其弱点。
• 完善保密性：One-Time Pad (OTP)，香农定理，信息论安全 vs 计算安全。

2. 对称加密体系 (计算安全)

• 计算安全基础：可忽略函数，PRG (伪随机发生器)，PRF (伪随机函数)。强Church-Turing理论保证安全性。IND-CPA 安全。
• 流密码与分组密码：流密码(RC4/LFSR)，分组密码(DES/AES)，Feistel结构与SP网络。
  • 流密码本质上就是用 PRG 来模拟一次一密。
• 操作模式：ECB, CBC, CTR, OFB, CFB 的安全性与区别。

3. 完整性与认证

• 消息认证码_MAC：MAC定义，CBC-MAC及其安全性缺陷，重放攻击。
• 哈希函数：抗碰撞性，Merkle-Damgård 结构，HMAC，生日攻击。

4. 公钥加密与数论

• 数论基础：群论，RSA假设，离散对数(DL/CDH/DDH)问题。
• 公钥加密_PKE：RSA加密，ElGamal加密，CPA安全，混合加密。

5. 高级安全性 (CCA)

• CCA安全与认证加密：Padding Oracle攻击，加密与认证的结合 (Encrypt-then-MAC)。

---

复习策略：

1. 重点理解 IND-CPA 和 IND-CCA 的安全游戏定义。
2. 能够推导 CBC-MAC 和 哈希长度扩展 的攻击方式。
3. 区分 计算安全 与 完善保密 的本质区别。

考点：

• 安全定义 = 安全目标 + 威胁模型
• DES：Feistel 结构，64位块，56位密钥，16轮。不安全（密钥太短，易受暴力破解）。
• AES：SPN 结构，128位块，128/192/256位密钥。目前标准。

考点

这份由你和同学回忆整理的“考前情报”含金量极高！它几乎把考试范围从“宽泛的课件”缩小到了“具体的考点”。

结合你提供的这些情报和之前上传的课件，我为你重新梳理了一份**《密码学期末绝密押题复习指南》**。这份指南直接针对你提到的考点进行解析，过滤掉了不考的内容（如X.509详细结构、NYK协议等）。

---

0. 核心概念与定义 (必考基础)

情报关键词：目标与防御对应、形式化定义、FOCS/STOC、有状态/无状态、压缩与加密

• 安全定义 (Security Definition)
  • 公式：安全定义 = 安全目标 (Security Goal) + 威胁模型 (Threat Model)。
  • 图示：考试让你“把那个图画出来”，指的是安全参数 (Security Parameter, $n$) 相关的图。通常是指随着 $n$ 增加，敌手成功的概率下降至可忽略 (negligible)，而算法运行时间呈多项式增长。
  • 形式化元素：$n$ (安全参数), $PPT$ (多项式时间敌手), $negl(n)$ (可忽略函数)。
  • 顶级会议：FOCS (IEEE Symposium on Foundations of Computer Science), STOC (ACM Symposium on Theory of Computing)。这是密码学理论最顶级的两个会议，记住名字。
• 状态性 (Statefulness)
  • 有状态 (Stateful)：当前的加密/解密行为依赖于之前的历史或计数器（如 CTR模式 如果不随机生成IV而是用计数器累加，或者 Stream Cipher 的内部状态）。
  • 无状态 (Stateless)：每次加密独立，互不影响（如 ECB，或者随机IV的 CBC）。
• 压缩与加密
  • 结论：先压缩后加密 (Compress-then-Encrypt)。
  • 理由：压缩去除冗余，减少了密文的统计特征，增加了安全性；同时减少了要加密的数据量，提高效率。

---

1. 对称加密 (Symmetric Encryption)

情报关键词：DES/AES长度、Feistel网络、CTR/CBC、Padding Oracle、GCM/CCM/Poly1305

• 算法参数 (死记硬背)
  • DES：
    • 全称：Data Encryption Standard。
    • 密钥长度：56 bits (虽然输入是64位，但每字节第8位是校验位)。
    • 分组长度：64 bits。
  • AES：
    • 全称：Advanced Encryption Standard (Rijndael)。
    • 分组长度：128 bits (固定)。
    • 密钥长度：128 / 192 / 256 bits。
• Feistel 网络 (DES的基础)

  • 考点：写出第 $i$ 轮的迭代公式。

  • 公式： $L_i=R_{i-1}$

    $R_i=L_{i-1}\oplus f(R_{i-1},K_i)$

  • 特点：解密和加密结构相同，轮函数 $f$ 不需要可逆。

• 操作模式 (Modes)
  • CTR (计数器模式)：流密码模式，可并行计算，CPA安全。
  • CBC (密码分组链接)：链式密码。$c_i=En{c}_k(m_i\oplus c_{i-1})$。
  • 对比：
    • CBC：串行（无法并行加密），错误传播（错1个密文块影响2个明文块），需填充 (Padding)。
    • CTR：并行，无错误传播，无需填充。
• Padding Oracle Attack (重难点)
  • 原理：利用服务器对“填充格式错误”和“MAC校验错误”的不同反馈（Oracle）。
  • 攻击手段：修改密文块 $c_{i-1}$ 的字节，使得解密后的 $m_i$ 在去除填充时触发不同错误。
  • 核心操作：通过修改 $c_{i-1}$ 的某一位，试图让解密后的中间值 $P$ 的最后一位变成 0x01 (合法填充)。
  • 为什么能抵御？：如果不先验证MAC，CBC模式本身无法抵御此攻击。必须使用 Encrypt-then-MAC 才能抵御。
• 认证加密 (Authenticated Encryption, AE)
  • 必考题：以下哪个方案能同时提供机密性和认证性？
  • 背诵列表 (PPT那一页)：
    1. GCM (Galois/Counter Mode)：CTR + GMAC。
    2. CCM (Counter with CBC-MAC)。
    3. ChaCha20-Poly1305 (流密码+Poly1305 MAC)。
  • 原理：只有 AE 方案（特别是 Encrypt-then-MAC）能保证CCA安全。

---

2. 哈希与MAC (Hash & MAC)

情报关键词：MD Transform、Merkle树、HMAC构建、压缩/抗碰撞

• 哈希基础
  • 首要功能：压缩 (Compression) (将任意长映射为固定长)。
  • 首要安全目标：抗碰撞 (Collision Resistance)。
  • 输出长度：SHA-256 输出 256 bits。
• 结构与构建
  • Merkle-Damgård Transform (MD变换)：
    • 考点：如何用固定长度的压缩函数 $h$ 构建任意长度的哈希函数 $H$。
    • 过程：填充消息 → 分块 → 迭代压缩 ($z_i=h(z_{i-1}||m_i)$)。
  • HMAC 构建：
    • 公式：$HMAC(k,m)=H((k\oplus opad)||H((k\oplus ipad)||m))$。
    • 核心：两次哈希嵌套，为了防御 长度扩展攻击 (Length Extension Attack)。
  • Merkle Tree：
    • 用途：高效验证大数据集中的某个数据块（区块链基础）。
    • 考点：根哈希 (Root Hash) 的计算，路径验证。
• CBC-MAC
  • 定义：用CBC模式加密，取最后一个密文块作为 Tag。
  • 限制：仅对固定长度消息安全。

---

3. 数论与公钥加密 (Number Theory & PKE)

情报关键词：$Z_N^{\ast }$的阶、RSA证明/攻击、DH协议/中间人、ElGamal

• 数论基础
  • 欧拉函数 $\varphi (N)$：$Z_N^{\ast }$ 中元素的个数。
    • 若 $N=p$ (素数)，$\varphi (N)=p-1$。
    • 若 $N=pq$，$\varphi (N)=(p-1)(q-1)$。
  • 欧拉定理：$a^{\varphi (N)}\equiv 1(\mathrm{mod}N)$。
• RSA 算法
  • 证明 (为什么互素?)：
    • 密钥生成需 $ed\equiv 1(\mathrm{mod}\varphi (N))$。要保证 $d$ 存在，必须 $\gcd (e,\varphi (N))=1$ (即互素)。
    • 加解密正确性依赖于 $m^{ed}\equiv m^{1+k\varphi (N)}\equiv m\cdot (m^{\varphi (N)}{)}^k\equiv m\cdot 1^k\equiv m(\mathrm{mod}N)$。
  • 教科书式 RSA 攻击 (必考)：
    • 问题：什么是教科书式RSA？(无填充，$c=m^e\mathrm{mod}N$)。
    • 小指数攻击 (Small e)：如果 $e=3$ 且同一消息发给3个人，用中国剩余定理 (CRT) 开立方根破解。
    • 已知部分明文：如果不加随机填充，容易验证猜测的明文。
    • 共模攻击：不同用户共享 $N$，若 $e$ 不同，可解密。
• Diffie-Hellman (DH) 协议
  • 流程：$A\to g^a$, $B\to g^b$, 共享 $g^{ab}$。
  • 中间人攻击 (MITM)：
    • 考点：画图展示中间人 $E$ 如何分别与 $A$ 和 $B$ 建立密钥。
    • $A\leftrightarrow E$ (共享 $g^{ae}$), $E\leftrightarrow B$ (共享 $g^{eb}$)。
    • 防御：需要身份认证 (如数字签名)。
• ElGamal 加密
  • 基于 离散对数问题 (DLP)。
  • 加密是随机化的：$(c_1,c_2)=(g^r,m\cdot y^r)$。

---

4. 数字签名与 PKI

情报关键词：私钥签名、Schnorr/DSA (AB卷区分)、CA证书

• 核心原理
  • 唯一性：数字签名用私钥签，因为要保证只能有一个人（持有私钥的人）能签名，具有不可否认性。
  • 公钥基础设施 (PKI)：底层原语是 数字签名。
  • CA (证书授权中心)：
    • 作用：将公钥与身份 ($ID$) 绑定。
    • 证书：$Cert=Sig{n}_{S{K}_{CA}}(ID,P{K}_{User})$。
    • DiDi 案例：身份信息必须加密存储（机密性），明文存储是大忌。
• 具体方案 (重中之重)
  • Schnorr 签名 (A卷概率大)：
    • 生成随机 $k$，计算 $r=g^k$。
    • 计算 $e=H(r||m)$。
    • 计算 $s=k+x\cdot e$。
    • 签名是 $(e,s)$。
  • DSA 签名 (B卷概率大)：
    • 基于 ElGamal 的变种，美国标准。
    • 签名也是两个数 $(r,s)$，但计算过程包含模逆运算。

---

5. 高级应用与计算

情报关键词：秘密共享计算题

• Shamir 秘密共享 (Secret Sharing)

  • 考点：拉格朗日插值法计算。

  • 场景：$(t,n)$ 门限方案。已知 $t$ 个点 $(x_i,y_i)$，恢复多项式 $f(x)$，秘密是 $S=f(0)$。

  • 公式： $f(0)={\sum }_{j=1}^t{y}_j\left({\prod }_{m=1,m\ne j}^t\frac{0-x_m}{x_j-x_m}\right)$

  • 一定要练：给3个点，在模某个素数 $p$ 下算出 $S$。

---

🚀 最终突击策略 (Based on your notes)

1. 背诵 PPT：
   • AE 模式那页：GCM, CCM, Poly1305。
   • Feistel 网络：$L_i,R_i$ 迭代公式。
   • DES/AES 参数：位数，位数，位数。
2. 练习画图：
   • 安全定义图 (概率 vs 安全参数)。
   • DH 中间人攻击图。
   • Merkle-Damgård 结构图。
3. 计算题准备：
   • Lagrange 插值 (秘密共享)。
   • RSA/ElGamal 的简单加解密验证。
4. 区分 A/B 卷重点：
   • 重点看 Schnorr 和 DSA 的签名生成与验证过程，确保无论考哪个都能写出来。