生日悖论与密码学威胁

用一个反直觉的概率问题引入课程：23 人房间中至少两人生日相同概率超过 50%。

• 问题：一个房间至少有多少人，两人生日相同的概率超过 50%？
• 答案是 23 人，远小于 365
• 直觉与数学的冲突：这不是魔术，而是概率
• 本课将看到它如何威胁密码学

让学习者在看到答案前先选择一个自己认为正确的概率，激活直觉。

• 单选题：23 人中至少两人生日相同概率约为？
• 选项：5% / 25% / 50% / 99%
• 先凭直觉作答，后面揭晓

通过改变房间人数，实时观察至少两人生日相同的概率如何增长，建立直觉。

• [Chart] 概率曲线：横轴人数（1-80），纵轴碰撞概率
• 操作人数滑块，观察 50% 对应的临界点
• 验证 23 人时概率超过 50%，50 人时约 97%

从补事件出发推导碰撞概率公式，并用近似式说明碰撞规模与样本空间的关系。

• 无碰撞概率：(365/365)×(364/365)×…×((365-k+1)/365)
• 碰撞概率 P ≈ 1 - e^{-k(k-1)/(2N)}
• P=0.5 时 k≈1.177√N，生日问题中 N=365 → k≈23
• [Chart] 概率曲线：横轴人数 k，纵轴 P(k)

把生日问题映射到哈希碰撞：哈希输出空间等价于“生日”，寻找两个输入等价于随机抽取样本。

• 哈希函数将任意输入映射为固定长度输出（如 256 位）
• 两个不同输入产生相同输出称为碰撞
• 找碰撞就像在 N 个“生日”中找重复，N = 2^n
• 生日悖论告诉我们：大约测试 √N = 2^(n/2) 次就会出现碰撞

解释生日攻击的核心思想：攻击者只需约 2^(n/2) 次哈希运算就能找到碰撞，因此 n 位哈希只提供 n/2 位抗碰撞安全级别。

• 目标：找一对输入 (x, y) 使 H(x)=H(y)
• 随机查询 q 次后碰撞概率 ≈ q^2/(2N)，N=2^n
• q ≈ √N = 2^(n/2) 时已有不可忽略的碰撞概率
• 结论：n 位哈希的抗碰撞强度不是 n 位，而是约 n/2 位
• [Table] 输出长度 vs 实际碰撞工作量：128→约2^64，256→约2^128

举例说明生日攻击在真实世界已造成安全事件：MD5 与 SHA-1 的碰撞被实际利用，威胁数字签名与证书体系。

• MD5 输出 128 位，生日攻击只需约 2^64 次；MD5 已被实际碰撞
• SHA-1 输出 160 位，2017 年公开碰撞演示（SHAttered）
• 攻击者可用碰撞构造两份不同内容的相同签名：恶意 PDF 与良性 PDF 共享同一哈希
• 恶意证书与受信任证书共享同一哈希时，可影响 TLS 信任链
• [Table] 算法 / 输出 / 理论碰撞成本 / 状态

说明密码系统如何通过更大的输出长度、抗碰撞设计和安全协议来抵御生日攻击。

• 使用足够长的哈希输出：SHA-256（256 位）将碰撞成本提高到约 2^128 次
• 优先选择 SHA-2 / SHA-3 等经受检验的哈希函数
• 在签名方案中采用更保守的安全参数，避免 128 位以下输出
• 涉及用户生成内容时，用随机化哈希或域分隔降低利用碰撞的风险
• 安全评估：不要把 n 位输出当作 n 位抗碰撞强度

通过两道题检验学习者是否掌握生日攻击的安全强度影响与防御选择。

• 第 1 题：SHA-256（256 位）的抗碰撞安全强度约为多少？
• 第 2 题：下列哪些措施能缓解生日攻击威胁？
• 完成作答后进入总结

串联本课核心：生日悖论如何把抽象概率变成密码学现实威胁，并给出可迁移的判断方法。

• 生日悖论：碰撞概率比直觉快得多，规模约 √N
• 在密码学中：n 位哈希的抗碰撞强度约为 n/2 位
• 真实攻击已利用 MD5 / SHA-1 的碰撞影响签名与证书
• 设计新系统时，先按 n/2 估算碰撞工作量，再选择足够大的哈希输出