网络安全攻防：密码技术之散列算法

gclome

原文链接：网络安全攻防：密码技术之散列算法

密码学上的散列算法是一种测试与保障消息完整性的有效方法，散列函数可以接受任意长度的明文信息输入，输出的是一个固定长度的字符串，这个字符串就叫作散列值或信息摘要。

散列算法是独立于对称密码和公钥密码体制的，因为它不需要解密，是一种保障信息完整性的鉴别算法。假设Alice想要给Bob一些方法，使Bob能确认接收了她发来的完整的信息，她可以将信息的摘要伴随着的信息（可能已经加密）一起发给Bob，一旦Bob接收到了信息，Bob 就可以用相同的方法再次计算出这段信息的摘要，然后将新的摘要和Alice 发来的摘要进行比对。如果相同则说明消息是完整的，如果不同，那么Bob就知道这些数据可能在传输途中遭到黑客篡改。

因此，散列算法在密码学上应满足如下特征。

（1）输入长度可以是任意长度，即可对任意明文计算散列值。

（2）输出是固定长度，如MD5是128 bit长度，SHA则是256 bit。

（3）给出任意的报文可以很轻松地算出散列函数H(x)。

（4）散列函数是个不可逆的函数，即给定一个Y，其中，Y=H(x)，无法推算出x。

（5）散列函数不存在碰撞，即不存在不同于x的一个x′，使H(x′)=H(x)。

（6）散列函数存在雪崩效应，即明文即使只有细微不同，其散列值结果也会明显不同。

例如，采用MD5散列函数对两个明文的处理结果如下。

MD5(“zhejiang university of technology”)=7419750C3359FE1D
MD5(“zhejiang university ov technology”)=85FDE61CC94FD1A1

MD5的全称是Message-Digest Algorithm 5（信息—摘要算法），在20世纪90年代初由MIT Laboratory for Computer Science和RSA Data Security Inc的Ronald L.Rivest提出，经MD2、MD3和MD4发展而来。由于国内学者王小云教授在2005年首次找到了MD5散列的碰撞，因此最新的业界标准算法已转到安全散列算法SHA-1和SHA256。

散列算法的典型应用是对一段信息（Message）产生信息摘要（Message-Digest），以防被篡改。例如，在 Unix 下有很多软件在下载的时候都有一个文件名相同，文件扩展名为.md5的文件，在这个文件中通常只有一行文本，大致结构如下。

MD5(zjut.tar.gz)=0ca175b9c0f726a831d895e269332461

这就是zjut.tar.gz文件的数字指纹。MD5将整个文件当作一个大文本信息，通过其不可逆的字符串变换算法，产生了这个唯一的 MD5 信息摘要。我们常常在某些软件下载站点的某软件信息中看到其 MD5 值，它的作用就在于可以在下载该软件后，对下载回来的文件用专门的软件（如Windows MD5 Check等）做一次MD5校验，以确保获得的文件与该站点提供的文件为同一文件。利用 MD5 算法来进行文件校验的方案被大量应用到软件下载站、论坛数据库、系统文件安全等方面。

MD5还广泛用于操作系统的登录认证上，如Unix、各类BSD系统登录密码、数字签名等诸多方。如在Unix系统中用户的密码是以MD5（或其他类似的算法）经散列运算后存储在文件系统中。当用户登录的时候，系统把用户输入的密码进行 MD5 散列运算，然后再去和保存在文件系统中的MD5值进行比较，进而确定输入的密码是否正确。通过这样的步骤，系统在并不知道用户密码的明码的情况下就可以确定用户登录系统的合法性。这可以避免用户的密码被具有系统管理员权限的用户知道。MD5将任意长度的“字节串”映射为一个128 bit的大整数，并且是通过该128 bit反推原始字符串是困难的，换句话说就是，即使看到源程序和算法描述，也无法将一个 MD5 的值变换回原始的字符串，从数学原理上说，是因为原始的字符串有无穷多个，这有点像不存在反函数的数学函数。所以，要遇到了MD5密码的问题，比较好的办法是：可以用这个系统中的md5()函数重新设一个密码，如admin，把生成的一串密码的散列值覆盖原来的散列值就行了。

正是因为这个原因，现在被黑客使用最多的一种破译密码的方法就是一种被称为“跑字典”法。有两种方法得到字典，一种是日常搜集的用做密码的字符串表，另一种是用排列组合方法生成的，先用MD5程序计算出这些字典项的MD5值，然后再用目标的MD5值在这个字典中检索。假设密码的最大长度为8 B，同时密码只能是字母和数字，共26+26+10=62个字符，排列组合出的字典的项数则是P(62,1)+P(62,2)+…+P(62,8)，那也已经是一个很天文的数字了，存储这个字典就需要 TB 级的磁盘阵列，而且这种方法还有一个前提，就是能获得目标账户的密码MD5值的情况下才可以。因此，散列函数依然是当前最被广泛应用的密码技术。