CS3314 密码学课程内容
第二讲：古典密码学基础（Basics of Cryptography）
一、密码学总体框架
密码学的组成
- Cryptography（密码编码）：设计加密与保护信息的技术
- Cryptanalysis（密码分析）：破译密码的技术
- Cryptology（密码学） = Cryptography + Cryptanalysis
密码系统五元组
一个密码系统由五个集合组成
(P, C, K, E, D)
- P：明文空间 (Plaintext)
- C：密文空间 (Ciphertext)
- K：密钥空间 (Key)
- E：加密算法 (Encryption)
- D：解密算法 (Decryption)
满足：
D(E(M, K₁), K₂) = M
二、两大密码体制
| 体制 | 密钥关系 | 特点 | 示例 |
|---|---|---|---|
| 单钥体制（对称密码） | K₁ = K₂ | 加密与解密使用相同密钥，速度快，密钥分配困难 | AES, DES |
| 双钥体制（非对称密码） | K₁ ≠ K₂ | 加密与解密密钥不同，可公开公钥 | RSA, ECC |
⚠️ Kerckhoffs 原理：
密码系统的安全性应仅依赖密钥的保密，而不是算法的保密。
三、密码分析与攻击模型
| 攻击类型 | 攻击者已知信息 | 特点 |
|---|---|---|
| 唯密文攻击 (Ciphertext-only) | 仅密文 | 难度最高 |
| 已知明文攻击 (Known-plaintext) | 若干明文-密文对 | 常见于对称密码 |
| 选择明文攻击 (Chosen-plaintext) | 可选择加密输入 | 典型攻击RSA等 |
| 选择密文攻击 (Chosen-ciphertext) | 可选择解密密文 | 针对公钥体系 |
能力层级：唯密文 < 已知明文 < 选择明文 < 选择密文
四、信息论与安全性基础
香农的贡献
- 提出了扩散性（Diffusion）与混淆性（Confusion）原则
- 建立了密码学的数学基础
- 证明了一次一密 (One-Time Pad) 是完善保密（Perfect Secrecy）的
安全分类
| 类型 | 定义 | 特点 |
|---|---|---|
| 无条件安全 / 完善保密 (Unconditional Security) | 无论计算资源多少都无法破解 | 如一次一密 OTP |
| 计算安全 (Computational Security) | 破解成本或时间过大 | 如AES, RSA |
条件：若 I(M; C) = 0 → 完善保密
必要条件：H(K) ≥ H(M) → 密钥熵不小于消息熵（相当于密钥空间 ≥ 明文空间）
五、古典密码技术
1️⃣ 代换密码 (Substitution Cipher)
用其他符号替换明文字符
| 类型 | 加密规则 | 特点 / 弱点 |
|---|---|---|
| Caesar 移位密码 | c = (p + k) mod 26 | 密钥空间 25，易穷举 |
| 单表代换 | 任意置换表 | 可频率分析破解 |
| 仿射密码 | E(x)=ax+b (mod 26)，需 gcd(a,26)=1 | 容易被统计攻击 |
| Playfair 密码 | 按双字母加密 | 频率规律削弱但仍可破 |
| Hill 密码 | 向量线性代换 Kp=C | 抵抗密文攻击，不抗明文对攻击 |
| Vigenère 密码 | 多表代换，周期r | 可用 Kasiski 方法破译 |
| 一次一密 (OTP) | cᵢ = mᵢ ⊕ kᵢ | 唯一无条件安全系统，但密钥管理困难 |
2️⃣ 置换密码 (Transposition Cipher)
不改变字符，只改变顺序。
| 类型 | 方法 | 特点 |
|---|---|---|
| 栅栏密码 (Rail Fence) | 对角线写，按行读 | 简单，易破解 |
| 列换位 (Columnar Transposition) | 写矩阵后按密钥列序读取 | 字母频率不变 |
| 乘积密码 (Product Cipher) | 代换 + 置换 组合 | 古典 → 现代桥梁 |
六、机械密码与现代演化
转轮机 (Rotor Machine)
- 基于多表代换，通过物理转子产生不同映射。
- 代表：德国 Enigma、日本 Purple。
- 启示：多层代换 + 动态置换 → Feistel结构 / DES 的前身。
七、隐写术 (Steganography)
- 隐藏信息存在性，不是加密。
- 例：隐形墨水、图像LSB、IoT SmartConfig。
- 缺点：容量小，易检测。
八、核心结论
- 安全性取决于密钥，而非算法。
- 仅有代换或置换都不安全，需结合。
- 密钥空间必须足够大，以防穷举攻击。
- OTP 是唯一无条件安全的系统。
- 现代密码算法的雏形：乘积密码与转轮机。
