Birthday Attack
生日攻击利用生日悖论：在约 2^(n/2) 次 hashing 后有 50% 概率找到 n 位哈希碰撞，决定哈希所需输出长度。
用途
设定哈希输出长度的下界，确保碰撞搜索不可行。
机制
生日悖论：23 人中有 50% 概率两人同生日。对哈希，n 位输出空间下，约 1.177×√(2^n) = 1.177×2^(n/2) 次随机输入即有 50% 碰撞概率。因此 128 位哈希仅需 2^64 次不安全。
用例
- 哈希输出长度选择
- 数字签名安全级别
- 证书有效期评估
- 密码学教学
示例
- 输入
128-bit hash输出Collision found in 2^64 trialsInsecure
常见错误
- Assuming an n-bit hash needs 2^n trials to collide
- Collisions take only 2^(n/2); use outputs of at least 256 bits