在服务器上一般不用明文存储用户的密码，而是存储密码的哈希值 (hash values)，该值可由密码原字符串输入哈希函数 (hash function) 计算得到。

概念

A hash function takes an arbitrary-length message $ m $ and returns a fixed-length hash value (message digest) $ h(m) $ . 即：

$$ h:{0,1}^* \to {0,1}^r $$

其中 $ * $ 是输入的任意字符串的长度；$ r $ 是输出的定长字符串的长度。

对于 MD5 (Message-Digest Algorithm 5，信息-摘要算法 5)， $ r=128 $，即 16 字节；对于 SHA-1 (Secure Hash Algorithm 1，安全散列算法 1)， $ r=160 $，即 20 字节。这样的哈希值是 0 和 1 的组合，但一般表示成 16 进制。

一般哈希函数是公开的，因此所有人都能校验某个字符串或文件（实质也是 0 和 1 的序列）的哈希值。

此外，两个不同文件也可能有相同的哈希值（因为文件的总数显然多于定长哈希值所有组合的总数），但这样的情况实际概率极低。

特性

哈希函数可具有以下特性：

单向性 (One-way)

考虑问题 [P1] – Given $ y $ where $ y = h(x) $, to find $ x $.

若：解决 P1 非常困难 (computationally infeasible)，也即知道 $ x $ 的 message digest 却难以倒推计算出 $ x $，则称该函数是 an “one-way” function.

弱抗碰撞性 (Weak Collision Resistance)

考虑问题 [P2] – Given $ x $, find $ x’ $ such that $ x \ne x’ $ but $ h(x) = h(x’) $. ($ x, x’ $ is called a collision if $ h(x) = h(x’) $ ).

若：解决 P2 非常困难 (computationally infeasible)，也即已知一个输入及其输出，难以找到另一个输入具有相同的输出哈希值（因此也难以在不被察觉的情况下替换文件），则称该函数是 weak collision resistant 的。

强抗碰撞性 (Collision Resistance, or Strong Collision Resistance)

考虑问题 [P3] – Find $ x $ and $ x’ $ such that $ x \ne x’ $ but $ h(x) = h(x’) $.

若：解决 P3 非常困难 (computationally infeasible)，也即难以找到两个不同的输入具有相同的输出（虽然必然是存在的），则称该函数是 strong collision resistant 的。

应用

例 1 – 登录密码的校验过程：输入用户名、密码后计算密码的哈希值，并在服务器中比对“用户名-哈希值”对。该场景要求哈希函数具备特性 1，而不一定要具备特性 2、3。值得注意的是，在这样的场景中，有极小概率输入错误的密码仍能登录（可能与另一个密码的哈希值相同）。

例 2 – 下载文件时的哈希校验：计算出下载到电脑上的文件的哈希值，并与某处（例如官网）提供的哈希值比较，以判断文件是否被恶意篡改。该场景要求哈希函数必须具备特性 2。