哈希(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
下列算法即可实现最简单的单项函数:
取第0位的值作为参数1(本例而言是4)。
取第1位的值作为参数2(本例而言是6)。
交换位于参数1、2位置处(第4、6位)的值。
本例中的第4位和第6位数字分别是:
4 6 0 1 3 5 7 8 9 2
^ ^
进行最终变换可得:
4 6 0 1 7 5 3 8 9 2
即使我们知道具体的算法和最终的函数值,我们也无法确定最初的输入值是什么。因为最初的位置参数值可能是0也可能是1,这两个参数可能会被交换位置。
以上只是对单向函数的一种简单说明。实际应用中的单向函数远比本例复杂。