Classical Cryptography
加密Encryption = 加密算法
解密Decryption = 解密算法
Modern cryptography
加密 = 加密算法 + 密钥Secret Key
解密 = 解密算法 + 密钥
对称加密：
同一套密钥负责加密和解密，而且必须满足 解出来的肯定是原来的内容
A and B have the same key. and（D (k,E (k,m))=m）
- 加密：E（密钥，明文）= 密文
- 解密：D（密钥，密文）= 明文
1 Stream Ciphers流密码
One-Time Pad（OTP）一次一密
- c = E(k,m) = k⊕m
- m = D(k,c) = k⊕c
- k = m⊕c
- Secret key isas long asmessages to be encryted
- Each secret key will beused once only
- Choose secretkey randomly
有完美的保密性，但过于理想，每次都用新的，且要与信息等长消耗太大，无法现实使用。
Pr[E(k,m0)=c] = Pr[E(k,m1)=c]即k在密钥空间中均匀分布，无法从密文中得到明文的信息
异或XOR的重要性质
一个随机变量XOR一个独立均匀变量= 一个均匀变量
PRG伪随机生成器（解决密钥太长）
replace "random" key by "pseudorandom" key
PRGmust beunpredictable不可预测
把短密钥 “拉长”，代替 OTP 里的长钥匙，需要不可预测（知道前面的几位，不能猜出后面的）
不是完美安全的
Stream Ciphers 流密码(由PRG创造)
用 PRG 生成的乱码，和明文做拼图匹配
E(k,m)=m⊕G(k) 加密 = 明文⊕由密钥生成的伪随机序列
D(k,c)=c⊕G(k) 解密 = 密文⊕由密钥生成的伪随机序列
缺点
- 同一密钥不能用两次
- 没有 “防篡改” 功能（不能用于磁盘加密--很容易定位哪里修改了）
重复使用OTP或流密码是不安全的，两次的结果异或，可以得到两条明文的异或结果
PRG安全
希望输出的伪随机与真随机是不可区分的
statistical test统计测试
A是一个关于{0，1}^n的统计测试区分器，输出1表示是认为是PRG的输出；输出0表示认为是真随机数
Pr是概率，G伪随机数生成器
优势（Advantage）：AdvPRG[A, G] = | Pr[A(G(k))=1] - Pr[A(U)=1] |属于[0,1]
核心公式本质上都是 “攻击者通过统计测试区分 PRG 输出与真随机串的概率差的绝对值”
优势接近1-->A能区分G和随机数
优势接近0-->A无法区分G和随机数
题：
- A(x) = LSB(x), Pr[LSB(G(k)=0)]=1/2 ①
- (A,G') = LSB(G'(k1,k2)) = LSB(G(k1)^G(k2)) = LSB(G(k1))^LSB(G(k2))
- ^is AND function-->only just when LSB(G(k1))=0 and LSB(G(k2))=0, LSB(G(k1))^LSB(G(k2))=0 ②
- because of①②-->Pr(LSB(G(k1))^LSB(G(k2))=0)=1/2*1/2 = 1/4
- Adv_PRG[A,G'] = |Pr[A(G')=0]-Pr[A(U)]=0| = |1/4-1/2| = 1/4
Semantic security语义安全
密文不泄露任何关于明文的 “有用信息”
对于任意两个明文m_1, m_2（长度相同），以及任意攻击者A，若A无法区分 “m_1加密后的密文c_1” 和 “m_2加密后的密文c_2”，则方案满足语义安全。
攻击测试：
Adv（adversary）攻击者给挑战者发送两条明文m0和m1，
Chal.挑战者随机选一条消息（m0或m1）加密得到密文c，并将c给Adv
优势计算：两条明文加密后结果的概率相减，看Adv是否能判断出是哪条明文被加密了
不能每次加密用的k都是一样的
不能直接把k接在m后面加密
Negligible and non-negligible可忽略和不可忽略
密码学里，只要攻击成功的概率是 “可忽略” 的，就认为这个加密方法是安全的
2 Block ciphers分组加密
将固定长度的明文块加密为相同长度的密文块的对称加密算法。
- 对称性：加密和解密使用同一个密钥k。
- 固定分组长度：如 AES 的分组长度为 128 位（16 字节）。
- 确定性：对于相同的明文块和密钥，输出的密文块总是相同的（除非结合工作模式引入随机性）。
例子：
3DES：n = 64bits,k = 168bits
AES:n = 128bits,k = 128,192,256bits
迭代构建分组加密
密钥k作为输入，k被扩展为子ki（round轮密钥），
R(k,m)轮函数接收轮密钥和消息m的当前状态，结果输出到下一轮，经过n轮后输出密文c。
PRFs伪随机函数（Pseudorandom Function）
密钥和输入一起 映射到一个输出空间
F:{0,1}^κ×{0,1}^n→{0,1}^m
其中：
- κ：密钥长度；
- n：输入长度；
- m：输出长度（通常 m=n 或固定值）；
- 对每个密钥 k，Fk(⋅)=F(k,⋅) 是一个从 n 位到 m 位的确定性函数。
对于不知道密钥 k 的攻击者来说，访问 Fk(⋅) 就像在访问一个真正随机的函数（即每次输入不同，输出看起来完全随机且不可预测）。
PRF安全
如果对所有概率多项式时间（PPT）攻击者 A，该优势都是可忽略函数（negligible），则称 F 是一个安全的 PRF。
特点
- 不要求是双射（即不要求一一对应）；
- 多个不同输入可能映射到相同输出（允许碰撞）；
- 常用于 MAC（如 HMAC）、密钥派生（KDF）、流密码构造等。
PRPs伪随机置换（Pseudorandom Permutation）
E:{0,1}^κ×{0,1}^n→{0,1}^n
满足：
- 对每个密钥 k，Ek(⋅) 是一个双射（bijection），即一个置换（permutation）一对一；
- 存在高效的逆函数 Dk=Ek−1，使得 Dk(Ek(x))=x。
PRP 是一个可逆的 PRF，且其输出空间与输入空间相同，并构成一个排列。
安全分组密码就是需要成为安全伪随机置换。
PRF 生成 PRG
数据加密标准DES
64bits输入初始置换（重新排列）--16轮Feistel网络--初始置换逆操作--得到输出
Feistel网络
将输入分为R0 L0左右两个块，初始的R0放到下一轮的L1，下一轮的R1是这轮的f(R0) ROX L0
S盒（Substitution-box，替换盒）
S盒是分组密码中实现非线性替换的基本结构。
DES中输入 6 位，输出 4 位，通过查表实现非线性替换，表格如下所示：
Exhaustive Search穷举搜索攻击
尝试所有可能的密钥，直到找到能正确解密出有意义明文的那个密钥。
DES挑战，可以被穷举搜索攻击破解密文
3DES 是对 DES 的加强，用三次 DES 操作（通常是 E-D-E 模式）来提升安全性。
为什么不用 2DES？
因为中间相遇攻击（meet in the middle attack）使其有效安全强度仅为 ~57 位，远低于预期的 112 位。
攻击步骤：
- 正向：用所有可能的 k1 加密明文 P，得到中间值 X=Ek1(P)，存入表。
- 反向：用所有可能的 k2 解密密文 C，得到 X′=Dk2(C)。
- 找到 X=X′ 的配对 → 对应的 (k1,k2) 就是候选密钥。
AES高级加密标准
高级加密标准（Advanced Encryption Standard），是目前最广泛使用的对称分组密码。
| 项目 | 值 |
|---|---|
| 分组长度 | 固定128 位（16 字节） |
| 密钥长度 | 128、192 或 256 位（对应 AES-128、AES-192、AES-256） |
| 加密轮数 | 10 轮（128 位密钥）、12 轮（192）、14 轮（256） |
核心结构：SPN 网络
AES 基于SPN（Substitution-Permutation Network）：
- S：非线性替换（通过S盒）
- P：线性扩散（行移位 + 列混淆）
每轮操作包括（最后一轮只有2、3）：
- AddRoundKey：与轮密钥异或（XOR）
- SubBytes：每个字节通过 S盒非线性替换（提供混淆）
- ShiftRows：状态矩阵的行循环左移（增加扩散）
- MixColumns：每列进行线性变换（进一步扩散）
基于PRG的分组密码PRF构建（GGM 构造）
PRG：将一个长度为n的种子，扩展成一个长度为m的输出，其中m > n。
PRF：对于不同的输入x，输出PRF(k, x)看起来是完全随机且独立的。
把输入k当作二叉树路径，用 PRG 逐层展开，重复多次得到kn，非常慢，但只要PRG安全，PRF就安全
Many-time key
- 指同一个密钥被用于加密多个消息。
- 这在现实中非常常见（比如你用同一个 Wi-Fi 密码加密每天的上网数据）。
- 只要加密方案设计正确（如带随机 IV），many-time key 是安全的。
- 如果方案是确定性的（如 ECB 或重复使用 nonce），就会出问题。
选择明文攻击（Chosen-Plaintext Attack,CPA）
一种安全模型，用于评估加密方案的安全性。
同一明文加密得到的密文相同
选择明文加密，攻击者给两个一样的信息m0,m0，获取他选择的特定消息m0的密文，之后再发m0,m1，看密文就能知道那个消息被加密了，这是不安全的。
CPA安全的模型允许many-time key
Nonce-based 加密
Nonce（Number used once）仅使用一次的数，它不需要保密，通常随密文一起传输，在同一个密钥下，nonce 绝不能重复使用，不一定需要随机（但常是随机或计数器（计数器的范围要够大不能重复）），只需唯一性。
引入 nonce 后，每次加密：c=Enck(nonce,m)
nonce 不保密，随密文一起发送。
即使 m 相同，只要 nonce 不同，密文就不同 → 实现CPA 安全。
CBC密码块连接
CBC（Cipher Block Chaining，密码块链接）是一种经典的分组加密工作模式，用于将固定长度的分组密码（如 AES、DES）扩展为可加密任意长度消息的安全方案。
引入初始向量（IV）和链式异或，使相同明文块加密后产生不同密文，消除 ECB 模式的模式泄露问题。
基于nonce的CBC
rand ctr-mode随机化计数器模式
随机化计数器模式（Randomized CTR Mode）是CTR 模式（Counter Mode）的一种标准安全用法，核心在于使用随机 nonce来实现CPA 安全的加密。
CTR 模式基本思想
CTR 将分组密码（如 AES）转换为流密码：
- 不直接加密明文，而是用密钥 k 加密一个递增的计数器值，生成 keystream；
- 明文与 keystream 异或得到密文：
Ci=Pi⊕Ek(counteri)
随机 nonce + CTR = 安全流式加密
3.数据完整性message integrity
MAC（Message Authentication Code）消息认证码
保证消息的完整性、真实性。
- 通过MAC签名算法生成一个短标签tag和m一起发送S(k,m)->t
- 对方通过MAC验证算法计算tag是否是’yes'V(k,m,t)->0,1
- 同时要共享一个对称密钥k，来保证消息不被篡改
消息 M：需要被认证的原始数据（如文本、文件、网络数据包）；
共享密钥 K：发送方与接收方预先约定的秘密密钥（双方独有，第三方未知）；
MAC 算法：公开的哈希 / 加密类算法（如 HMAC、CMAC），用于将 “消息 + 密钥” 转化为固定长度的 MAC基本流程
发送方： 1. 持有 消息M + 共享密钥K 2. 用 MAC 算法计算：Tag = MAC(K, M) 3. 发送 消息M + 标签Tag 给接收方 接收方： 1. 收到 消息M' + 标签Tag' 2. 用自己的共享密钥K和收到的M'，计算 Tag'' = MAC(K, M') 3. 对比 Tag' 与 Tag''： - 若相等：说明M未被篡改，且发送方持有合法密钥（来源真实） - 若不等：说明M被篡改，或发送方无合法密钥（来源伪造）特点
- 完整性：任何对消息的篡改都会导致 MAC 值变化，接收方可通过对比发现篡改；
- 认证性：只有持有共享密钥的合法方才能生成正确的 MAC 值，可验证消息来源；
- 无抗抵赖性：MAC 依赖共享密钥（双方都持有），无法区分是发送方还是接收方生成的标签，因此不具备 “抗抵赖” 能力（这是与数字签名的核心区别）；
- 固定长度：无论消息长短，MAC 输出的标签长度固定（如 HMAC-SHA256 输出 256 比特）。
一个安全的 MAC 必须满足：
不可伪造性（Unforgeability under Chosen-Message Attack,UF-CMA）
即：即使攻击者能获取任意(m,t)【允许发起选择消息攻击】，也无法伪造新消息的有效 tag。
没有加密的 MAC ：内容公开但可信
常见的 MAC 算法
HMAC（哈希消息认证码）
- 原理：基于哈希函数（如 SHA-1、SHA-256）和共享密钥，是应用最广泛的 MAC 算法；
- 特点：无需依赖对称加密算法，计算高效，安全性由哈希函数和密钥强度保证；
- 典型应用：HTTPS 协议的消息认证、API 接口签名（如阿里云 / 腾讯云接口）。
CMAC（Cipher-based MAC）
- 原理：基于对称分组密码（如 AES），将消息分块后用密钥加密计算认证标签；
- 特点：安全性与底层分组密码绑定，适用于已部署对称加密系统的场景；
- 典型应用：金融领域的交易数据认证、物联网设备的通信校验。
GMAC（Galois/Counter Mode MAC）
- 原理：基于 AES-GCM 模式的认证组件，可同时实现加密和认证（AEAD 算法）；
- 特点：支持并行计算，效率高，常用于高速通信场景；
- 典型应用：TLS 1.3 协议、5G 通信的数据加密与认证。
MAC 与数字签名的核心区别
MAC 和数字签名都能实现消息认证，但核心差异在于密钥体系和抗抵赖性：
| 特性 | 消息认证码（MAC） | 数字签名 |
|---|---|---|
| 密钥体系 | 共享密钥（对称密钥） | 非对称密钥（公钥 + 私钥） |
| 核心能力 | 完整性 + 来源认证 | 完整性 + 来源认证 + 抗抵赖 |
| 密钥持有方 | 发送方和接收方都持有 | 发送方持私钥，接收方持公钥 |
| 典型算法 | HMAC、CMAC | RSA-SHA256、ECDSA |
