生日攻击

理解问题

举个例子，想象一位老师问一个有30名学生的班级（n = 30）每个人的生日在哪一天（为简便，此处省略闰年）以确定是否有两个学生同一天生日（对应碰撞）。从直觉角度考虑，几率看起来很小。若老师选择特定日期（例如9月16日），则至少有一名学生在那天出生的概率是，约为7.9%。但是，与我们的直觉相反的是，至少一名学生和另外任意一名学生有着相同生日的概率大约为70.63%（n = 30时），从方程中可看出。

源码示例

下列是能准确生成上方表格中大多数数值的Python函数：
from math import log1p, sqrtdef birthday(probability_exponent, bits):
    probability = 10.0**probability_exponent
    outputs = 2.0**bits
    return sqrt(2.0*outputs*-log1p(-probability))
若代码保存在命名为birthday.py的文件中，您可和下面的例子一样交互运行此程序：
$ python -i birthday.py
>>> birthday(-15, 128)824963474247.1193>>> birthday(-6, 32)92.68192319417072

数字签名敏感度

数字签名可对生日攻击十分敏感。设想一条被首次计算（为密码散列函数）所签名的信息，且随后又使用了一些密钥来签名。假设爱丽丝与鲍伯牵涉到签名诈骗合同。马洛里准备了一份正常合同和一份伪造合同。她随后发现所在的位置数可在不改变原意的情况下（如插入逗号、清空行、在句后增加一两个空格、替换同义词等等）被更改。通过结合这些更改，她可新建诸多的变体且均为正常合同。
相似情况下，马洛里也为伪造合同新建了诸多变体。她随后应用哈希函数到所有变体直到她找到与正常合同有着相同哈希值的伪造合同位置。她随后将正常合同带给鲍勃签名。在鲍勃签名完后，马洛里将签名取下并依附到伪造签名上。此签名“证实了”鲍勃签署了伪造合同。
此例中，攻击概率与原始的生日问题稍有不同，因为马洛里将在寻找两份具有相同哈希的正常合同与伪造合同时将一无所获。马洛里的策略是生成一份伪造和一份正常的合同。生日问题公式适用于为合同对数的情况下。但马洛里所生成的哈希数实际上为。
为避免这种攻击，用于签名方案的哈希函数的输出长度应够大以从计算角度防止生日攻击。换言之，位数应为防止普通暴力破解所需位数的两倍。
除了使用更大的位数长度外，签名者（鲍勃）可以在签名前做出一些随机且无害的更改，并且在自己的手上留下一份合同副本以在法庭上展示出他的签名与正常合同上的匹配，而不匹配伪造合同。
离散对数Pollard Rho 算法是一项使用生日攻击以计算离散对数的算法。