抗碰撞性、生日攻击及安全哈希函数结构解析

回想一下，在密码学中上一篇的内容涉及完整性。完整性通过一段定长的部分来实现——具体来说是一个哈希值（Tag）。由于哈希值具有固定长度，在实际应用中需要处理的信息类型却是无限多的可能性。因此必然存在这样的情况：当两个不同的信息块mi和mj被输入时（mi≠mj），它们对应的Tag会相同（即存在mi≠mj但Tag(mi)=Tag(mj)的情况发生）。为了应对这种情况带来的风险，在密码系统中必须引入抗碰撞性这一概念。

抗碰撞性：

抗碰撞性(Collision-resistant)：经过一系列计算实验发现，在X集合中的任意两个不同元素x和x’进行处理后得到的结果相同的情况极其罕见（计算不可行）；此外称为强抗碰撞性（Strong Collision-resistant）。相反的是弱抗碰撞性（Weak Collision-resistant），这一概念也被提出并应用于相关领域。

弱抗碰撞性：在给定一条消息的散列值时，单向散列函数必须确保找到另一条具有相同散列值的消息也非常困难。
强抗碰撞性：指的是要找到两条不同的消息拥有相同的散列值也非常困难。

而针对碰撞性的攻击，最主要的要数生日攻击了：

生日攻击（Birthday Attack）：

生日悖论（Birthday paradox）：

生日悖论即指，在一个房间里如果有至少23人时，则至少两人同生