哈希函数及其性质

目录散列函数及散列函数的特点 什么是散列函数？

哈希函数接受任何输入 x

可以是字符串数字或任何类型的任何值

并返回一个固定长度的值 y

此过程也称为散列或消化

所以散列函数有时会变成散列函数或摘要函数（digest algorithms）

常见的哈希函数（哈希算法）坏哈希函数的例子

将任意输入值视为字符串，将字符串中每个字符的值转换为ascII码表的整数值

将每个字符对应的ascII码表值相加得到一个整数

返回此整数模 256 的值 (

长度在0-255之间，即长度固定在8个二进制数00000000~11111111之间

即这个hash函数返回的值永远是1byte长的数据

无论我们输入什么值

此函数始终返回 0 到 255 之间的整数

这是一个有效的散列函数，但不是一个好散列函数

哈希 - 加密哈希

哈希在计算中有很多用途

比如在HashMap这样的数据集合中

这种数据结构实际上是根据元素的哈希值来决定将数据存储在内存中的哪个位置

或者在分库分库分表的场景下

根据key的hash值，考虑一条数据应该存放在哪个库/表中或者应该使用哪个库/表来查找这条数据

哈希函数有很多种，它们不同的特性决定了它们适用的领域

在区块链领域比特币采用的哈希算法是，哈希函数用于密码哈希

加密哈希的属性 Collision-free or collision-resistant collison-free

如果对于哈希函数 H(x)

如果：

x≠y

高（x）==高（y）

collison-free描述的特征是

如果我通过 H(x) 得到一个散列，那么其他人应该很难用不同的输入得到相同的散列

碰撞示例

以上面提到的坏散列函数为例

如果我们将“ATTACKATDAWN”作为输入，最终值将为 77

如果您使用“SIT DOWN###MEOW”。 作为输入，你得到的值也将是 77

哈希冲突是不可避免的

哈希函数的输入参数可以是任何可能的数据，这个数据集可以看成是无限的

但是由于hash函数的定义（返回值定长）

他只能将输入参数映射到一个比较小的数据集

这种从无限到有限的映射必然会重复

所以所谓的非碰撞或者防碰撞只是指在一个合理的时间范围内能否发现一个hash值的碰撞

如果哈希值的取值范围足够大

并且构造哈希值的算法合理，使得生成的值看起来是随机的

这是可以做到的（至少很难暴力破解）

哈希函数漏洞

如果哈希函数生成值

碰撞值可以比蛮力更快找到

那么可以说哈希函数是有漏洞的

但是，哈希函数可能不需要防冲突属性，具体取决于应用程序

所以也许有问题的哈希函数仍然被广泛使用

使用哈希作为消息摘要

如果我们使用的哈希函数是防碰撞的

如果 H(x) = H(y)

那么有理由相信 x=y

隐藏隐藏

指隐藏原始信息

无法从结果中推导出原始哈希函数输入值

即哈希函数应该是单向的

一个没有隐藏的哈希函数的例子：

如果我们知道H(x)的算法来生成哈希值

知道得到的哈希值为42

然后我们可以轻松地将 x 倒回 41

所以这里的H(x)不是隐藏哈希函数

承诺计划

为了理解隐藏的特性，想象这样一个例子

与b打赌

猜猜今年比特币的价值将突破10,000美元

但是他不想在赌注完成之前让b知道这个信息

那么a可以通过与b约定的哈希函数H(x)生成一个哈希值：

x = "今年一个比特币的价值将超过 10,000 美元"

H(x) = y

让 b 保持 y

兑现赌注和判断谁是赌注的赢家时，A提供x → “一个比特币的价值今年将超过10,000美元”

b 计算哈希值H(x)是否等于y，则可以知道a在建立赌注时用来生成哈希值的信息是不是“一个比特币的价值今年将突破10000美元”

在这个过程中a和b在信息没有完全传达的情况下完成了一次打赌

如果这个例子中提到的情况要成立，H(x)需要防碰撞和隐藏

如果不耐撞

a 在建立赌注时可以使用哈希值 y 提供的与 x 不同的信息（碰撞值）来完成赌注

毫不掩饰

b 得到哈希值 y 后，可以推断出 a 用来建立赌注的信息 x

本例的上述投注过程类似于区块链领域使用的CommitmentScheme，即提交方案

com = commit(m, nonce)

m是原始信息，nonce是一个随机值，只使用一次。 com可以理解为一个hash值

验证（com、msg、nonce）

验证过程需要提供哈希值com和生成这个com的m和nonce

如果m和nonce生成的hash值等于com，则验证通过

如果commit方法使用的hash函数是防碰撞隐藏的

那么就不太可能找到m'/nonce'（m'≠m nonce'≠nonce）

这样 commit(m',nonce,)=commit(m,nonce)

也保证了拟议提案的有效性

这里加入了随机值nonce，可以理解为当算法commit不变，原始信息m不变时

com为了得到不同的hash值的一种处理方式

nonce没有实际意义比特币采用的哈希算法是，只使用一次（类似于入库前对密码进行加盐和散列的过程）

益智友善

简而言之，拼图友好性是

没有生成特定或部分特定（以大于或小于特定值的值开始或结束）哈希值的捷径

没有其他方法可以生成特定的哈希值，而不是尝试

此功能称为益智游戏

工作量证明和益智游戏友好功能

即 H(x) 必须是拼图友好的

前面提到的坏散列函数对拼图友好吗？

因为算法生成的hash值来自于字符串每个字符对应的ascII码表的索引值之和

只需要简单调整输入的字符串内容就可以得到特定的哈希值

例如，将“A”替换为“B”可以使最终哈希值增加 1

否则减1

上面用作示例的哈希函数不适合拼图

比特币使用的哈希函数

本文为个人学习笔记