密码学哈希函数的三个要素

        用于加密的哈希函数必须满足一定的安全性,否则就无法保障隐私数据不被泄漏。本文就来谈谈使哈希函数达到密码安全的三个要素。


1, 碰撞阻力(collision-resistance)---- 没有人能够找到碰撞

2, 隐秘性(hiding)---- 无法根据哈希输出计算出输入

3,谜题友好(puzzle-friendliness)---- 对于哈希输出,想要找到输入,必须随机去试,没有捷径可走


所谓的碰撞,就是说对于不同的输入,得到了相同的输出。

对于第一要素碰撞阻力,并不是说没有碰撞,而是没有人能够找到碰撞。事实上,也不存在没有碰撞的哈希函数。

根据鸽巢原理(Pigeonhole Principle),必然会有大量的不同的数据经过哈希,得到了相同的输出。

鸽巢原理就是说,n+1只鸽子想要住在n个鸽巢里面,那么必然有一个鸽巢住了两只或以上鸽子

因为输入集合大小是无穷大,而输出集合是有限的,那么必然产生碰撞。

事实上,碰撞产生的概率远远大于我们的直觉,这就叫做生日悖论。

生日悖论:在较小的群体中,两个或以上的人的生日是同一天的概率比人们的直觉大很多

只需要23个人,至少两个人的生日是同一天的概率就超过了50%。

计算方法如下:

我们只需要算出生日都不在同一天的概率,然后用1减去这个概率就行了。

那么P_{至少两个人的生日在同一天} = 1 - \frac{365}{365} * \frac{364}{365} * \frac{363}{365}*   ····

Python代码如下:


计算生日悖论的Python代码

所以,总结一下,第一要素碰撞阻力就是说很难找到碰撞。

对于像SHA256哈希算法,产生的结果有2^{256}种结果,这个数字已经非常大了,如果没有概念,可以找个例子对比一下:

据科学家估计,宇宙中大约有10^{80}个原子(参考:维基百科)。那么我们的2^{256}和10^{80}孰大孰小呢?笔者这里用Python结果来直观的比较下:

对比

可以看到,结果是比较接近的,对于这么多种可能,要碰撞自然很困难。


第二要素隐蔽性强调的是无法根据输出结果来推算出输入;

第三要素谜题友好强调的是生成因子是随机的,要想推算结果,必须随机去试,没有捷径可走;

二、三强调重点不同,二强调输入无法计算,三强调无捷径可走,必须随机去试。

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成,浏览时请结合常识与多方信息审慎甄别。
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

相关阅读更多精彩内容

友情链接更多精彩内容