哈希函数
Last updated
Last updated
定义：哈希函数是将任意长度的消息映射成一个较短的定长输出消息的函数。
形式为h=H(M) ，其中M是变长的消息，h是定长的哈希值。
目的：为文件、消息或其他的分组数据产生“数字指纹”。
正向快速：给定明文和哈希算法，在有限时间和有限资源内可以计算出哈希值
输入敏感：原始输入信息修改一点信息，产生的哈希值有很大的不同
逆向困难：给定特定哈希值，在有限时间内基本不可能逆推出明文
冲突避免：很难找到两段内容不同的明文，使得它们的哈希值一致（发生冲突）
区块链中一般采用比MD5安全性更好的SHA2系列的哈希算法，SHA2系列生成的hash值更长，SHA256、SHA512这些数值代表哈希长度。
如果达到密码学安全，还需要以下附加特性：
碰撞阻力（collision- resistance）
隐秘性（hiding）/不可逆性
谜题友好（puzzle- friendliness）
定义：如果无法找到两个值，x与y，x与y不相同但是H(x)=H(y)，那么称哈希函数H具有碰撞阻力。
找不到碰撞，并不意味着碰撞不存在
碰撞阻力可以用于信息摘要，比如文件存储系统生成信息摘要：SHA256(file)
定义：哈希函数H具有隐秘性，如果当输入x选自一个符合高阶最小熵的概率分布，在给定H(x)时，确定x是不可能的。
该特性的作用就是不可逆性，如果仅仅知道哈希函数的输出，没有可行的办法算出输入值x。
要求：
x需要取值自一个很广泛的集合
仅仅通过尝试几个特定的x，找不到特定的输出值
隐秘性一个应用例子：make a commitment
定义：如果对于任意n位输出值y，假定x选择高阶最小熵分布，如果无法找到一个可行的办法，在比2^n小很多的时间内找到x，保证H(x)=y成立，那么我们称哈希函数H为谜题友好。（只能一个一个去试错）
