关于散列函数的"强，弱无碰撞性"

0. 先搞懂：什么叫 “碰撞”

对于哈希函数 h(x)：

如果 两个不一样的输入 x ≠ y，却算出 相同的哈希值 h (x) = h (y)

这就叫碰撞。

无碰撞性 = 很难人为造出这种碰撞。

1. 弱无碰撞性（抗第二原像）

正式定义

给定任意一个 x，在计算上找不到另一个不同的 y（y≠x），使得 h(x) = h(y)。

人话翻译

• 对手手里已经有一个固定消息 x
• 他的目标：造一个不一样的 y，让哈希值和 x 一样
• 做不到 → 就是弱无碰撞

核心限制

必须固定一个 x，只允许找另一个配对的 y

2. 强无碰撞性（抗碰撞）

正式定义

在计算上找不到任意一对不同的消息 x、y（x≠y），使得 h(x) = h(y)。

人话翻译

• 对手完全自由，可以随便选 x、随便选 y
• 只要能找出任何一对不一样的东西哈希相同，就算攻破
• 做不到 → 就是强无碰撞

核心限制

没有任何限制，随便找一对碰撞都不行

3. 最关键的区别（一句话分清）

• 弱无碰撞： 给你一个原文，不准你造出第二个原文跟它撞
• 强无碰撞： 世界上不准存在任何两个不同原文会撞车

4. 安全强度关系

强无碰撞 ⇒ 弱无碰撞

• 如果一个哈希函数满足强无碰撞，那它一定满足弱无碰撞
• 反过来不成立

简单理解：

连 “随便找一对都找不到”，那 “给定一个再找一个” 肯定更找不到。

强的要求更严、更安全。

5. 超形象小例子

假设哈希函数是 “给名字算长度”：

• 弱无碰撞：给你名字「张三」（长度 2），不准你找另一个不同名字长度也是 2 → 做不到（李四也是 2）
• 强无碰撞：不准存在任何两个不同名字长度一样 → 显然不可能

6. 考试标准答题模板

弱无碰撞性

对任意给定的消息x，计算上不可行找到另一个不同的消息y(y≠x)，使得h(x)=h(y)。

强无碰撞性

计算上不可行找到任意一对不同的消息x,y(x≠y)，使得h(x)=h(y)。