第34章 哈希函数

哈希(hash)函数能够生成可靠程度较高的校验和(Checksum),可充分满足数据检验的需要。CRC32算法就是一种不太复杂的哈希算法。哈希值是一种固定长度的信息摘要,不可能根据哈希值逆向“推测”出信息原文。所以,无论CRC32算法计算的信息原文有多长,它只能生成32位的校验和。但是从加密学的角度看,我们可以轻易地伪造出满足同一CRC32哈希值的多个信息原文。当然,防止伪造就是加密哈希函数(Cryptographic hash function)的任务了。

此外,人们普遍使用MD5、SHA1等哈希算法生成用户密码的摘要(哈希值),然后再把密码摘要存储在数据库里。实际上网上论坛等涉及用户密码的数据库,存储的密码信息差不多都是用户密码的哈希值;否则一旦发生数据库泄露等问题,入侵人员将能够轻易地获取密码原文。不仅如此,当用户登录网站的时候,网络论坛等应用程序检验的也不是密码原文,它们检验的还是密码哈希值:如果用户名和密码哈希值与数据库里的记录匹配,它将授予登录用户相应的访问权限。另外,常见的密码破解工具通常都是通过穷举密码的方法,查找符合密码哈希值的密码原文而已。其他类型的密码破解工具就要复杂得多。

单向函数与不可逆算法

单向函数(one-way function))是一种具有下述特点的单射函数:对于每一个输入,函数值都容易计算(多项式时间);但是根据函数值对原始输入进行逆向推算却比较困难(无法在多项式时间内使用确定性图灵机计算)。本节着重讲解它的不可逆性。

假设函数的输入值是由10个介于0~9之间的数值构成的一组矢量,且矢量中的标量仅出现一次。例如:

4  6  0  1  3  5  7  8  9  2

下列算法即可实现最简单的单项函数:

本例中的第4位和第6位数字分别是:

4  6  0  1  3  5  7  8  9  2
            ^     ^

进行最终变换可得:

4  6  0  1  7  5  3  8  9  2

即使我们知道具体的算法和最终的函数值,我们也无法确定最初的输入值是什么。因为最初的位置参数值可能是0也可能是1,这两个参数可能会被交换位置。

以上只是对单向函数的一种简单说明。实际应用中的单向函数远比本例复杂。