$散列算法和应用

Sun, Jul 13, 2014

本来一直以为有机会直接的面对面的科普关于数据安全的知识，不过现在发现就是一厢情愿，还是写成博客比较好一点。 既然是概述篇，那么，无论你是否有电脑方面得基础，都可以理解这篇文章的内容。

首先，什么是散列算法。这个名字一看起来就很高大上，但是实际上，它的定义并不复杂。它的基本定义是将输入的数据打乱并将内容缩短.(这也是为什么在这类算法刚刚进入中国的时候在书籍中的翻译叫越压越陷算法.)而在数据经过这样的算法之后产生的结果叫散列值(摘要,指纹).尽管没有方法之间从中恢复原始数据,但是,对于每一个不同的文件,都会有一个不同的散列值(理想的散列算法).因此,散列算法有很大的用处,下面我来一一介绍.

##完整性校验##

完整性校验可以让两个人在不传输大量的数据的情况下,比较两个文件的内容.在目前,用途一般是校验通过网络传输的文件的完整性,因为网络传输相对于本地的散列计算来说是一个更加耗时的,使用散列值而不是整个文件进行校验可以显著的提高速度.

对于使用散列值的校验来说,最大的痛苦在于即使发现了问题,也无法从解决问题,只能面对一个失败的提示.在现代的互联网,通过更加强大的网络速度和网络传输的准确性,这个问题已经有了有效的缓解.但是在互联网的早期,人们发明了par算法来解决这个问题,本篇文章不深入研究.

在压缩软件中也有类似的机制(是因为在早期的压缩软件压缩完了解压就不是原来的文件了么>.<),对于有压缩密码的压缩包(实际上是其中的一部分),在解压之后会计算一次解压后数据的散列值,如果和之间存储的散列值相同的话,那么这个文件的解压就是成功的,否则就会提示密码错误.

##密码验证##

密码大家都很熟悉,但是密码验证的机制却鲜有人知.密码实际上是要存储在电脑上的,否则要如何知道输入的对不对呀.但是,将未经散列的密码存储在电脑上,无论是在登录本地系统或者登录在线帐号,都不是稳妥的做法,因为一旦电脑被直接取出硬盘,那么硬盘上的任何内容都可以被直接查看.这时,未经散列的密码也会被轻而易举的得到.这也就导致攻击者可以在相当低的成本下,在不被发现的情况下继续保持对于电脑的控制权.更糟糕的是,如果这个密码还在其他的地方被使用,那么攻击者也同样拥有了在其他地方的密码,这样一来,后果十分凄惨.

如果将密码在散列之后存储,就会有不一样的故事,攻击者就算已经得到了散列后的密码,依然无法访问系统,原因很简单,密码在被提交后会被散列,但是将散列值再散列一次之后得到的结果并不是本身,而是散列值的散列值.如果想知道一个散列值所代表的内容,成本十分的高昂,对于越长的密码,所需要的计算成本越大.因此在一定程度上而言,储存密码的散列阻止了攻击.

还有另一种方法,就是直接修改已经被记录的散列值.在这种情况下,攻击者确实可以得到对于系统的控制,但是,却无法在不让他人发现的情况下完成,一旦散列值被修改,原来的密码便无法再次登录,因此可以很快的发现被攻击,并采取减少损失的措施.

##计算量证明##

这个比较反人类一点,之前的两个是用来校验的,而这个第3种用法,是用来创造的(实际上也没有创造什么).

散列函数的输入和输出完全不能建立出任何有效的关联,所以对于一遍的使用来说,两个散列值之间只能比较是否相等,比较大于小于,是没有实际意义的.但是,在如比特币中,通过改变数据,使数据的散列值小于一个值成为了很多电脑计算的目标.

从某种意义上来讲,散列的结果就是随机数,如果要使这个数在一个范围之内,就需要尝试一定量的次数.又与随机数不同,对于同一个数据来说,同样的输入会导致相同的结果,所以可以验证数据的产生者确实经过了大量的尝试才得出这个成功品的.

散列函数的基本用法到这里就结束了,作为密码学的一部分,散列函数为人们通过技术改变生活提供了很好的平台.尽管在设计的时候可能并没有想到散列函数会有这样多的用途,但是,其却却实实成为了构建更好的生活的基石.(跳跃有点大…..)