概率论基本概念
样本空间 Ω：所有可能结果的集合。
事件：样本空间的子集。
概率 P(A)：事件 A 发生的可能性，满足 0 ≤ P(A) ≤ 1，P(Ω) = 1。
基本规则
- 加法规则：P(A ∪ B) = P(A) + P(B) - P(A ∩ B)
- 乘法规则：P(A ∩ B) = P(A) × P(B|A)
- 独立事件：若 P(A ∩ B) = P(A) × P(B)，则 A, B 独立
- 全概率公式：P(A) = Σ P(A|Bi) × P(Bi)
- 贝叶斯定理：P(B|A) = P(A|B) × P(B) / P(A)
随机变量与分布
随机变量：从样本空间到实数的映射。
- 均匀分布：每个结果等概率，是密码学最常用的假设
- 二项分布：n 次独立伯努利试验中成功的次数
- 几何分布：首次成功所需的试验次数
期望 E[X]：随机变量的加权平均值。
方差 Var(X) = E[(X - E[X])²]：衡量随机变量的离散程度。
生日悖论
问题：在一个房间里至少需要多少人，才能使其中至少两人生日相同的概率 ≥ 50%？
直觉上可能认为是 365/2 ≈ 183 人，但实际答案仅需 23 人！这就是"悖论"的含义。
推导
计算"所有人都不同"的概率：
P(全部不同) = (365/365) × (364/365) × (363/365) × ... × ((365-n+1)/365)
当 n = 23 时，P(全部不同) ≈ 0.493，所以 P(至少一对相同) ≈ 0.507 > 50%。
推广到一般情况
对于 N 个可能的值（如哈希函数的输出空间），要使碰撞概率达到 50%，大约需要 √(πN/2) ≈ 1.177√N 个随机样本。
更粗略的估计：约需要 √N 个样本就能以不可忽视的概率找到碰撞。
生日攻击
生日悖论直接导致对哈希函数的生日攻击：
对于 n 位哈希函数，输出空间为 2n。暴力碰撞搜索需要约 2n 次尝试，但利用生日攻击只需约 2n/2 次尝试。
具体例子
| 哈希算法 | 输出位数 | 暴力搜索 | 生日攻击 |
|---|---|---|---|
| MD5 | 128 | 2128 | 264 |
| SHA-256 | 256 | 2256 | 2128 |
| SHA-512 | 512 | 2512 | 2256 |
这就是为什么 MD5（128 位输出，264 即可碰撞）被认为不安全，而 SHA-256（需要 2128 次碰撞尝试）目前仍被认为安全。
信息论与熵
香农熵 H(X) = -Σ p(x) log₂ p(x)，衡量随机变量的不确定性。
均匀分布时熵最大。对 n 位随机变量，H = n bit。密码学追求密文具有最大熵（即均匀分布、无规律可循）。
完美保密性
如果 P(M=m|C=c) = P(M=m) 对所有明文 m 和密文 c 成立，则系统具有完美保密性——观察密文不提供关于明文的任何信息。
一次性密码本（One-Time Pad）是唯一达到完美保密性的密码系统，但要求密钥至少与明文一样长且只用一次。