
先看下wiki的定义:
单向函数(One-way function)是一种具有下述特点的单射函数:对于每一个输入,函数值都容易计算(多项式时间);但是对于一个随机的函数值,算出其对应的输入却比较困难(无法在多项式时间内使用确定性图灵机计算)。 单向函数是否存在仍然是计算机科学中的一个开放性问题。实践中,常将“容易计算”和“不容易计算”定义为“对于合法用户容易计算,对于恶意用户不容易计算”。从这个意义上,密码散列函数可以被当作单向函数。这是因为,虽然单向函数可能根本不存在,也无人能证明一个散列函数真的是单向函数,但也无人发现可以在合理时间内破解它们的实用算法。
单向陷门函数是有一个陷门的一类特殊单向函数。单向陷门函数包含两个明显特征:一是单向性,二是存在陷门。所谓单向性,也称不可逆性,即对于一个函数y=f(x),若已知x要计算出y很容易,但是已知y要计算出x=f ^(-1) (y)则很困难。单向函数的命名就是源于其只有一个方向能够计算。所谓陷门,也被称为后门。对于单向函数,若存在一个z使得知道z则可以很容易地计算出x=f ^(-1) (y),而不知道z则无法计算出x=f ^(-1) (y),则称函数y=f(x)为单向陷门函数,而z称为陷门。
散列函数(英語:Hash function)又称散列算法、哈希函数,是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据压缩成摘要,使得数据量变小,将数据的格式固定下来。该函数将数据打乱混合,重新创建一个叫做散列值(hash values, hash codes, hash sums,或hashes)的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库更难找到。
在密码学中上述三个概念都有涉及,RSA、离散对数、ECC等公钥密码算法就是基于单向陷门函数来实现,而MD系列和SHA系列是典型的密码散列函数。
回到题主的问题,哈希函数其实是一个比较模糊的统称,在密码学和计算机科学中会稍有不同。
在密码学中,哈希函数更加类似于指纹的功能,追求的是生成hash value(字符串)的唯一性和随机性,同时难以找到逆向规律。显然,一个有限长度的字符串,它能表示的所有字符串组合是有限的。为了保证hash value的唯一性,哈希函数的输入必须是无限长的,同时hash函数也要保证一一映射,这在目前是无法实现的。因此,实践中采取了概率的思想,把hash value的长度取得相对较大,比如256位的二进制,所有的组合就是2^256种(不要小瞧这个数字,它其实已经很大了),然后把任意长度的输入串都映射到固定256位长度的二进制串中。可以发现上述映射过程中哈希碰撞不可避免,但是由于hash函数输出空间足够大,同时采用均匀散列的设计,保证了发生碰撞的概率很低,当然,也不绝对,有兴趣可以参考王小云院士的论文看看。所以,理论上,如果两个输入字符串对应的输出hash value不相同,基本可以断定这是两个不同的输入。
在计算机科学中,哈希函数可以看成是密码学中哈希函数简单版。比如在Java中,一个对象的hash code 是一个32位的二进制数,它是根据对象的属性值简单计算出来的,这个hash code是所有对象的属性值一起混淆的结果。再比如,在某些集合和数据库中,常常使用一个对象或者字段的hash code来建立索引,方便进行数据查找。可以发现,计算机中使用的hash value的长度要更小,毕竟内存和磁盘都是有限的,不可能搞的很大,其实也没必要,这导致了发生碰撞的概率更高,但是可以通过开放寻址和再散列等方式来解决(判断对象相等可以通过调用equals());其次,计算hash value的过程并不严格要求难以逆向,因为不用考虑被破解的问题,所以计算过程相对简单,计算速度快。
最后,题主问业界是不是有什么作为实际上标准的、常用的哈希函数?在密码学中,MD系列和SHA系列有大公司,大机构、开源社区实现的工具包,可以直接下载使用。当然,也可以自己动手写,原理和步骤都是公开的,就是写出来性能可能一般。在计算机中,经常使用平方取中法,折叠法,除留取余法等一些散列性质比较好的算法来作为哈希函数,同样可以自己设计,但是要衡量算法的好坏就需要反复测试了。
水平有限,写的不对,还望指出!
