【密码学】杂(瞎)谈(聊)哈希函数

简介: 本文依然是闲聊,不讲具体的算法内容,来一个小总结,相信大家看过我写过的文章之后,应该对于md系列算法 sha系列算法 sm3等哈希函数比较熟悉了,不熟悉的读者,我再来安利一下我之前写过的文章或者大家也可以去查阅相关的资料,在这里不再重复描述算法的具体内容了,本文呢,针对哈希函数来一个小小的总结,来看一下哈希函数有哪些公共的特性。

7MQI$VU6X69629GVVCDYGS3.jpg哈希函数

本文依然是闲聊,不讲具体的算法内容,来一个小总结,相信大家看过我写过的文章之后,应该对于md系列算法 sha系列算法 sm3等哈希函数比较熟悉了,不熟悉的读者,我再来安利一下我之前写过的文章或者大家也可以去查阅相关的资料,在这里不再重复描述算法的具体内容了,本文呢,针对哈希函数来一个小小的总结,来看一下哈希函数有哪些公共的特性。


什么是哈希函数?

「哈希函数」H使用变长的数据分组M作为输入,生成固定长度的结果h = H(M)这一值也称为哈希值或者散列值。对于广义上的哈希函数而言,这个实际上就是把某个任意大小的集合映射到某个固定长度的集合里面,就好比我们编程语言经常会用到的哈希表,里面也是用到了哈希函数。

)%]P8XT5]BJ5UGT9MGI83JX.png

image.gif哈希函数


可能对于上面的描述,读者看起来还是不太好理解,下面我来举一个简单的例子,相信大家都用过电话本,没用过实体的电话本相信大家手机大概率是有通讯录的,可能手机上没有存通讯录的习惯,那么相信能够看到这篇文章的读者,大概率是一个微信用户,微信里面同样会有联系人,我们来定义一个简单的哈希函数,这个哈希函数呢,就是把联系人的拼音的首字母取出来,当做最新的哈希值,这里我们再来简化一下,假设联系人的名称都可以抽象为3个字(不要问为什么要这么做,上面说了,哈希函数要映射到固定长度的大小)。

我们来看下面的通讯录,如下的人名均为我虚拟出来的,如有雷同纯属巧合。

  • 张三一(zsy)
  • 张三二(zsr)
  • 张三三(zss)
  • 张三四(zss)

这里,我们发现,最后两个名字所对应的哈希值是一样的,这其实就是哈希冲突,也就说明,我这个定义的哈希函数是比较差的,比较容易的去找到一组冲突。不过虽然我这个哈希函数质量比较差,不影响他看做是一个哈希函数。


非密码学的哈希函数

之前我们提到的md5 sha1 sm3之类的,其实都是密码学安全的哈希函数(虽然某些已经发现不安全因素,不推荐使用了),但是对于哈希函数大家庭来说,不仅仅有密码学安全的哈希函数,还有非密码学安全的哈希函数,这些函数呢,其实不太追求在密码学当中的安全性,但是在某些场景下,也有他独特的优势。

举一个简单的例子,我们常见的短网址应用,我们需要把一个不定长的网址URI转换成为一个比较短的,固定长度的值,对于这个需求,哈希函数的定义太贴合了,那么我们是不是可以使用md5 sha1 sm3之类的来实现呢,这实际上是可以的,但是呢,对于短网址来说,我们需要的是更快的计算,较少的冲突,我们不需要他符合密码学哈希函数的所有特性(有关密码学哈希函数的特性,接下来的章节在讲)对于密码学安全的哈希函数来说,他的计算相对来说是比较慢的,可能大家没有体会,大家思考一下是不是就突然火一把的btc,他的pow就是基于密码学安全的哈希函数,如果这种哈希函数可以被非常快速计算,那么就没有矿工什么事儿了。

对于短网址来说,我们希望它计算的越快越好,可以满足这个需求的算法也比较多,比如说MurmurHash算法,这个算法在2008年被发明出来,在很多软件比如Redis,openresty,LevelDB,MemCache等等都有应用,这个算法有两种长度的哈希值(这里指的v2/v3,这里给自己挖个坑,请叫我挖坑小能手,后面具体聊一聊这个算法的具体结构,这里就不展开讲了)分别是32bits和128bits对于短网址而言,我们采用32bits的结果就可以了。当然对于短网址生成来说,也有不基于哈希函数来实现的,可以采用分布式发号器(Distributed ID Generator)来实现,这里也不过多去描述了。对于MurmurHashmd5计算速度的比较,可以参考文末的参考资料,这里对于Lua的实现来说前者的速度是后者的将近10倍。


密码学的哈希函数

这里,我们来聊一下有关密码学哈希函数的特征,对于密码学哈希函数来说,我们不仅仅需要只是让一个值变为另一个值的映射,而且还需要保持一定的安全特性。

抗原像性

先来回顾一下之前学过的什么是原像,原像是数学当中函数的一个概念,函数h的输出h(x)通常称为x的像,因此x被称为h(x)的原像。哈希函数应该是抗原像的,说人话就是哈希函数的逆运算是困难的,也就是对于一个哈希值,我们想找到是哪个值计算而来的这个是十分困难的。

抗第二原像性

这个和抗原像性类似,这个是指,对于一个哈希函数h, 给定一个输入值x, 以及他输出的哈希值h(x) 很难找到一个不等于x的y 使得h(y) = h(x) 。换句话就是,给定一个输入值以及一个哈希值,很难找具有相同哈希值的另一个不同的输入值。

这两个安全属性的差异在于,前一个是根据哈希值,攻击者无法推断计算哈希值之前的内容,后一个是指,即时攻击者拿到了哈希前和哈希后的内容,很难找到另一个其他的值,使得哈希之后的内容相同。

抗碰撞性

之前我们提到的哈希冲突,也就是发生了碰撞,这个是指,我们很难找到两个不同的x和y使得h(x) = h(y),看起来这个和上面所提到到的抗第二原像性有些类似(这条约束比上一条要强,有些地方吧抗第二原像性也叫做抗弱碰撞性,而后者称之为抗强碰撞性,换句话说,也就是如果一个函数是抗碰撞的,那么他一定是抗第二原像的),只不过这里没有给定的哈希值了,而是针对所有的输入,都很难找到两个一样的值。

这里后面两个所说的都是十分困难,而不是绝不可能,对于现代密码学来说,保证在有限的算力和时间下不可能就足够了,因为哈希函数是从无穷集合到有限集合的一个映射,因此根据鸽巢原理我们必定能找到一组冲突的值,只不过找到这组冲突的值,可能消耗的算力或者时间是我们现在无法接受的。

F56VCWJ1BQ)R$DOL%MK9)08.png

哈希函数安全特性


小结

本文主要介绍了一下什么是哈希函数,以及密码学哈希函数需要满足那些特性,对于一般的哈希函数来说,我们不一定要去追求他的安全特性,比如说字典的实现,短网址,或者说是图片名称保存这些,我们只是要他冲突小,速度快就够了,而对于密码学来说,我们是需要保证他的安全特性的,比如数字签名,密码的存储,我们可能要牺牲一部分的性能来换回更加的安全。举个简单的例子,比如说我们拿到一个密码的哈希值,那么我们希望去找到这个原来密码的明文,这里我们只能去通过不断的穷举实现,假设两个哈希算法的抗碰撞性程度相似,那么如果一个哈希算法的计算时间要更长,那么对应的穷举时间也会相应的增加,因此这就更加能保护我们密码的安全,还是那句话,安全和效率其实不太好做到双赢,我们只能在安全和效率中间取得一个trade off。

相关文章
|
Rust 算法 安全
【密码学】一文读懂MurMurHash2
上次我们聊过了一代的MurMurHash算法,是的,我又来水文章了,今天呢,接着来聊一下二代的MurMurHash算法,二代算法的整体结构实际上和一代算法差不太多,只是对于每一轮数据的处理过程当中的运算有一些差异,算法的来源依然是来自于Google官网给提供的源码,对着源码看的结构,对于这个算法呢,有两个版本,一个是32位的,一个是64位的,对于32位的算法和64位的算法,区别在于两个初始的魔数不同,整体运算过程还是十分相似的。
2623 0
【密码学】一文读懂MurMurHash2
|
存储 缓存 NoSQL
HyperLogLog——用户日活(dau)、月活(mau)统计
HyperLogLog——用户日活(dau)、月活(mau)统计
294 1
|
测试技术 异构计算
【FPGA基础入门实践】Verilog 基本项目操作逐步演示
【FPGA基础入门实践】Verilog 基本项目操作逐步演示
527 0
|
传感器 存储 边缘计算
3000字11张图硬核科普:什么是边缘计算?与云计算有什么联系和区别?
边缘计算是 现代IT 网络架构的一种创新的、革命性的方法,计算处理去中心化并在靠近数据源的网络“边缘”执行它,数据不再发送到云或任何单个数据处理中心,而是被发送到靠近传感器或生成此数据的设备数据源,极大的提高了数据的处理速度,节省了大量的带宽,还提高了数据的安全性。
1348 0
3000字11张图硬核科普:什么是边缘计算?与云计算有什么联系和区别?
|
Rust 算法 Go
【密码学】一文读懂MurMurHash3
本文应该是MurMurHash算法介绍的最后一篇,来一起看一下最新的MurMurHash算法的具体过程,对于最新的算法来说,整个流程和之前的其实也比较相似,这里从维基百科当中找到了伪代码,也就不贴出来Google官方给出的推荐代码了,先来看一下维基百科给出的伪代码,这里只有32位的伪代码。
2785 0
【密码学】一文读懂MurMurHash3
|
存储 关系型数据库 MySQL
如何处理爬取到的数据,例如存储到数据库或文件中?
处理爬取的数据,可存储为txt、csv(适合表格数据)或json(适合结构化数据)文件。若需存储大量数据并执行复杂查询,可选择关系型(如MySQL)或非关系型(如MongoDB)数据库。以MySQL为例,需安装数据库和Python的pymysql库,创建数据库和表,然后编写Python代码进行数据操作。选择存储方式应考虑数据类型、数量及后续处理需求。
235 1
|
数据采集 数据可视化 数据挖掘
数据抽样技术全面概述
抽样是研究和数据收集中不可或缺的方法,能够从更大数据中获得有意义的见解并做出明智的决定的子集。
773 2
|
机器学习/深度学习 文字识别 算法
【Keras计算机视觉OCR】文字识别算法中DenseNet、LSTM、CTC、Attention的讲解(图文解释 超详细)
【Keras计算机视觉OCR】文字识别算法中DenseNet、LSTM、CTC、Attention的讲解(图文解释 超详细)
594 0
|
存储 安全 数据处理
阿里云oss收费标准图文详细介绍
阿里云OSS是阿里巴巴集团旗下的云计算服务提供商,提供了一系列高效、可靠、安全的数据存储、数据处理和分析服务。它充分利用了云计算技术的优势,为用户提供了全新的数据管理体验。
|
存储 SQL 分布式计算
云计算与大数据期末考试题库(二)
云计算与大数据期末考试题库(二)
1494 0