认识 PHP 的hash函数

Hashing function (散列函式) 在网页应用中被广泛采用，从数码签署、错误检测、登入验证、到压缩储存空间，由于它的原理比较复杂，很多人把它跟加密函式混淆，对于如何运用hash function，如何选择合适的hash function，和它的优点缺点都不清楚，本文尝试解

Hashing function (散列函式) 在网页应用中被广泛采用，从数码签署、错误检测、登入验证、到压缩储存空间，由于它的原理比较复杂，很多人把它跟加密函式混淆，对于如何运用hash function，如何选择合适的hash function，和它的优点缺点都不清楚，本文尝试解答这些问题。

简单地说，Hashing 是一种数据影射(mapping) 的算法(algorithm)，通常用来把一大串不定长度的数据影射到一个固定长度的、较短的数据，这个固定长度的数据称为hashing value (散列值)。

例如我们把一个由英文字母组成的任意长度的字串，把每一个字符的ASCII 数值加起来，最后除以256 得到的余数作为hash value，这里输入的字串长度没有限制，输出的数值则必定在0 至255 之间，所以是一个合法的hashing function。

以上的hash function 只有256 个可能的hash value，很明显有很多字串都会得到相同的hash value，这种情况我们称为hash collision (散列冲突)，或者简称collision，事实上从一个不定长度的数据影射到一个固定长度的数据，Collision 是无可避免的，我们并不要求完全没有collision，只需把collision 的机会尽量降低便可以了，若果真的要完全没有collision 的话，Hash value 理论上必须与输入的数据长度相同，这样便违背了hash function 的设计目的。

现实应用的hashing function 通常比较复杂，比较有名的包括MD4、MD5、SHA1、SHA256 等，它们的hash value 的数量从2 的几十次方到几百次方。其实我们任何人都可以自行设计一个hashing function，不过基于hashing function 的实际用途，我们对hashing function 有一些基本要求，在进一步解释前，让我们看看hashing 有什么常见的用途。
Hashing 的用途

1.

数码签署

很多提供程式下载的网站，都会在网页上列出下载档案的hash value，比较常见的是MD5 码，下载的人可以自行计算下载回来的档案的hash value 是否与网站提供的相符，从而验证这个程式是否曾经被修改，这个过程就是数码签署。数码签署的概念可以应用在很多通讯领域，例如你要发送一个很重要的电子邮件给别人，为了让收件者放心内容在传送过程中没有被其他人擅改，你可以另外告诉收件人电子邮件的MD5 码，让他自行验证。

在这种用途中，理想的hashing function 应该具备两种特性，首先是任何对原本文件的改动都会令产生的hash value 改变；第二是没有方法可以得知如何该动原本的文件使计算出来的hash value 相同。

当然，我们还要确保hash value 不会在传送途中被人拦截并且修改，但这属于通讯安全的问题，超越了hash function 的讨论。
2.

错误检测

资料在网络上传送的时候，会受到很多干扰而使内容改变，其中包括网络问题、电脑硬件问题、电脑程式问题等，为了检验资料的正确性，我们可以一并把资料的hash value 发送给收件者，让收件者比对自行计算的hash value 和收到的hash value 来确认资料的正确性。

在这种用途种中，理想的hash function 跟上面的要求差不多，就是任何对原本资料的改动都会令产生的hash value 改变。
3.

登入验证

在伺服器上储存用户的系统密码是有风险的，第一这样做等于把密码的安全交托给伺服器管理员，他们一定可靠吗？别忘记密码万一泄漏背黑镬的是你而不是他们啊；第二很多用户把相同的密码应用在很多不同的系统（这样做当然很不好，但你无法限制用户不可以这样做），当一个系统被黑客入侵泄漏了用户的密码，他们在其他系统的帐号也同时中门大开，后果可以很严重。为了保障用户，设计良好的系统都不会直接储存用户的密码，只会储存密码的hash value。用户登入时输入的密码，会被转换成hash value，然后与伺服器上储存的hash value 比较来进行身分验证。

这种用途的hash function，必须是不可能返过来从hash value 计算原本的密码。此外，由于collision 的缘故，只要找到一个密码，它的hash value 与用户的密码的hash value 相同，便可以冒认这名用户登入系统，无须知道真正的密码，所以hash value 的数量必须非常庞大，使collision 的可能性很低很低，使寻找这个「伪冒」密码的人要付出很大的代价。
4.

压缩储存空间

Hash function 其中一个最经典的用途是制作hashing table (散列表)，它可说是一个关联阵列(associative array)，阵列的指标是一些不定长度的数据或者是比较复杂的数据结构，很多高阶编程语言包括PHP、Perl、gawk 等都支援关连阵列，背后的原理就是利用hash function 把这些数据转换成数字，然后读取阵列中的元素。在大部分的情况下，作为阵列指标的数据可以非常庞大，但是阵列的长度(元素的数量) 相对来说却很少，所以冲突的情况会比较突出，从用户(编程人员) 的角度冲突是不应该发生的，不同的数据便应该对应到不同的阵列位置，所以这些语言都有某些方法来处理冲突。

用hash table 来实作关联阵列的好处是搜索资料的速度高，无论有多少资料，搜索的速度都是固定的，这一点对于要处理大量数据的应用很重要。

PHP 有什么 hashing 工具？

Hash Functions	Hash value 的长度 (bit)
CRC32	32
MD5	128
SHA-1	160

（在PHP5.12以后可以使用 hash_algos()返回所有的hash算法，并从手册上得知现支持 35种算法；查看手册）

在PHP5 之前我们只有CRC32、MD5 和SHA1 三个内置的hash function，它们输出的hash value 长度如下：
Hash Functions Hash value 的长度 (bit)
CRC32 32
MD5 128
SHA-1 160

其中SHA-1 可说是最多人使用的hash function，原因是它的hash value 比其他的大，Collision 的机会便小得多。其次SHA 家族的hashing functions 是由美国国家安全部(NSA – National Security Agency) 设计，并被列为美国联邦资讯处理标准的一部分，所以给人较高的信心，很多复杂的安全方案例如SSL 都使用SHA-1。

PHP 还有两个需要额外安装的函式库支援更多hash function，就是mhash 和hash，Hash 从PHP 5.1.2 开始列为标准的模组，无须自行编译或安装，所以越来越多人使用。一些比SHA-1 更先进的hash function 都可以在这两个函式库中找到，例如属于SHA-2 家族的SHA-256 和SHA-512 等，不过由于SHA-1 的历史比较悠久，很多系统仍然继续使用它，尤其是用SHA-1 来进行登入验证的系统，由于hash function 的不可还原性，很难一下子改用其他hash function。

使用SHA-1 的方法很简单(PHP 的函式大都很简单，不是吗？)：

echo sha1("I am a happy boy");

Hash 的用法也很简单：

echo hash("sha256","I am a happy boy.");

Hash 支援很多hash function，可以用hash_algo 查看你的PHP 版本支援什么：

print_r(hash_algos());