通过这两种场景我们会发现 ， 数字签名也未必可信 。 目前技术的快速发展 ， 使得数字签名的伪造成为可能 ， 虽然这种攻击方式的门槛仍然较高 ， 但随着算力和算法的发展 ， 该攻击方式的实施成本会进一步降低 ， 这也是为什么我们需要不断探索强度更高的密码算法 。
HASH 碰撞与生日攻击
HASH 碰撞在数学上有一个原型叫“生日攻击” ， 问题是“一个班级需要有多少人 ， 才能保证每个同学的生日都不一样？” 。 这里我先直接说答案 ， 你肯定会十分吃惊 ， 如果要求出现相同生日的同学概率不超过 5% ， 那么这个班只能有 7 个人；如果概率是 50% ， 那么这个班只需要 23 个人 。
如果按照 HASH 碰撞的角度来理解 ， 哈希值的空间范围是 365 ， 只需要计算 23 个哈希就有 50% 的概率出现碰撞 。 接下来我们就以 50% 为标准 ， 来判断通用意义上 HASH 碰撞的可行性 。
数学推导
这里我们仍然以生日攻击为例 ， 来推导数学公式 。 如果所有人的生日都不相同 ， 那么意味着每个同学需要在选择自己生日时 ， 排除已经被选择掉的天数 ， 在剩余的日期中做出选择 。
p(n) = 1 · (1-1/365) · (1-2/365) · ... · (1-(n-1)/365)
参考泰勒公式：
e^x = 1 + x + x^2/2 + x^3/6 + ...
在x很小的情况下 -> e^x ≈ 1 + x
将泰勒公式带入 p(n)：
p(n) ≈ 1 · e^(-1/365) · (-2/365) ··· (-(n-1)/365)
= e^(-n(n-1)/730)
进一步将 p(n) 通用化 ， 并将结果从不碰撞转换为碰撞的概率：
p(nh) = 1 - e^(-n(n-1)/2h)
进行简单的数学变换：
n(ph) = (2h·ln(1/(1-p)))^1/2
实际应用中 ， 暂时我们以 50% 为标准 ， 将 0.5 代入 p：
n(0.5H) = 1.1774 · (h ^ 1/2)
抽象理解和安全验证边界
从抽象层面来看 ， 生日攻击的理念类似于以空间换时间的攻击方式 。 主要原因是生日攻击的目标一般是 HASH 碰撞 ， 而 HASH 计算的本质是将近乎无限的输入映射到定长或者有限长的 hash 串 ， 这就注定了多对一的映射关系 。 因此 ， 必然存在两个输入 M1 和 M2 能够满足 HASH(M1)=HASH(M2) ， 这其中的 M1 和 M2 就是我们定义的 HASH 碰撞攻击结果 。
尤其值得注意的是 ， 这里我们探讨的 HASH 碰撞与生日攻击 ， 没有利用任何 HASH 函数内部的实现机制 ， 因此这种攻击是具有通用型的 ， 而防御方式也相对简单 ， 只需要增加 HASH 的长度 ， 提高攻击者的计算成本即可 。
"
推荐阅读
- 北京市教委|翁铁慧调研北京高校大学生就业创业工作
- 隔离点|天津一高校成隔离点粗暴转运学生物品，网友喊话去“抄作业”
- 江西|江西6所“民办高校”！暂停招生，立即整改！
- 评价|完善评价机制增强高校教师职业自豪感
- 文化|教育部支持106所高校建设中华优秀传统文化传承基地
- 年检|江西6所“民办高校”！暂停招生，立即整改！
- 高校|省人社厅、省档案局关于深化档案专业人员职称制度改革的实施意见（四）
- 安阳|杭州和成都，谁家的高校实力更强？
- 高校|二本中的985和211，这些学校实力堪比名校，报考学生占大便宜
- 高校|年薪50万以上的人，学历大多数是什么水平？很多学生看后沉默了