密码学简介（二）

楼主^#

更多发布于：2011-12-09 05:57

[] 1


	散列函数散列函数，也叫杂凑函数，实际就是哈希（Hash）函数，“散列函数”是信息安全领域惯用的译法。不论从概念还是从形式上看，它跟数据结构课程上讲的哈希函数的确如出一辙：基于任意输入都产生定长的输出，且好的散列函数值域会分布得尽量平均。然而，信息安全领域使用的散列函数却有着诸多安全方面的要求。像针对字符串的每个字节不断乘以一个素数并取模的那种哈希函数，在数据结构领域用于构造关联数组已经相当好了，但在信息安全领域却远远不合格。除任意输入，定长输出之外，信息安全领域中使用的散列函数还有以下要求（设H是散列函数）：（1）单向性：已知内容（常称为“报文”）x，计算h = H(x)相对容易；而已知散列值h1，要寻找给定的内容x1，使H(x1) = h1则非常困难；（2）抗冲突性：已知报文x，寻找另外一个报文y，使得H(x) = H(y)非常困难。最好能做到：随便找一对x，y，使H(x) = H(y)都非常困难。一般前者称为弱抗冲突性，后者称为强抗冲突性。此外，一个好的散列函数也应该具有本文（一）中曾经提到的“雪崩效应”。常见的散列函数包括MD5，SHA系列等。 MD5可针对任意输入产生128bit（16字节）的输出。SHA是一组散列函数的统称，包括SHA-0、SHA-1、SHA-2等，产生160到512bit之间的散列值。 MD5目前已被证明不够安全，2004年，山东大学王小云教授证明：可在合理的时间内找到“非特定”的碰撞。所谓非特定，打个比方说，你写一篇小说，保存为一个doc文件，我能在可接受的时间内制造出另外一个文件，产生的散列值跟你这个文件产生的一模一样，但当你要打开它时，却发现Word未必能打开它，即使打开也可能是乱码，即使不是乱码也可能无意义，即使有意义也不一定是一篇小说…… 散列函数的一大用途是构造数字签名（见后文介绍），而要破解数字签名，在散列这一关上，必需找到“特定”碰撞。继续使用上面的比方，就是也要找到一篇小说，保存为Doc后能产生一模一样的散列值。然而，且不讨论问题的严重程度，它毕竟是被人发现了问题，趁它还没有被完全破解，赶紧抽身才是王道。著名的C++加密库crypto++早已把MD5放进了一个叫做“Weak1”的名字空间中。关于散列函数，需要澄清一个普遍存在的误区：散列不是加密。散列函数是单向的，所以，上文提到的“破解”指的是寻找碰撞，而非恢复原文。别忘了，散列函数能针对任意输入产生固定长度的输出，倘若能恢复原文，那它岂不成了世上最酷的压缩算法了? 密码保存说到散列函数，不得不提一下它的另一项重要功能：“保存”密码。注意这里的密码指的是用户口令，比如操作系统的用户登录密码，它跟之前一直讨论的“密钥”不是一个概念。不知大家可曾考虑过操作系统是如何保存用户登录密码的。直接保存明文吗？玩笑，当然不能。那自然是加密咯？可是，加密用的密钥放哪里呢？怎么放呢？明文吗？又开玩笑了…… 或许有朋友想到了非对称加密。由于非对称加密中有一个密钥可以不公开，于是，让软件开发商来保存其中的一个密钥就安全了。这种想法是不成立的。因为设置用户密码时需要加密，验证用户登录时则需要解密——也就是说，两个密码都必需保存在系统中。所以，非对称加密在这里是派不上用场。一种可行的方案是利用散列函数。具体方法是：（1）创建用户时，根据选定的用户名和用户输入的口令，再加一其它一些信息，比如时间戳，随机数（注意这些信息都要保存起来）等，共同作为散列函数（比如SHA）的输入，产生的散列值保存在一个系统文件中（需系统管理员的权限才能修改）。（2）之后用户登陆时，把用户输入的口令，同样附上之前保存的附加信息作为散列函数的输入，再次计算散列值，并把这个值跟系统文件中保存的值进行比较，如果相同，则认为用户通过了验证。很简单很强大，不是吗？再说明几点：第一，附加额外信息是为了增加方案的安全性，倘若只用口令本身作为散列输入，那么同样的口令就会产生同样的散列值，于是，如果有用户看到系统文件中对应某个用户的散列值与自己的一样，就可以断定那个用户的口令跟自己一样。第二，方案的安全性来自哪里？当然是散列函数的强度。即之前强调的两点：单向性和抗冲突性。第三，以上只是基本原理，具体实现中会涉及其它细节。说到这里，可能许多朋友已经明白了为什么许多系统中用户密码可以修改但无法恢复，原因就是系统并没有保存你的密码，也没保存任何可恢复出密码的信息。这也正是它安全的地方之一：负责验证密码的组件都不知道密码本身，那除了用户自己，谁还能知道密码呢？这早已是成熟的技术，现实情况却是很多系统并不使用它，仍以明文形式保存密码。下次再看到有网站可以把密码以明文形式发到你的信箱中，你就知道他们有多么不专业和不负责了。